Number of Islands: Exploring Grid-Based Graph Algorithms

The "Number of Islands" problem is a classic algorithmic challenge that involves counting the number of distinct islands in a 2D grid.

Problem Statement

Given a 2D grid map of '1's (land) and '0's (water), determine the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Example

Consider a grid map: 11110 11010 11000 00000

The number of islands in this grid is 1.

Depth-First Search Solution

function numIslands(grid) {
  if (!grid || !grid.length) return 0;

  let numIslands = 0;

  function dfs(row, col) {
    if (
      row < 0 ||
      row >= grid.length ||
      col < 0 ||
      col >= grid[0].length ||
      grid[row][col] === "0"
    ) {
      return;
    }
    grid[row][col] = "0"; // Mark as visited
    dfs(row + 1, col); // Down
    dfs(row - 1, col); // Up
    dfs(row, col + 1); // Right
    dfs(row, col - 1); // Left
  }

  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === "1") {
        numIslands++;
        dfs(i, j);
      }
    }
  }

  return numIslands;
}

Breaking Down the Solution

• DFS Traversal: Use depth-first search to explore each land cell and mark it as visited by setting it to '0'.
• Count Islands: Iterate over each cell in the grid. When a land cell ('1') is found, increment the island count and use DFS to mark the entire island.
• Handle Edge Cases: Check for invalid indices and water cells ('0') in the DFS function to prevent out-of-bounds errors and unnecessary exploration.

Time Complexity

The time complexity is O(M x N), where M is the number of rows and N is the number of columns in the grid. This is because, in the worst case, the algorithm needs to visit every cell in the grid once. The DFS traversal ensures that each cell is visited only once, so the total number of operations is proportional to the total number of cells.

Space Complexity

The space complexity is also O(M x N) in the worst case. This is due to the recursive nature of DFS, which could potentially have a call stack with a depth equal to the number of cells in the grid in the worst case (e.g., a grid that is entirely land).

Can It Be Improved?

• Space Complexity: One way to improve the space complexity is to use an iterative DFS approach with an explicit stack instead of recursion. This can help in scenarios where the grid is large, and recursion might lead to a stack overflow.
• Alternative Approach - BFS: Another way to traverse the grid is by using breadth-first search (BFS). While BFS does not improve the worst-case time complexity, it can be more practical in terms of space complexity, especially if the grid forms one large island, as BFS will keep the queue size minimal relative to the size of the island being explored.
• Union-Find (Disjoint Set): An alternative approach is to use the Union-Find algorithm. This can be particularly efficient if there are many queries on the grid after some modifications (e.g., adding or removing land). However, the implementation complexity is higher compared to DFS or BFS.

In practice, the choice of algorithm might depend on the specific characteristics of the input data and the constraints of the problem (e.g., grid size, number of islands, likelihood of stack overflow, etc.).

Conclusion

The Number of Islands problem is an essential application of depth-first search in a grid-based context. It highlights how grid traversal can be used to solve complex problems in areas such as mapping, geographical information systems, and computer graphics.