0200. Number of Islands

https://leetcode.com/problems/number-of-islands

Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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:

**Input:** grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
**Output:** 1

Example 2:

**Input:** grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
**Output:** 3

Constraints:

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 300

• grid[i][j] is '0' or '1'.

ac1：DFS

DFS for this problem is way cleaner and faster.

key:

• dfs sink islands: grid[r][c] = '0';

class Solution {

    public int numIslands(char[][] grid) {
        if (grid == null) return 0;
        int gr = grid.length;
        if (gr == 0) return 0;
        int gc = grid[0].length;

        int islands = 0;
        for (int i = 0; i < gr; i++) {
            for (int j = 0; j < gc; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    islands++;
                }
            }
        }

        return islands;
    }

    private void dfs(char[][] grid, int r, int c) {
        int gr = grid.length;
        int gc = grid[0].length;

        if (r < 0 || c < 0 || r >= gr || c >= gc || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r+1, c);
        dfs(grid, r-1, c);
        dfs(grid, r, c+1);
        dfs(grid, r, c-1);
    }
}

ac2: BFS

here no for loop is needed because you don't care about layer.

class Solution {

    public int numIslands(char[][] grid) {
        if (grid == null) return 0;
        int gr = grid.length;
        if (gr == 0) return 0;
        int gc = grid[0].length;

        int islands = 0;
        Queue<int[]> q = new LinkedList<int[]>();
        for (int i = 0; i < gr; i++) {
            for (int j = 0; j < gc; j++) {
                if (grid[i][j] == '1') {
                    islands++;
                    q.offer(new int[]{i,j});
                    while (!q.isEmpty()) {
                        int[] head = q.poll();
                        int r = head[0];
                        int c = head[1];
                        if (r < 0 || c < 0 || r >= gr || c >= gc || grid[r][c] == '0') {
                            continue;
                        }
                        grid[r][c] = '0';
                        q.offer(new int[]{r+1,c});
                        q.offer(new int[]{r-1,c});
                        q.offer(new int[]{r,c+1});
                        q.offer(new int[]{r,c-1});
                    }
                }
            }
        }

        return islands;
    }
}

ac3: Union find

class Solution {
    public int numIslands(char[][] grid) {
        // edge cases
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int row = grid.length;
        int col = grid[0].length;

        UnionFind uf = new UnionFind(grid);

        // union all cells
        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == '1') {
                    int curr = col * r + c;
                    // left
                    if (c > 0 && grid[r][c-1] == '1') {
                        uf.union(curr, curr - 1);
                    }
                    // up
                    if (r > 0 && grid[r-1][c] == '1') {
                        uf.union(curr, curr - col);
                    }
                }
            }
        }


        return uf.count;
    }

    class UnionFind {
        int[] father;
        int count;
        public UnionFind(char[][] grid){
            int row = grid.length;
            int col = grid[0].length;
            father = new int[row*col];

            for (int r = 0; r < row; r++) {
                for (int c = 0; c < col; c++) {
                    if (grid[r][c] == '1') {
                        int curr = col * r + c;
                        father[curr] = curr;
                        count++;
                    }
                }
            }
        }

        public void union(int a, int b) {
            int aFather = find(a);
            int bFather = find(b);
            if (aFather == bFather) return;
            father[aFather] = bFather;
            count--;
        }

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