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.

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

python

▶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

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.

06

Complexity

Time

O(R·C)

Space

O(R·C)

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