Count Number of Islands

The Problem

Given a 2D binary grid/matrix which represents a map of 1s (land) and 0s (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.

Examples:

[
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
] // output: 1

[
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
] // output: 3

Solutioning

Let's deliberate how we might solve this problem as a computer program.

We know that we must visit each cell to determine which cells are land and which are water. We can do so by traversing the grid from its top-left to its bottom-right.

Once we arrive at a land cell, then we'd like to increment our island counter. Now, if we stopped here, we would face an issue where every single land cell is considered its own island. In order to fix this, we must keep track of our visited cells and perform a depth-first traversal where we mark all contiguous land cells as visited. This way, when we arrive at a previously visited cell via our linear matrix traversal, we know to simply move on!

Time Complexity: $O(m*n)$

Implementation

Let's implement this solution with TypeScript.

For setup, we need to set up some data structures. We need a 2D grid to mark cells as visited. We need a count variable to keep track of our island count.

Once setup is finished, then we need to write the linear traversal of the grid. We can utilize two for-loops for this. We also need to peform a depth-first traversal. We can set up a new helper function for this. Depth-first search utilizes a stack, so we can simply use recursion—this uses the callstack as an implicit stack.

function numIslands(grid) {
  const visited = new Array(grid.length)
    .fill(null)
    .map(() => new Array(grid.length).fill(false));
  let count = 0;

  // linearaly traverse grid top-left to bottom-right
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (visited[i][j] === true) {
        continue;
      }

      // if node is land, then increment count and mark all connected 1's as visited via DFS
      if (grid[i][j] === "1") {
        count++;
        dfsWalk(grid, visited, { row: i, col: j });
      }
    }
  }

  return count;
}

function dfsWalk(grid, visited, pos) {
  if (
    pos.row < 0 ||
    pos.row >= grid.length ||
    pos.col < 0 ||
    pos.col >= grid[pos.row].length
  ) {
    return;
  }

  if (visited[pos.row][pos.col] === true || grid[pos.row][pos.col] === "0") {
    return;
  }

  visited[pos.row][pos.col] = true;

  const up = { ...pos, row: pos.row - 1 };
  const down = { ...pos, row: pos.row + 1 };
  const left = { ...pos, col: pos.col - 1 };
  const right = { ...pos, col: pos.col + 1 };

  dfsWalk(grid, visited, up);
  dfsWalk(grid, visited, down);
  dfsWalk(grid, visited, left);
  dfsWalk(grid, visited, right);
}