LeetCode 200 · Graphs

Number of Islands, explained with a picture

Painting islands on a sea chart.

MediumGraphs
▶ Watch it step by step

The problem

Given a map of 1s (land) and 0s (water), count the islands. An island is a group of land cells connected up, down, left or right.

Input:  11000 / 11000 / 00100 / 00011
Output: 3

Picture it

Picture a sea chart. We scan it cell by cell. When we hit land we haven’t painted yet, we’ve found a new island: count it and paint that whole island (flood fill to every connected land cell) so we never count it again.

How to recognise it

  • The input is a grid, and cells touching up, down, left or right belong together.
  • The question is about groups of connected cells: how many, how big, or whether two cells share a group.
  • Nothing asks for a shortest distance, so any traversal that visits a whole group will do.
  • Rows × columns can be 300 × 300 = 90,000 cells, so you cannot afford to re-explore the same cells many times.

Start with brute force

For every land cell, search outwards to find its whole island with a fresh visited set, and note the island's smallest cell. Count a cell only if it is the smallest cell of its own island, so each island is counted exactly once.

def num_islands_brute(grid):
    R, C = len(grid), len(grid[0])
    def smallest(r0, c0):
        seen, stack = {(r0, c0)}, [(r0, c0)]
        while stack:
            r, c = stack.pop()
            for nr, nc in nbrs(grid, r, c):
                if grid[nr][nc] == "1" and (nr, nc) not in seen:
                    seen.add((nr, nc)); stack.append((nr, nc))
        return min(seen)
    return sum(1 for r in range(R) for c in range(C)
               if grid[r][c] == "1" and smallest(r, c) == (r, c))

Every land cell triggers a search that may cover the whole grid, so the time is O(R·C) searches of O(R·C) each, which is O((R·C)²). On a 300 × 300 grid of land that is about 90,000 × 90,000 = 8 × 10^9 steps, far too slow. It also needs O(R·C) extra space for the visited sets.

From brute force to the idea

  1. Find the waste. Once you have explored an island, you already know every cell in it. The brute force throws that knowledge away and rediscovers the same island from each of its cells.
  2. Paint what you have seen. The shown code overwrites each visited land cell with "0", so a cell can never be explored twice. The grid itself is the visited set.
  3. One search per island. Scan the grid in order. When you meet a "1", it must belong to an island you have not seen yet: add one to the count, then call flood, which spreads out with a queue and turns the entire island to "0".
  4. Mark when you push. Cells are set to "0" as they enter the queue, not when they leave it, so no cell is queued twice.

The key idea: each island is found once, at its first cell in scan order, and then erased.

The key idea

For each unvisited land cell: count + 1, then DFS/BFS to mark its whole island. O(rows × cols).

Python solution

def num_islands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == "1":
                count += 1
                flood(grid, r, c)
    return count

def flood(grid, r, c):
    q = deque([(r, c)]); grid[r][c] = "0"
    while q:
        r, c = q.popleft()
        for nr, nc in nbrs(grid, r, c):
            if grid[nr][nc] == "1":
                grid[nr][nc] = "0"
                q.append((nr, nc))

def nbrs(g, r, c):  # in-grid neighbours
    R, C = len(g), len(g[0])
    for nr, nc in ((r+1, c), (r-1, c),
                   (r, c+1), (r, c-1)):
        if 0 <= nr < R and 0 <= nc < C:
            yield nr, nc

LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import deque

In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.

Complexity

ApproachTimeSpace
Brute forceO((R·C)²): each land cell starts a search over up to R·C cellsO(R·C): a visited set per search
Flood fill (shown code)O(R·C): every cell is queued at most once and checks four neighboursO(R·C) in the worst case for the queue; the grid is changed in place

Edge cases

  • Empty grid []: returns 0, because the outer loop never runs. (The problem promises at least one row.)
  • All water ([["0","0"]]): returns 0.
  • All land: returns 1, however large the grid is.
  • Diagonal neighbours ([["1","0"],["0","1"]]): returns 2, because only four directions count.
  • The input is destroyed: after the call every "1" has become "0". Copy the grid first if the caller still needs it.
  • Missing import: the shown code uses deque, so it needs from collections import deque. It uses a queue rather than recursion, so a 300 × 300 grid of land does not hit Python's recursion limit.

Common mistakes

  • Forgetting to mark cells, so the fill bounces between neighbours forever or counts one island many times.
  • Marking a cell only when it is popped, which lets the same cell enter the queue several times.
  • Comparing to the integer 1 when the grid holds the characters "1".
  • Including diagonals when the problem says four directions.
  • Using recursive DFS on a large grid and hitting the recursion limit.
Your turn: diagonals count too

Count islands when cells that touch diagonally are also connected, so [["1","0"],["0","1"]] is a single island. Describe what changes, then write it if you like.

Compare with our answer

Nothing about the plan changes: scan, count, flood. Only the neighbour rule changes, from 4 directions to 8.

def count_islands_8(grid):
    def nbrs8(r, c):
        for dr in (-1, 0, 1):
            for dc in (-1, 0, 1):
                nr, nc = r + dr, c + dc
                if (dr or dc) and 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):
                    yield nr, nc
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == "1":
                count += 1
                grid[r][c] = "0"
                q = deque([(r, c)])
                while q:
                    a, b = q.popleft()
                    for nr, nc in nbrs8(a, b):
                        if grid[nr][nc] == "1":
                            grid[nr][nc] = "0"
                            q.append((nr, nc))
    return count

count_islands_8([["1","0"],["0","1"]]) is 1. Time O(R·C) (eight neighbour checks per cell, still a constant), space O(R·C) worst case.

A strong answer mentions: only the neighbour list changes, each cell is still visited once, and the cost stays O(R·C).

Check what stuck

1. A cinema seating chart is a grid of occupied (1) and empty (0) seats. You must count the groups of occupied seats that touch side to side. Which approach fits best?

2. Why does the shown solution run in O(R·C) even though it contains a flood fill inside a double loop?

3. A learner replaces nbrs so it also yields the four diagonal neighbours. Which input now returns a wrong answer for Number of Islands?

Score 60% or more and the lesson is marked complete.