Number of islands

Medium TimeO(n·m) SpaceO(n·m)

A grid holds 1 for land and 0 for water, and an island is a group of 1s joined horizontally or vertically — land touching only at a corner counts as separate. Given grid, return how many islands it contains. A grid of all water has none.

Examples

Example 1

Input
grid = [[1, 1, 0], [0, 1, 0], [0, 0, 1]]
Output
2
Three 1s joined into one island, and the corner 1 touching only diagonally is a second.

Example 2

Input
grid = [[0, 0], [0, 0]]
Output
0
All water, so there is no island to count.

The Code

function numIslands(grid) {
  let count = 0;
  function sink(r, c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length) return;
    if (grid[r][c] !== 1) return;
    grid[r][c] = 0;
    sink(r + 1, c);
    sink(r - 1, c);
    sink(r, c + 1);
    sink(r, c - 1);
  }
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === 1) {
        count++;
        sink(r, c);
      }
    }
  }
  return count;
}
numIslands([[1, 1, 0], [0, 1, 0], [0, 0, 1]]);
Done

The first 27 calls, of 35. This one does not fit on a page.

Step through numIslands([[1, 1, 0], [0, 1, 0], [0, 0, 1]]) call by call

More like this

All matrices & grids examples (7) →