[LeetCode] – Number of Islands Solution

93

In this problem, we are given a 2D grid consisting of ‘1’s (land) and ‘0’s (water). Our task is to count the number of islands. An island consists of a group of connected ‘1’s surrounded by water (‘0’s). The connection can be in four directions—up, down, left, or right.

The most important aspect of this problem is to ensure that we count each piece of land only once. To do this, we need an efficient way to traverse the grid and mark visited lands.

Input:
grid = [
  ['1', '1', '0', '0', '0'],
  ['1', '1', '0', '0', '0'],
  ['0', '0', '1', '0', '0'],
  ['0', '0', '0', '1', '1']
]
Output: 3
Explanation:
- The first two rows form one island.
- The single '1' in the third row is another island.
- The last two '1's in the fourth row form the third island.

Brute Force Approach

A naive approach would be to iterate over every cell in the grid and try to count islands while keeping track of visited cells using an auxiliary data structure. This method would involve unnecessary re-traversals, making it inefficient.

Steps:

1. Initialize a variable count to store the number of islands.
2. Create a separate visited matrix to track visited cells.
3. Iterate through every cell in the grid:
   • If a cell contains ‘1’ and hasn’t been visited, perform a traversal (BFS or DFS) to mark all connected land as visited.
   • Increment the island count.
4. Return count as the number of islands.

Optimized Approach

Instead of maintaining an extra visited array, we can modify the grid itself by marking visited land cells as ‘0’ (water). This reduces space complexity while ensuring we don’t count the same island multiple times.

Steps:

1. Initialize count = 0 to track the number of islands.
2. Iterate through the grid:
   • If a cell is ‘1’, trigger a Depth-First Search (DFS) to mark all connected land as visited.
   • Increment count after each DFS traversal.
3. The DFS function should:
   • Check if the cell is out of bounds or already water (‘0’). If so, return.
   • Mark the current cell as ‘0’ to avoid re-visiting.
   • Recursively visit its neighbors (up, down, left, right).
4. Once the entire grid is traversed, return count.

Code:

int numIslands(char[][] grid) {
    if (grid == null || grid.length == 0 || grid[0].length == 0) {
      return 0;
    }

    int count = 0;

    for (int i = 0; i < grid.length; i++)
      for (int j = 0; j < grid[0].length; j++)
        if (grid[i][j] == '1') {
          dfs(grid, i, j);
          count++;
        }

    return count;
}

private void dfs(char[][] grid, int i, int j) {
    if (i < 0 || i >= grid.length
        || j < 0 || j >= grid[0].length
        || grid[i][j] == '0') {
      return;
    }

    grid[i][j] = '0'; // Mark the cell as visited

    // Explore all four directions
    dfs(grid, i + 1, j);
    dfs(grid, i - 1, j);
    dfs(grid, i, j + 1);
    dfs(grid, i, j - 1);
}
Code language: Java (java)

• Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. Each cell is visited once and its adjacent cells are checked at most once.
• Space Complexity: O(n * m) in the worst case due to recursion stack depth (if the grid is entirely land). However, this is more space-efficient than using an auxiliary visited array.

Video Explanation: