827. Making A Large Island

Version #1 Union Find
题不难 胜在难写
有一个tricky的地方
当前grid为0，要想办法和它周围四个方向Union
此时需要 判断这个这四个方向的root是否已经是相连的
就用一个visited来防止重复加size


Time O(mn)
Space O(mn)

98.99
class Solution {
    private int[] id;
    private int[] size;
    private int[] dx = new int[]{1, 0, -1, 0};
    private int[] dy = new int[]{0, -1, 0, 1};

    private int max;
    public int largestIsland(int[][] grid) {
        if (grid == null) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        // y * cols + x -> y - 1
        id = new int[rows * cols];
        size = new int[rows * cols];
        for (int i = 0; i < rows * cols; i++) {
            id[i] = i;
            size[i] = 1;
        }
        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < cols; x++) {
                if (grid[y][x] != 0) {
                    max = Math.max(max, 1);
                    if (x > 0 && grid[y][x - 1] != 0) {
                        union(y * cols + x, y * cols + (x - 1));
                    }
                    if (y > 0 && grid[y - 1][x] != 0) {
                        union(y * cols + x, (y - 1) * cols + x);
                    } 
                }
               
            }
        }
        for (int y = 0; y < rows; y++) {
            for (int x = 0; x < cols; x++) {
                if (grid[y][x] == 0) {
                    Set<Integer> visited = new HashSet<>();
                    int currSize = 1;
                    for (int i = 0; i < 4; i++) {
                        if (x + dx[i] >= 0 && x + dx[i] < cols && y + dy[i] >= 0 && y + dy[i] < rows
                           && grid[y + dy[i]][x + dx[i]] != 0) {
                            int rootId = root((y + dy[i]) * cols + x + dx[i]);
                            if (!visited.contains(rootId)) {
                                currSize += size[rootId];
                                visited.add(rootId);
                            }
                        }
                       
                    }
                    max = Math.max(max, currSize);
                }
            }
        }
        return max;
    }
   
    private int root(int i) {
        while (id[i] != i) {
            id[i] = id[id[i]];
            i = id[i];
        }
        return i;
    }
   
    private 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];
            max = Math.max(max, size[rootQ]);
        } else {
            id[rootQ] = rootP;
            size[rootP] += size[rootQ];
            max = Math.max(max, size[rootP]);
        }
    }
}

二刷

感觉之前复杂度写错了，应该是O(mnlog(2)mn), 因为bisides traversing graph, the union find can take extra log(2)mn time.