LeetCode #200 Medium

Number of Islands

Count islands in a grid of '1' (land) and '0' (water). Land connects 4-directionally.

griddfsbfs

02

Intuition

Every island is one connected component. Scan the grid; each time you step on unvisited land, that is a brand-new island — count it, then flood-fill (sink) the whole component so none of its cells can be counted again. The counter increments exactly once per island because the flood erases the rest of it.

How to spot this pattern

Counting connected components is always the same two-part shape: scan every cell, and whenever you meet an unvisited piece of a component, increment the counter and flood the entire component so it's never counted again. The flood can be DFS or BFS — it makes no difference to the answer. Recognise it whenever the question asks how many groups, as opposed to how large or how far.

03

Approach

1

Scan + sink

Loop over every cell. On seeing '1': answer += 1, then DFS from that cell turning every reachable '1' into '0' (or a visited mark).

2

The flood fill

DFS(r,c): if out of bounds or water, return. Set grid[r][c]='0', recurse into the 4 neighbors. Marking before recursing prevents infinite loops.

3

Why it counts correctly

The counter only fires on land that survived all previous floods — i.e. land in a component never seen before. One fire per component = number of islands.

04

Solution & live demo

▶1class Solution:
▶2    def numIslands(self, grid):
▶3        R, C = len(grid), len(grid[0])
▶4        def sink(r, c):
▶5            if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != "1":
▶6                return
▶7            grid[r][c] = "0"
▶8            sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
▶9        count = 0
▶10        for r in range(R):
▶11            for c in range(C):
▶12                if grid[r][c] == "1":
▶13                    count += 1
▶14                    sink(r, c)
▶15        return count

05

Common pitfalls

Marking cells visited after recursing instead of on entry

✗ Wrong

sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)
grid[r][c] = "0"

✓ Right

grid[r][c] = "0"
sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1)

Two adjacent land cells each recurse into the other before either is marked, so the recursion bounces between them until the stack overflows. Mark first, then explore — the mark is what terminates the search.

Checking bounds at the call site

✗ Wrong

if r + 1 < R and grid[r+1][c] == "1": sink(r+1, c)
if r - 1 >= 0 and grid[r-1][c] == "1": sink(r-1, c)

✓ Right

def sink(r, c):
    if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != "1":
        return

The same four conditions get written at every call site, and one typo among them is easy to miss. Validating once at the top of the function covers all four directions and both recursion and the initial call.

Comparing against integers when the grid holds strings

✗ Wrong

if grid[r][c] != 1:

✓ Right

if grid[r][c] != "1":

LeetCode passes this grid as characters, not numbers. "1" != 1 is always true in Python, so every cell reads as water and the count comes back 0.

06

Edge cases

All water

Counter never fires — 0.

All land

First cell fires, flood sinks everything — 1.

Diagonal-only touching

Diagonals are not connections; such islands count separately.

07

Complexity

Time

O(R·C)

Space

O(R·C)

Each cell visited a constant number of times; recursion depth worst-case the whole grid.