~20 minutes · Day 52 · grid DFS · Python
Tonight you meet your first graph problem: Number of Islands. It does not look like a graph at first. It looks like rows and columns. In interviews, that is the point: many graph questions hide inside grids, and the skill is to see each land cell as a node with up to four edges.
DFS floods everything reachable in one component; count how many times you must start a new flood. The grid itself is the adjacency list — mark visited in place.
That one sentence is the pattern. When the scan finds fresh land, you have found a new component. A depth-first search then floods every land cell connected to it, so none of those cells can start another island later. LeetCode defines islands with horizontal and vertical neighbors only, not diagonals (problem statement).
The first fresh land cell starts one flood; diagonal land is not connected in this problem.
A graph normally has an adjacency list: for each node, a list of its neighbors. In a grid, the coordinates create those neighbors for free:
(r, c)."1" into water "0".A grid cell becomes a graph node; its four coordinate moves are the edges.
Depth-first search keeps walking from a node into an unvisited neighbor until it cannot go farther, then backs up. In Python, a list can work as a stack with append and pop (Python docs).
The brute force way is to start a fresh search from every land cell, rediscover its whole island, then compare that discovered set with islands you saved earlier. It works, but a grid full of land makes you rediscover the same component from many starting cells. With m * n cells, that can grow to O((mn)^2) time.
The better question is simpler: has this land cell been flooded yet? If no, count one island and flood the whole component immediately.
def num_islands(grid):
R, C, islands = len(grid), len(grid[0]), 0
for r in range(R):
for c in range(C):
if grid[r][c] != "1": continue
islands += 1; stack = [(r, c)]; grid[r][c] = "0" # start flood
while stack:
x, y = stack.pop()
for nr, nc in ((x+1,y), (x-1,y), (x,y+1), (x,y-1)):
if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1":
grid[nr][nc] = "0"; stack.append((nr, nc)) # mark once
return islands
The scan is the island counter. The stack is the flood. The in-place mark is what prevents double counting: once land becomes "0", later scans and later floods ignore it.
Max Area of Island: instead of counting how many islands exist, return the size of the largest island.
Before opening the reveal: what changes in the code? Say the invariant out loud, then predict which variable should replace islands += 1.
It is the same flood. Start a flood whenever you find fresh land, but make that flood count how many cells it marks. Keep best = max(best, area). The graph model did not change; only the value you collect from each component changed.
| Approach | Time | Space |
|---|---|---|
| Brute force (fresh search from each land cell) | O((mn)^2) | O(mn) |
| DFS flood (mark each land cell once) | O(mn) | O(mn) |
The O(mn) space is the worst case for the stack when a huge island is waiting to be explored. The important win is that every cell is marked at most once.
1. What tells you to start a new island flood?
2. Why mark a land cell before adding its neighbors?
3. Spot the bug in this island loop:
for r in range(R):
for c in range(C):
if grid[r][c] == "1":
islands += 14. Which task is this pattern in disguise?
Solve Number of Islands on LeetCode, logging it in your Notion tracker with the cycle - predict -> attempt -> compare -> encode:
Watch NeetCode - Number of Islands after your attempt, as the compare step. Do not use it before the first serious try.
Stuck or curious? Ask your teacher (the agent) - that's what it's for.