Skip to content

200. Number of Islands

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

Intuition

Traverse the grid array using DFS. Check every entry in the array and use count to store the number of island.

Approach

When we visit a cell in the grid, we set its value as '0', as when we encounter the cell with '0', we simply ignore it and visit next cell. The invalid case for DFS is

  • row < 0 || row >= grid.length
  • col < 0 || col >= grid[0].length
  • grid[row][col] != '1'

Complexity

  • Time complexity: \(O(R \times C)\), in the worst case, we need to visit every cell in the grid.
  • Space complexity: \(O(R \times C)\), in the worst case, all cells in the grid are land cells, thus DFS will be called \(R\times C\) times

Code

 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
class Solution {
    public int numIslands(char[][] grid) {
        int row = grid.length;
        int col = grid[0].length;
        boolean isCheck[][] = new boolean[row][col];
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }

        return count;
    }

    private void dfs(char[][] grid, int row, int col) {
        if (row < 0 || row >= grid.length || 
            col < 0 || col >= grid[0].length || 
            grid[row][col] != '1') {
            return ;
        }
        grid[row][col] = '0';
        dfs(grid, row + 1, col);
        dfs(grid, row, col + 1);
        dfs(grid, row - 1, col);
        dfs(grid, row, col - 1);
    }
}