Number of Islands

The problem

You are given grid, a rectangle of cells in which 1 is land and 0 is water. An island is a group of one or more land cells joined side by side: from any of its cells you can walk to any other by stepping up, down, left or right over land. Cells that touch only at a corner are not joined. Return the number of islands. The grid may be empty, with no rows or with rows that hold no cells; then return 0.

What to write

function solve(grid: number[][]): number

Input
grid = [[1,1,0],[0,1,0],[0,0,1]]

Output
2

Input
grid = [[0,0],[0,0]]

Output
0

Constraints

Rectangular grid up to 50 × 50 of 0 or 1; empty grids allowed.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The grid has at most 50 × 50 = 2,500 cells, so you can afford to look at every cell, and even to come back to a cell a few times. Only up, down, left and right join land: touching at a corner does not. An empty grid has no islands.

2. Hint 2: Ask a smaller question

   In the first example the top-left island has three cells, and a scan that goes row by row meets all three. If every 1 you meet added one to the count, the answer would be 4, not 2. What could you do on meeting the first cell of an island, so that its other cells are not counted later?

3. Hint 3: Name the pattern

   An island is a group of cells in which you can walk from any cell to any other: a connected component. You must count them. Scan the cells: each time you find land that is not marked yet, walk the whole island and mark it. This walk is called a flood fill, and the pattern is grid connected components. Read the lesson on grid connected components.

4. Hint 4: State the invariant

   Every cell that still holds 1 belongs to an island that has not been counted yet. When an island is counted, all of its cells are turned to 0 before the scan moves on, so each island is counted once, at the first of its cells the scan reaches.

5. Hint 5: Sketch the pseudocode

   count = 0. For each cell, row by row: if it holds 1, add 1 to count, write 0 into it and put it on a list. Until the list is empty: take a cell off, and for each of its four neighbors inside the grid that holds 1, write 0 there and add it to the list. Return count.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Scan every cell. When land is found, count a component and flood-fill its orthogonal neighbors, marking them visited.

The slow way

Counting every land cell counts cells, not islands: the first example would give 4. A tempting repair is to count only the land cells with no land directly above them and none directly to their left. It is fast but wrong. In a grid with rows 0 1 and 1 1 the three land cells are one island, yet two of them pass that test.

The insight

You do not have to recognize an island by its shape. The first time the scan touches an island, walk over all of it and sink it: write 0 into every one of its cells. After that, any 1 the scan meets must belong to an island that has not been counted, so every 1 the scan finds is exactly one new island.

Step by step

1. Start with no islands counted. Islands are added to the count as the scan finds them. A grid with no cells never reaches the counting line, so the count is still 0 when it is returned.
2. Scan every cell, skipping water and land that is already sunk. An island can begin anywhere, so every cell is looked at. A cell that holds 0 is water, or land of an island that was already counted. Neither can start a new island.
3. Land that is still 1 starts a new island: count it. Every island counted so far was sunk completely, so a cell that still holds 1 cannot be part of any of them. It is the first cell the scan reaches of a new island.
4. Sink that cell and put it on a list of cells to spread from. The list holds cells that are sunk but whose neighbors have not been looked at yet. Starting it with this one cell is what lets the rest of the island be found.
5. While cells are waiting, take one and look at its four neighbors. The rest of the island can only be reached through neighbors: up, down, left and right. The code takes the newest cell first, but any order reaches the same cells.
6. Sink each neighbor that is land and add it to the list. A land neighbor belongs to the same island. It is sunk at the moment it joins the list, so no cell can join twice, and its own neighbors get their turn later.
7. Return the number of islands counted. The scan has passed every cell, and each island raised the count exactly once, at the first of its cells the scan reached.

The same numbered steps are the comments in each solution.

function solve(grid) {
  // 1. Start with no islands counted
  let count = 0;
  // 2. Scan every cell, skipping water and land that is already sunk
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[r].length; c++) {
      if (grid[r][c] !== 1) continue;
      // 3. Land that is still 1 starts a new island: count it
      count++;
      // 4. Sink that cell and put it on a list of cells to spread from
      const stack = [[r, c]];
      grid[r][c] = 0;
      // 5. While cells are waiting, take one and look at its four neighbors
      while (stack.length) {
        const [a, b] = stack.pop();
        for (const [x, y] of [
          [a - 1, b],
          [a + 1, b],
          [a, b - 1],
          [a, b + 1],
        ])
          // 6. Sink each neighbor that is land and add it to the list
          // Outside the grid, grid[x]?.[y] is undefined instead of an error,
          // so a neighbor that does not exist is never taken for land.
          if (grid[x]?.[y] === 1) {
            grid[x][y] = 0;
            stack.push([x, y]);
          }
      }
    }
  // 7. Return the number of islands counted
  return count;
}

function solve(grid: number[][]): number {
  // 1. Start with no islands counted
  let count = 0;
  // 2. Scan every cell, skipping water and land that is already sunk
  for (let r = 0; r < grid.length; r++)
    for (let c = 0; c < grid[r].length; c++) {
      if (grid[r][c] !== 1) continue;
      // 3. Land that is still 1 starts a new island: count it
      count++;
      // 4. Sink that cell and put it on a list of cells to spread from
      const stack = [[r, c]];
      grid[r][c] = 0;
      // 5. While cells are waiting, take one and look at its four neighbors
      while (stack.length) {
        const [a, b] = stack.pop()!;
        for (const [x, y] of [
          [a - 1, b],
          [a + 1, b],
          [a, b - 1],
          [a, b + 1],
        ])
          // 6. Sink each neighbor that is land and add it to the list
          // Outside the grid, grid[x]?.[y] is undefined instead of an error,
          // so a neighbor that does not exist is never taken for land.
          if (grid[x]?.[y] === 1) {
            grid[x][y] = 0;
            stack.push([x, y]);
          }
      }
    }
  // 7. Return the number of islands counted
  return count;
}

def solve(grid):
    # 1. Start with no islands counted
    count = 0
    # 2. Scan every cell, skipping water and land that is already sunk
    rows = len(grid)
    # A grid with no rows has no first row to measure, so it gets 0 columns.
    cols = len(grid[0]) if grid else 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != 1:
                continue
            # 3. Land that is still 1 starts a new island: count it
            count += 1
            # 4. Sink that cell and put it on a list of cells to spread from
            stack = [(r, c)]
            grid[r][c] = 0
            # 5. While cells are waiting, take one and look at its four neighbors
            while stack:
                x, y = stack.pop()
                for nx, ny in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)):
                    # 6. Sink each neighbor that is land and add it to the list
                    # A negative index would read from the far edge of the grid,
                    # so the neighbor is first checked to lie inside it.
                    if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                        grid[nx][ny] = 0
                        stack.append((nx, ny))
    # 7. Return the number of islands counted
    return count

Example 1, traced

Input
grid = [[1,1,0],[0,1,0],[0,0,1]]

Output
2

Why it works

Each time the scan looks at a new cell, every cell that still holds 1 belongs to an island that has not been counted. The scan counts an island at its first cell and sinks all of it before moving on: every cell of an island is joined to that first cell through neighbors, so the spreading reaches it. So no island is counted twice and none is missed.

Time and space

Time O(rows × columns), extra space O(rows × columns). The scan visits all rows × columns cells once. A cell can be sunk only once, so it joins the list at most once, and its four neighbors are checked once: O(rows × columns) time. The list never holds more cells than the grid has: O(rows × columns) space.

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Spread in all four directions. Right and down may seem enough for a scan that moves right and down, but an island can bend back: the grid with rows 0 1 and 1 1 then gives 2 instead of 1.
• Check that a neighbor is inside the grid before you read it. Python does not complain about row -1: it reads the last row, so land on the top edge silently joins land on the bottom edge.
• Do not read the first row before you know there is one. Three tests pass a grid with no rows, and asking for the length of its first row stops the program with an error.

Pattern

Grid connected components. Builds on Binary Tree Level Order Traversal and Word Search.

Keep going