[LeetCode] 200. Number of Islands

Posted on | In

Problem

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:

1
2
3
4
5
6
7
Input:
11110
11010
11000
00000

Output: 1

Example 2:

1
2
3
4
5
6
7
Input:
11000
11000
00100
00011

Output: 3

Explanation 1

  1. We can use DFS and a visited array to solve this problem.

  2. Loop through every element in the two dimensional array, if the element is 1 and it’s not visited, then we start our flood fill dfs helper function to update the visited array. Then, we increase our result counter by 1.

  3. At the end, we return our result.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    void helper(char[][] grid, boolean[][] visited, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) {
            return;
        }
        if (grid[r][c] == '0' || visited[r][c]) {
            return;
        }
        visited[r][c] = true;
        helper(grid, visited, r-1, c);
        helper(grid, visited, r+1, c);
        helper(grid, visited, r, c-1);
        helper(grid, visited, r, c+1);
    }

    public int numIslands(char[][] grid) {
        int res = 0;
        if (grid == null || grid.length == 0) {
            return res;
        }
        int row = grid.length, col = grid[0].length;
        boolean[][] visited = new boolean[row][col];

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    res += 1;
                    helper(grid, visited, r, c);
                }
            }
        }

        return res;
    }
}

Explanation 2

  1. We can also use BFS to solve this problem. In order to use BFS, we need a queue. We still need to iterate the 2d grid. When the current grid element is 1, we increase the result by 1 and mark its coordinate in the visited 2d array to true. Then, we push the current grid element’s total value (curRow * numOfColumn + curCol) into the queue.

  2. While the queue is not empty, we pop out the total value and use the total value to get back the curRow and curCol. Then we we iterate 4 times, each time we get its updated surrounding position (left, top, right, bottom). If the updated surrounding position is inside the grid and it’s not visited and its value is 1, then we mark the updated position as visited, and then push it to the queue. Repeat until the queue is empty.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int numIslands(char[][] grid) {
        int res = 0;
        if (grid == null || grid.length == 0) {
            return res;
        }
        int row = grid.length, col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        Queue<Integer> queue = new LinkedList<>();
        int[] dirX = new int[] {-1, 0, 1, 0};
        int[] dirY = new int[] {0, 1, 0, -1};

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == '1' && !visited[r][c]) {
                    res += 1;
                    visited[r][c] = true;
                    queue.offer(r * col + c);
                    while (!queue.isEmpty()) {
                        int pNum = queue.poll();
                        int pRow = pNum / col, pCol = pNum % col;
                        for (int i = 0; i < 4; i++) {
                            int x = pRow + dirX[i];
                            int y = pCol + dirY[i];
                            if (x < 0 || x >= row || y < 0 || y >= col) {
                                continue;
                            }
                            if (grid[x][y] == '0' || visited[x][y]) {
                                continue;
                            }
                            visited[x][y] = true;
                            queue.offer(x * col + y);
                        }
                    }
                }
            }
        }

        return res;
    }
}

Explanation 3

  1. This is a disjoin set or union find problem.

  2. First, we creat an array parent[] that has size row * col, and a variable cnt. Loop through every element, if the current element is 1, then we increase cnt and update parent[i] = i.

  3. Next, we loop through every element again, this time if the current element is 1, then we check its 4 neighbor directions. If its neighbor is not out of bound and its element is also 1, then we find the current element’s parent and its neighbor’s parent. If both parent is not the same, we union both parents and subract cnt by 1.

  4. At the end, we return cnt as the result.

Solution 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
    int findParent(int parent[], int p) {
        while (p != parent[p]) {
            p = parent[parent[p]];
        }
        return p;
    }

    public int numIslands(char[][] grid) {
        int cnt = 0;
        if (grid == null || grid.length == 0 || grid[0].length == 0) return cnt;
        int row = grid.length;
        int col = grid[0].length;
        int[] parent = new int[row * col];
        int[] dx = {-1, 0, 1, 0};
        int[] dy = {0, 1, 0, -1};

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

        for (int r = 0; r < row; r++) {
            for (int c = 0; c < col; c++) {
                if (grid[r][c] == '1') {
                    for (int i = 0; i < 4; i++) {
                        int x = r + dx[i];
                        int y = c + dy[i];
                        if (x >= 0 && x < row && y >= 0 && y < col && grid[x][y] == '1') {
                            int curParent = findParent(parent, r * col + c);
                            int dirParent = findParent(parent, x * col + y);
                            if (curParent != dirParent) {
                                parent[curParent] = dirParent;
                                cnt -= 1;
                            }
                        }
                    }
                }
            }
        }

        return cnt;
    }
}