Number of Islands
Number of Islands: count islands in a grid of '1' (land) and '0' (water). Land connects 4-directionally.
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] is '0' or '1'.
Intuition
Number of islands counts connected groups of land in a grid, where cells connect horizontally and vertically. The temptation is to devise a counting rule based on shapes or edges; the right move is to recognise this as counting connected components, a standard graph problem wearing a grid costume. The algorithm follows directly. Scan every cell. When you find land that has not yet been visited, you have discovered a component nobody has seen before — so increment the count once, then flood the entire component so none of its other cells can trigger another increment. That is the whole idea, and its correctness rests on one observation: - The counter fires only on land that survived every previous flood, which means land belonging to a component not yet visited. One fire per component, and every component eventually fires, so the count is exact. The flood itself is a DFS or BFS from the discovered cell, converting each reachable land cell to water — or marking it visited. Overwriting the grid is the neat version, since it removes the need for a separate visited structure, though it does destroy the input. One detail is essential: mark the cell before recursing into its neighbours, not after. Two adjacent land cells would otherwise call into each other endlessly. On a large grid the recursion can be thousands deep, so an explicit stack or BFS queue is safer than recursion when the whole grid might be one island.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what one visit per cell or vertex would have to mark so nothing is counted twice. Aim for O(R·C) time and O(R·C) space.
Recognise it as counting components
Each island is a connected component of land cells under 4-directional adjacency. Framing it this way makes the algorithm standard rather than something to invent — scan, discover, flood, repeat.
Scan every cell once
Loop over the whole grid. Most cells are water or already-flooded land and cost O(1) to skip; only an unvisited land cell triggers work.
Count once, then flood
On finding unvisited land, increment the answer and immediately flood the entire component. The increment happens once per component because every other cell in it is erased before the scan reaches it.
Mark before recursing
Set the cell to water or visited before exploring its neighbours. Marking afterwards lets two adjacent cells recurse into each other indefinitely — the classic infinite-loop bug in flood fill.
Check bounds inside the flood
The recursion must reject out-of-range coordinates and water cells before doing anything. Handling it at the top of the function keeps the four neighbour calls uniform with no guards at each call site.
Prefer an explicit stack on large grids
A single grid-spanning island gives recursion depth of rows × cols, which overflows the call stack on big inputs. An explicit stack or a BFS queue avoids that at the same asymptotic cost.
Cost of the sweep
Every cell is examined by the outer scan once and flooded at most once, giving O(rows × cols) time. Space is O(rows × cols) worst case for the traversal structure when the grid is entirely land.
Solution & live demo
Common pitfalls
Marking cells visited after recursing instead of on entry
sink(r+1, c); sink(r-1, c); sink(r, c+1); sink(r, c-1) grid[r][c] = "0"
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
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)
def sink(r, c):
if r < 0 or r >= R or c < 0 or c >= C or grid[r][c] != "1":
returnThe 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
if grid[r][c] != 1:
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.
Edge cases
Counter never fires — 0.
First cell fires, flood sinks everything — 1.
Diagonals are not connections; such islands count separately.