Union Find

number of island

note that: we need to calculate how many island area it originally have.

class solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int m = grid.length;
        int n = grid[0].length;

        UnionFind uf = new UnionFind(m * n);

        // count how many islands it originally have 
        // can add to the constructor of the unionfind 
        int num = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') num++;
            }
        }
        uf.set_count(num);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '1') {
                    for (int[] pair : pairs) {
                        int x = pair[0] + i;
                        int y = pair[1] + j;

                        if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1') {
                            uf.connect(i * n + j, x * n + y);
                        }
                    }
                }
            }
        }
        return uf.query();
    }

    private final int[] pairs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private class UnionFind{
        public int[] father;
        public int count;

        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; ++i) {
                father[i] = i;
            }
        }

        public void connect(int a, int b) {
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                father[root_a] = root_b;
                count--;
            }
        }

        public int find(int x) {
            if (x == father[x]) {
                return x;
            }
            return father[x] = find(father[x]);
        }

        public int query() {
            return count;
        }

        public void set_count(int n) {
            count = n;
        }
    }
}

number of islands 2

note: use a int array to record the number of the islands every time we change one area from water into a land. Should use one auxiliary 2D array to record the change. Another thing is that we need to transform the 2D matrix into one array.

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList<>();
        if (positions == null || positions.length == 0 || positions[0].length == 0) return res;

        UnionFind uf = new UnionFind(m * n);
        int[][] arr = new int[m][n];

        for (int[] pos : positions) {
            int x = pos[0];
            int y = pos[1];

            arr[x][y] = 1;
            uf.set_count(uf.query() + 1);

            for (int[] pair : pairs) {
                int xIndex = pair[0] + x;
                int yIndex = pair[1] + y;

                if (xIndex >= 0 && xIndex < m && yIndex >= 0 && yIndex < n && arr[xIndex][yIndex] == 1) {
                    uf.connect(x * n + y, xIndex * n + yIndex);
                }
            }
            res.add(uf.query());
        }
        return res;
    }

    private final int[][] pairs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

    private class UnionFind{
        public int[] father;
        public int count;

        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; ++i) {
                father[i] = i;
            }
        }
        public void connect(int a, int b) {
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                father[root_a] = root_b;
                count--;
            }
        }
        public int find(int x) {
            if (x == father[x]) {
                return x;
            }
            return father[x] = find(father[x]);
        }
        public int query() {
            return count;
        }
        public void set_count(int n) {
            count = n;
        }
    }
}

surrounded region

note that: the outer round of X will be connected to the root node with the array index of (m * n). So next time, we only need to change the X whose root index is not m * n.

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) return;

        int m = board.length;
        int n = board[0].length;

        UnionFind uf = new UnionFind(m * n + 1);

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O' && (i == 0 || j == 0 || i == m - 1 || j == n - 1)) {
                    uf.connect(i * n + j, m * n);
                } else if (board[i][j] == 'O') {
                    for (int[] pair : pairs) {
                        int x = pair[0] + i;
                        int y = pair[1] + j;
                        if (x >= 0 && y >= 0 && x < m && y < n && board[x][y] == 'O') {
                            uf.connect(i * n + j, x * n + y);
                        }
                    }
                }
            }
        }

        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (board[i][j] == 'O' && uf.find(i * n + j) != uf.find(m * n)) {
                    board[i][j] = 'X';
                }
            }
        }
    }

    private final int[][] pairs = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

    private class UnionFind{

        public int[] father;
        public int count;

        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }
        public void connect(int a, int b) {
            int root_a = find(a);
            int root_b = find(b);
            if (root_a != root_b) {
                father[root_a] = root_b;
                count--;
            } 
        }
        public int find(int x) {
            if (x == father[x]) {
                return x;
            }
            return father[x] = find(father[x]);
        }
    }
}