DSAMotivator

Number of Islands

Medium·🕸️ Graphs (BFS/DFS)·Open on LeetCode ↗

Given a rectangular map of land and water cells, count how many separate landmasses there are, where land joined edge-to-edge counts as one.

a 3×4 map where 1 is land and 0 is waterstep 1/11
1
1
0
1
1
0
0
1
0
0
1
0

Scan cell by cell. Every time the scan finds land it hasn't seen, that's a new island.

1def num_islands(grid):
2    rows, cols = len(grid), len(grid[0])
3    count = 0
4 
5    def sink(r, c):
6        if r < 0 or r >= rows or c < 0 or c >= cols:
7            return
8        if grid[r][c] != "1":
9            return
10        grid[r][c] = "0"
11        sink(r + 1, c); sink(r - 1, c)
12        sink(r, c + 1); sink(r, c - 1)
13 
14    for r in range(rows):
15        for c in range(cols):
16            if grid[r][c] == "1":
17                count += 1
18                sink(r, c)
19    return count
Read the 11 steps as text
  1. 1Scan cell by cell. Every time the scan finds land it hasn't seen, that's a new island.
  2. 2Land at (0, 0) that isn't part of anything yet — island 1.
  3. 3Sink (0, 0) — it belongs to island 1, so it can never be counted again.
  4. 4Sink (1, 0) — it belongs to island 1, so it can never be counted again.
  5. 5Sink (0, 1) — it belongs to island 1, so it can never be counted again.
  6. 6Land at (0, 3) that isn't part of anything yet — island 2.
  7. 7Sink (0, 3) — it belongs to island 2, so it can never be counted again.
  8. 8Sink (1, 3) — it belongs to island 2, so it can never be counted again.
  9. 9Land at (2, 2) that isn't part of anything yet — island 3.
  10. 10Sink (2, 2) — it belongs to island 3, so it can never be counted again.
  11. 11The scan is finished. 3 separate islands.

The idea

A grid is a graph wearing a costume. Each land cell is a node, and two land cells share an edge when they're horizontally or vertically adjacent. Counting islands is counting connected components — a problem with a standard answer.

The standard answer: scan for any node you haven't visited, and when you find one, walk the entire component it belongs to before continuing the scan. Every time the scan discovers something new, that's exactly one more component.

The trick that keeps this simple is what you do with the cells you've walked. Instead of maintaining a separate visited set, overwrite the land with water. A sunk cell is indistinguishable from ocean, so the outer scan skips it for free and no cell can ever be counted twice.

The approach

  1. 1Scan every cell in the grid, row by row.
  2. 2When you hit a land cell, increment the count — you've just discovered a new island.
  3. 3Immediately flood from that cell: sink it, then recurse into its four neighbours, stopping at the grid edge or at water.
  4. 4Continue the scan. Everything belonging to the island you just counted is now water, so it can't be counted again.

Complexity

Time
O(rows × cols)
Space
O(rows × cols)

Each cell is visited a constant number of times. The space is the recursion stack, which in the worst case — a grid that is entirely land — is as deep as the grid is large.

Code

def num_islands(grid):
    rows, cols = len(grid), len(grid[0])
    count = 0

    def sink(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols:
            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 r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1":
                count += 1
                sink(r, c)
    return count

What goes wrong

  • •Counting diagonals as connected. Unless the problem says otherwise it's four-directional, and eight-directional silently merges islands that should stay separate.
  • •Forgetting to sink the starting cell before recursing, which sends the flood straight back into where it came from and overflows the stack.
  • •Sinking cells but not checking bounds first — the recursion walks off the edge of the grid on the very first island touching a border.
  • •If mutating the caller's grid is unacceptable, say so and use a visited set instead. Interviewers do ask, and "I destroyed your input" is a real answer to have ready.