832. Flipping an Image

97.14 %
class Solution {
    public int[][] flipAndInvertImage(int[][] A) {
if (A == null || A.length == 0 || A[0] == null || A[0].length == 0) return A;
int cols = A[0].length;
for (int y = 0; y < A.length; y++) {
int left = 0;
int right = cols - 1;
while (left <= right) {
if (left == right) {
A[y][left] ^= 1;
} else {
int temp = A[y][left] ^ 1;
A[y][left] = A[y][right] ^ 1;
A[y][right] = temp;
}
                left++;
                right--;
}
}
return A;
}
}

929. Unique Email Addresses

need to escape special chars in .split()
no need to escape in .replace()

59.26 %
class Solution {
    public int numUniqueEmails(String[] emails) {
Set<String> set = new HashSet<>();
for (String email : emails) {
String[] parts = email.split("@");
String local = parts[0].split("\\+", 2)[0];
set.add(local.replace(".", "") + "@" + parts[1]);
}
return set.size();
}
}

743. Network Delay Time

Version #1 Dijastra

1 BUG-> it is possible that a node be added to minHeap more than once
Since we are marking visited when we are polling it -> it is possible that one node is not polled yet and it is added one more time with an larger distance
So we have to check visited in to place
-> right after we poll out one node
-> before we add a node to minHeap


25.65 %
class Solution {
    /*
times[i] = (u, v, w), where u is the source node, v is the target node,
and w is the time it takes for a signal to travel from source to target.
*/
public int networkDelayTime(int[][] times, int N, int K) {
//  source        target   weight
Map<Integer, Map<Integer, Integer>> graph = new HashMap<>();
for (int[] time : times) {
// time[0]-source, time[1]-target, time[2]-weight
graph.computeIfAbsent(time[0], weightMap -> new HashMap<>()).put(time[1], time[2]);
}
int max = Integer.MIN_VALUE;
boolean[] visited = new boolean[N + 1]; // since nodes are 1 indexed
// a[0]-current node, a[1]-weight from source
PriorityQueue<int[]> minHeap = new PriorityQueue<>(Comparator.comparing(a -> a[1]));
minHeap.offer(new int[]{K, 0});
while (!minHeap.isEmpty()) {
int[] curr = minHeap.poll();
int index = curr[0], distance = curr[1];
if (visited[index]) continue;
// System.out.println(index + " " + distance);
max = Math.max(max, distance);
visited[index] = true;
Map<Integer, Integer> neighbors = graph.get(index);
if (neighbors != null) {
for (int neighbor : neighbors.keySet()) {
if (!visited[neighbor]) {
minHeap.offer(new int[]{neighbor, distance + neighbors.get(neighbor)});
}
}
}
}
for (int i = 1; i < visited.length; i++) {
if (!visited[i]) return -1;
}
return max;
}
}

694. Number of Distinct Islands

二刷 05/2022

Version #2 BFS

Hash each island into List<List<Integer>>

Each position is normalize by calculating the offset from the left top grid of the island

caveat: 这里如果用int[]是不work的，可能int array的hash function是由地址代替的

Runtime: 21 ms, faster than 30.36% of Java online submissions for Number of Distinct Islands.

Memory Usage: 54.5 MB, less than 20.22% of Java online submissions for Number of Distinct Islands.

class Solution {

    public int numDistinctIslands(int[][] grid) {

        if (grid == null || grid.length == 0 || grid[0] == null || grid[0].length == 0) {

            return 0;

        }

        // Find all points of an island and store them in List<int[]>

        // Since we iterate from smaller to larger indexes, the fisrt grid in the list is always the top left grid

        // Normalize an island by calculate the relative position of every point with the top left point

        // Store the island grid list in a hash set

        Set<List<List<Integer>>> islands = new HashSet<>();

        int rows = grid.length, cols = grid[0].length;

        boolean[][] visited = new boolean[rows][cols];

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (!visited[y][x] && grid[y][x] == 1) {

                    // Expand an island from starting point (x, y) and returns all of its grids

                    List<List<Integer>> island = findIsland(grid, y, x, visited);

                    islands.add(island);

                }

            }

        }

        return islands.size();

    }

    

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    List<List<Integer>> findIsland(int[][] grid, int y, int x, boolean[][] visited) {

        List<List<Integer>> island = new ArrayList<>();

        Queue<List<Integer>> que = new ArrayDeque<>();

        que.offer(Arrays.asList(y, x));

        visited[y][x] = true;

        while (!que.isEmpty()) {

            List<Integer> curr = que.poll();

            island.add(Arrays.asList(curr.get(0) - y, curr.get(1) - x));

            // iterate all 4 directions

            for (int i = 0; i < 4; i++) {

                int ny = curr.get(0) + dy[i];

                int nx = curr.get(1) + dx[i];

                // out of the boundary

                if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length) {

                    continue;

                }

                if (!visited[ny][nx] && grid[ny][nx] == 1) {

                    visited[ny][nx] = true;

                    que.offer(Arrays.asList(ny, nx));

                }

            }

        }

        return island;

    }

}

Test Cases:
[[1,1,0,0,0],[1,1,0,0,0],[0,0,0,1,1],[0,0,0,1,1]]
[[1,1,0,1,1],[1,0,0,0,0],[0,0,0,0,1],[1,1,0,1,1]]

一刷
Version #1 DFS
Hash each island by grids offset from its left most & top grid

58.50 %
class Solution {
    public int numDistinctIslands(int[][] grid) {
// when we see the left,top grid of an island, try to expand it
// keep track of each grid by its relative position, seperated by " "
// use a string to encode the shape of each island
Set<String> set = new HashSet<>();
StringBuilder sb = new StringBuilder();
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == 1) {
dfs(grid, y, x, 0, 0, sb);
set.add(sb.toString());
sb.setLength(0);
}
}
}
return set.size();
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private void dfs(int[][] grid, int y, int x, int offY, int offX, StringBuilder sb) {
sb.append(offY).append(" ").append(offX).append(" ");
grid[y][x] = 0;
for (int i = 0; i < 4; i++) {
int nextY = y + dy[i];
int nextX = x + dx[i];
if (nextX >= 0 && nextX < grid[0].length && nextY >= 0 && nextY < grid.length
&& grid[nextY][nextX] == 1) {
dfs(grid, nextY, nextX, offY + dy[i], offX  + dx[i], sb);
}
}
}
}

695. Max Area of Island

三刷 07/2022

Version #3 Union Find

Time O(MN) - we have 4 MN union operations, union with size rank and path compression will result in amortized O(1) time

Space O(MN)

Runtime: 6 ms, faster than 25.46% of Java online submissions for Max Area of Island.

Memory Usage: 48 MB, less than 21.47% of Java online submissions for Max Area of Island.

class Solution {

    private static int ISLAND = 1;

    class UnionFind {

        private int[] size;

        private int[] id;

        private int rows;

        private int cols;

        int maxSize = 0;

        public UnionFind(int[][] grid) {

            rows = grid.length;

            cols = grid[0].length;

            size = new int[rows * cols];

            id = new int[rows * cols];

            for (int y = 0; y < rows; y++) {

                for (int x = 0; x < cols; x++) {

                    int index = getIndex(cols, y, x);

                    if (grid[y][x] == 1) {

                        maxSize = 1;

                        size[index] = 1;

                        id[index] = index;

                    }

                }

            }

        }

        

        

        public int root(int i) {

            while (id[i] != i) {

                id[i] = id[id[i]];

                i = id[i];

            }

            return i;

        }

        

        public void union(int p, int q) {

            int rootP = root(p);

            int rootQ = root(q);

            if (rootP == rootQ) {

                return;

            }

            if (size[rootP] < size[rootQ]) {

                id[rootP] = rootQ;

                size[rootQ] += size[rootP];

                maxSize = Math.max(maxSize, size[rootQ]);

            } else {

                id[rootQ] = rootP;

                size[rootP] += size[rootQ];

                maxSize = Math.max(maxSize, size[rootP]);

            }

        }

        

        public int getMaxSize() {

            return maxSize;

        }

        

    }

    

    public int getIndex(int cols, int y, int x) {

        return y * cols + x;

    }

    

    private int[] dx = new int[]{1, 0, -1, 0};

    private int[] dy = new int[]{0, -1, 0, 1};

    

    public int maxAreaOfIsland(int[][] grid) {

        int rows = grid.length;

        int cols = grid[0].length;

        UnionFind uf = new UnionFind(grid);

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (grid[y][x] != ISLAND) {

                    continue;

                }

                int index = getIndex(cols, y, x);

                for (int i = 0; i < 4; i++) {

                    int ny = y + dy[i];

                    int nx = x + dx[i];

                    if (ny < 0 || nx < 0 || ny >= rows || nx >= cols || grid[ny][nx] != ISLAND) {

                        continue;

                    }

                    uf.union(index, getIndex(cols, ny, nx));

                }

            }

        }

        return uf.getMaxSize();

    }

}

二刷 06/2022

We could also use stack based DFS to avoid using recursion

Version #2 DFS without changing the original matrix

Time O(MN)

Space O(MN)

Runtime: 4 ms, faster than 52.28% of Java online submissions for Max Area of Island.

Memory Usage: 47.4 MB, less than 48.23% of Java online submissions for Max Area of Island.

class Solution {

    public int maxAreaOfIsland(int[][] grid) {

        int rows = grid.length;

        int cols = grid[0].length;

        boolean[][] visited = new boolean[rows][cols];

        int max = 0;

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                if (grid[y][x] == 1 && !visited[y][x]) {

                    visited[y][x] = true;

                    max = Math.max(max, dfs(grid, visited, y, x));

                }

            }

        }

        return max;

    }

    private static int[] dx = new int[]{1, 0, -1, 0};

    private static int[] dy = new int[]{0, -1, 0, 1};

    

    // Return how many 1s are in current island

    private int dfs(int[][] grid, boolean[][] visited, int y, int x) {

        int count = 1;

        for (int i = 0; i < 4; i++) {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (nx < 0 || ny < 0 || nx >= grid[0].length || ny >= grid.length || visited[ny][nx] || grid[ny][nx] != 1) {

                continue;

            }

            visited[ny][nx] = true;

            count += dfs(grid, visited, ny, nx);

        }

        return count;

    }

    

}

一刷
Version #1 DFS


43.59 %
class Solution {
    public int maxAreaOfIsland(int[][] grid) {
// iterate through the grid, if we see any 1, we try to expand this island
// set any visited grid to 0
int max = 0;
for (int y = 0; y < grid.length; y++) {
for (int x = 0; x < grid[0].length; x++) {
if (grid[y][x] == 1) {
max = Math.max(max, dfs(grid, x, y));
}
}
}
return max;
}
private int[] dx = new int[]{1, 0, -1, 0};
private int[] dy = new int[]{0, -1, 0, 1};
private int dfs(int[][] grid, int x, int y) {
// return the size of current island
int size = 1;
grid[y][x] = 0;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (nx >= 0 && nx < grid[0].length && ny >= 0 && ny < grid.length
&& grid[ny][nx] == 1) {
size += dfs(grid, nx, ny);
}
}
return size;
}
}

725. Split Linked List in Parts

Version #1 Straight-forward


98.82 %
class Solution {
    public ListNode[] splitListToParts(ListNode root, int k) {
//[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
//Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
// length = 10, bucketLength = 10/3=3, residual = 10%3 = 1
ListNode[] result = new ListNode[k];
ListNode curr = root;
int length = 0;
while (curr != null) {
length++;
curr = curr.next;
}
int bucketLength = length / k;
int residual = length % k;
curr = root;
for (int i = 0; i < k && curr != null; i++) {
int len = bucketLength;
if (residual > 0) {
len++;
residual--;
}
result[i] = curr;
ListNode prev = null;
while (curr != null && len > 0) {
prev = curr;
curr = curr.next;
len--;
}
prev.next = null;
}
return result;
}
}

729. My Calendar I

二刷 08/2022

Version #1 TreeMap

一个bug，如果用floorKey(end)的话//  [19,25)[25,32)[33,41)[47,50) 要加入[19,25)就会失败，因为25的floorKey是[25,32)entry，然后32又比19大

所以应该用lowerKey

注意这里没有必要合并相邻的intervals

Time O(logN)

Space O(N)

Runtime: 30 ms, faster than 75.04% of Java online submissions for My Calendar I.

Memory Usage: 54.6 MB, less than 51.82% of Java online submissions for My Calendar I.

class MyCalendar {

    TreeMap<Integer, Integer> events;

    public MyCalendar() {

        this.events = new TreeMap<>();

    }

    

    //  [19,25)[25,32)[33,41)[47,50)

    

    public boolean book(int start, int end) {

        // [start, end)

        Integer prevStart = events.lowerKey(end);

        if (prevStart != null && events.get(prevStart) > start) {

            return false;

        }

        // [prevStart, prevEnd) [start, end)

        events.put(start, end);

        return true;

    }

}

一刷
Version #1 TreeMap

Time O(logn) for each book() call

94.57 %
class MyCalendar {

    TreeMap<Integer, Integer> treeMap;
public MyCalendar() {
// key-start, value-end
this.treeMap = new TreeMap<>();
}

public boolean book(int start, int end) {
// [start, end)    [start, end)
// There should be two constraints
// 1.any event happens after current start time, should start after end time
// 2.any event happens before current start time, should end before start time
Map.Entry<Integer, Integer> prev = treeMap.floorEntry(start);
if (prev != null && prev.getValue() > start) return false;
Map.Entry<Integer, Integer> next = treeMap.ceilingEntry(start);
if (next != null && next.getKey() < end) return false;
treeMap.put(start, end);
return true;
}
}