Description

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

Example 2:

11000
11000
00100
00011

Answer: 3

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

Solution

DFS, time O(m * n), space worst case O(m * n)

Space complexity : worst case O(M×N) in case that the grid map is filled with lands where DFS goes by M×N deep.

class Solution {
    public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int numIslands(char[][] grid) {
        int islands = 0;
        
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (dfsExpand(grid, i, j)) {
                    ++islands;
                }
            }
        }
        
        return islands;
    }
    
    public boolean dfsExpand(char[][] grid, int i, int j) {
        if (!isValid(grid, i, j) || grid[i][j] != '1') {
            return false;
        }
        
        grid[i][j] = '2';   // mark as visited
        for (int[] direction : DIRECTIONS) {
            dfsExpand(grid, i + direction[0], j + direction[1]);
        }
        
        return true;
    }
    
    public boolean isValid(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}

BFS, time O(m * n), space worst case O(min(M, N))

Space complexity : O(min(M,N)) because in worst case where the grid is filled with lands, the size of queue can grow up to min(M,N).

class Solution {
    public static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    
    public int numIslands(char[][] grid) {
        int islands = 0;
        
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                if (bfsExpand(grid, i, j)) {
                    ++islands;
                }
            }
        }
        
        return islands;
    }
    
    public boolean bfsExpand(char[][] grid, int i, int j) {
        if (!isValid(grid, i, j) || grid[i][j] != '1') {
            return false;
        }
        
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        grid[i][j] = '2';   // mark as visited       
        
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            for (int[] direction : DIRECTIONS) {
                int x = pos[0] + direction[0];
                int y = pos[1] + direction[1];
                
                if (isValid(grid, x, y) && grid[x][y] == '1') {
                    queue.offer(new int[] {x, y});
                    grid[x][y] = '2';
                }
            }
        }
        
        return true;
    }
    
    public boolean isValid(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}

Union-find, time O(m * n), space O(m * n)

定義一個UnionFind class，里面的count成員表示由'1'組成的set的個數(shù)，初始化為grid中'1'的數(shù)量。然后遍歷grid，分別向右和向下做union find，如果成功則count--，最終count即為所求。

注意這里擴張方向上的選擇，由于在上面的dfs算法中，每次擴張都需要竭盡全力夠到最廣最深的地方，所以需要向上下左右四個方向擴展；但是在union-find算法中，只需要保證每個節(jié)點都被union-find過即可，所以只需向右和向下擴張就可以了。

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 unionFind = new UnionFind(grid);
        
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == '0') {
                    continue;
                }
                // try union find
                if (i < m - 1 && grid[i + 1][j] != '0') {
                    unionFind.union(i * n + j, (i + 1) * n + j);
                }
                
                if (j < n - 1 && grid[i][j + 1] != '0') {
                    unionFind.union(i * n + j, i * n + j + 1);
                }
            }
        }
        
        return unionFind.count;
    }
    
    class UnionFind {
        int count;      // set of 1s count
        int[] parent;
        
        public UnionFind(char[][] grid) {
            for (char[] row : grid) {
                for (char c : row) {
                    if (c != '0') {
                        ++count;
                    }
                }
            }
            
            parent = new int[grid.length * grid[0].length];
            Arrays.fill(parent, -1);
        }
        
        public int find(int i) {
            if (parent[i] == -1) {
                return i;
            }
            parent[i] = find(parent[i]);
            return parent[i];
        }
        
        public void union(int i, int j) {
            int iset = find(i);
            int jset = find(j);
            if (iset == jset) {
                return;
            }
            parent[iset] = jset;
            --count;
        }
    }
}

或者這樣寫：

class Solution {
    public static final int[][] DIRECTIONS = {{1, 0}, {0, 1}};
    
    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;
        int[] parent = new int[m * n];
        
        for (int i = 0; i < parent.length; ++i) {
            parent[i] = i;
        }
        
        int islands = m * n;        
       
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] != '1') {
                    --islands;
                    continue;
                }
                
                for (int[] direction : DIRECTIONS) {
                    int x = i + direction[0];
                    int y = j + direction[1];
                    
                    if (isValid(grid, x, y) && grid[x][y] == '1') {
                        int iset = find(parent, getIndex(i, j, n));
                        int xset = find(parent, getIndex(x, y, n));
                        
                        if (iset != xset) {
                            union(parent, iset, xset);
                            --islands;
                        }
                    }
                }
            }
        }
        
        return islands;
    }
    
    public int getIndex(int i, int j, int cols) {
        return i * cols + j;
    }
    
    public int find(int[] parent, int x) {
        if (parent[x] != x) {
            parent[x] = find(parent, parent[x]);
        }
        return parent[x];
    }
    
    public void union(int[] parent, int xset, int yset) {
        parent[xset] = parent[yset];
    }
    
    public boolean isValid(char[][] grid, int i, int j) {
        return i >= 0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
}