200. Number of Islands

LeetCode

Union-Find

In this solution, we use Weighted Quick-Union to count the number of connected domain, which is an implementation of Union-Find algorithm in Robert Sedgewick and Kevin Wayne’s Algorithm.

Note that we should minus the number of ‘0’ islands, cause the algorithm also considers them as independent connected domains.

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int row = grid.length;
        int column = grid[0].length;
        UnionFind uf = new UnionFind(row * column);
        int zeroCounter = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < column; j++) {
                if (grid[i][j] == '0') {
                    zeroCounter++;
                    continue;
                }
                int curr = i * column + j;
                int target;
                if (i > 0 && grid[i - 1][j] == '1') {
                    target = curr - column;
                    uf.union(curr, target);
                }
                if (i < row - 1 && grid[i + 1][j] == '1') {
                    target = curr + column;
                    uf.union(curr, target);
                }
                if (j > 0 && grid[i][j - 1] == '1') {
                    target = curr - 1;
                    uf.union(curr, target);
                }
                if (j < column - 1 && grid[i][j + 1] == '1') {
                    target = curr + 1;
                    uf.union(curr, target);
                }
            }
        }
        // remove '0' counting
        return uf.count() - zeroCounter;
    }

    private static class UnionFind {
        private int[] id;
        private int[] sz;
        private int count;

        public UnionFind(int n) {
            this.id = new int[n];
            this.sz = new int[n];
            for (int i = 0; i < n; i++) {
                id[i] = i;
                sz[i] = 1;
            }
            this.count = n;
        }

        public void union(int p, int q) {
            int i = find(p);
            int j = find(q);
            if (i == j) {
                return;
            }
            // link small tree to large tree
            if (sz[i] < sz[j]) {
                id[i] = j;
                sz[j] += sz[i];
            } else {
                id[j] = i;
                sz[i] += sz[j];
            }
            count--;
        }

        // find the root of p
        public int find(int p) {
            while (p != id[p]) {
                p = id[p];
            }
            return p;
        }

        public boolean connected(int p, int q) {
            return find(p) == find(q);
        }

        public int count() {
            return count;
        }
    }
}

DFS

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0 || grid[0].length == 0) {
            return 0;
        }
        int m = grid.length;
        int n = grid[0].length;
        int islands = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == '1') {
                    // for all UNVISITED land, do a dfs
                    dfs(i, j, grid);
                    islands++;
                }
            }
        }
        return islands;
    }

    private void dfs(int i, int j, char[][] grid) {
        // if (i, j) is out of bounds or (i, j) is not a land, return
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] != '1') {
            return;
        }
        // mark as visited
        grid[i][j] = '0';
        dfs(i - 1, j, grid);
        dfs(i + 1, j, grid);
        dfs(i, j - 1, grid);
        dfs(i, j + 1, grid);
    }
}