Number of Islands (LeetCode 200)
You get an m x n grid grid of '1' (land) and '0' (water) cells, forming a map surrounded on all four sides by water. Count how many islands it contains, where an island is a group of land cells chained together through up/down/left/right neighbors.
Return that count.
Worked Examples
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]1grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]3⚖️Formal Constraints & Bounds
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Core Insight
Each connected component of '1's forms one island. Sinking visited land cells (e.g. setting them to '0') avoids separate visited set overhead.
Real-World Scenario & Production Applications
Image segmentation in computer vision and counting connected user communities in social networks both rely on connected-component grid flood-fills.
Subproblems & Recurrence Decomposition3 Phases
Iterate over every cell (r, c). Upon discovering an unvisited land cell (grid[r][c] == '1'), increment island count and initiate traversal.
island_count = 0
for r in range(R):
for c in range(C):
if grid[r][c] == "1":
island_count += 1
dfs(r, c)Step-by-Step Execution Trace Table
| Step | Outer Scan Coordinate | Cell State | Flood Fill Action | Cells Sunk to '0' | Island Count |
|---|---|---|---|---|---|
| 1 | (0,0) | Land ('1'), unvisited | Discover Island #1 DFS drain | (0,0), (1,0), (0,1) | 1 |
| 2 | (0,1) | Already sunk ('0') | Skip in | — | 1 |
| 3 | (0,2), (0,3) | Water ('0') | Skip | — | 1 |
| 4 | (0,4) | Land ('1'), unvisited | Discover Island #2 DFS drain | (0,4), (1,4) | 2 |
| 5 | (1,0) | Already sunk ('0') | Skip in | — | 2 |
| 6 | (1,1)–(1,3) | Water ('0') | Skip | — | 2 |
| 7 | (1,4) | Already sunk ('0') | Skip in | — | 2 |
| 8 | (2,0), (2,1) | Water ('0') | Skip | — | 2 |
| 9 | (2,2) | Land ('1'), unvisited | Discover Island #3 DFS drain | (2,2) alone | 3 |
| 10 | (2,3), (2,4) | Water ('0') | Skip | — | 3 (Done) |
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]1| Step | Outer Scan Coordinate | Cell State | Flood Fill Action | Cells Sunk to '0' | Island Count |
|---|---|---|---|---|---|
| 1 | (0,0) | Land ('1'), unvisited | Discover Island #1 DFS drain | (0,0), (1,0), (0,1) | 1 |
| 2 | (0,1) | Already sunk ('0') | Skip in | — | 1 |
| 3 | (0,2), (0,3) | Water ('0') | Skip | — | 1 |
| 4 | (0,4) | Land ('1'), unvisited | Discover Island #2 DFS drain | (0,4), (1,4) | 2 |
| 5 | (1,0) | Already sunk ('0') | Skip in | — | 2 |
| 6 | (1,1)–(1,3) | Water ('0') | Skip | — | 2 |
| 7 | (1,4) | Already sunk ('0') | Skip in | — | 2 |
| 8 | (2,0), (2,1) | Water ('0') | Skip | — | 2 |
| 9 | (2,2) | Land ('1'), unvisited | Discover Island #3 DFS drain | (2,2) alone | 3 |
| 10 | (2,3), (2,4) | Water ('0') | Skip | — | 3 (Done) |
| 1 | R, C = len(grid), len(grid[0]) |
| 2 | islands = 0 |
| 3 | for r in range(R): |
| 4 | for c in range(C): |
| 5 | if grid[r][c] == "1": |
| 6 | islands += 1 |
| 7 | stack = [(r, c)] |
| 8 | grid[r][c] = "0" |
| 9 | while stack: |
| 10 | curr_r, curr_c = stack.pop() |
| 11 | for each in-bounds neighbour (nr, nc) with grid[nr][nc] == "1": |
| 12 | grid[nr][nc] = "0" |
| 13 | stack.append((nr, nc)) |
| 14 | return islands |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting islands sounds like a geometry problem, but it's really a foundational graph question wearing a grid costume: every land cell is a node, and two adjacent land cells share an edge.
🏝️ The Analogy: Sinking Each Island as You Count It
Imagine scanning a map left-to-right, top-to-bottom, looking for unclaimed land. The moment you spot one, you know you've found a new island, so you count it — then you immediately "sink" that entire island (and every cell connected to it) so your scan never mistakes it for a second island later. Sinking an entire connected blob is exactly what a flood-fill traversal (BFS or DFS) does: start at one land cell, spread to every reachable neighboring land cell, marking each one visited so it's permanently excluded from future counting.
🔑 The Key Idea in the Code
The outer double-loop only ever increments islands when it lands on land that hasn't already been claimed by an earlier flood-fill — everything the inner while loop touches is turned to "0" so the outer scan glides right over it.
Marking visited on pop instead of push in BFS: Waiting until a cell is popped from the queue to mark it
'0'(or visited). Multiple neighboring cells will discover and enqueue the same cell, causing queue memory to grow exponentially to .Destructive mutation side-effects: Mutating
grid[r][c] = '0'in place when the interviewer specifies that the input grid is immutable or read-only. Clarify whether grid mutation is allowed; if not, maintain an explicitvisitedset.String
'1'vs integer1type mismatch: Checkingif grid[r][c] == 1instead of== '1'. LeetCode providesgridas a list of strings, so integer comparison silently evaluates toFalseon all cells.Python Recursion Limit Crash: for large snake-like islands (N = 300), DFS depth can exceed Python's default recursion limit (1000). A Senior SWE uses an iterative queue (BFS) or
sys.setrecursionlimit(200000)in production systems.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The grid holds "1" (land) and "0" (water), and an island is land "connected horizontally or vertically": the task is to count separate groups of joined cells, which is Flood Fill: one scan for new groups, one search per group.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Between searches, every land cell turned to "0" belongs to an island already counted in islands, and every "1" left belongs to one not counted yet. So the outer scan meeting a "1" means a new island: count it once, then flood it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
islands += 1belongs in the outer scan, once per search: inside thewhile stackloop it counts cells, not islands.grid[nr][nc] = "0"goes withstack.append((nr, nc)): marking on pop instead lets a cell be pushed by several neighbours before it is ever popped.0 <= nr < R and 0 <= nc < Ccomes beforegrid[nr][nc]: a cell on the edge has neighbours outside the grid:nr = -1silently reads the last row through Python's negative index, andnr = RraisesIndexError.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Counting islands is counting groups of joined land cells, so I'd use Flood Fill. I scan every cell. When I meet a one, that's land no search has reached, so it starts a new island: I add one to the count and flood that island with a stack search. Every land cell the search reaches is turned to zero as I push it, so the scan never meets that island again, and each island is counted exactly once. The trap is where the counter lives: it goes in the outer scan, once per search, never inside the flood, where it would count cells instead of islands. I use an explicit stack, not recursion, so a big snake-shaped island can't pass the recursion limit. Every cell is read by the scan and pushed at most once, so it's O(R times C) time, and O(R times C) space for the stack in the worst case."
Complexity & Mathematical Proof
O(R * C)
Look at the code: the two for loops read each of the R * C cells once. A land cell enters stack only while it is still "1", and it is turned to "0" at that moment (the first cell right after the scan finds it, every other cell together with stack.append), so each cell is pushed and popped at most once. Each pop checks 4 neighbours with O(1) work. Total: R * C scan steps plus at most 4 * R * C neighbour checks, O(R * C).
O(R * C)
There is no recursion: the search keeps its cells in the explicit stack on the heap. A cell is marked as it is pushed, so it is never in stack twice, and stack holds at most R * C cells; on an all-land grid it grows to about half the cells. The grid is changed in place, so there is no visited set.
T(R, C) = R * C (scan) + R * C (pushes and pops) + 4 * R * C (neighbour checks) = O(R * C)
Derivation Progression
for r in range(R): for c in range(C): R * C cell checks
Each cell is read once; a "1" starts a new island and a search.
grid[nr][nc] = "0" right before stack.append((nr, nc)): at most R * C pushes and pops
A cell turns to "0" as it is pushed, so no later neighbour can push it again.
for dr, dc in 4 directions: at most 4 * R * C checks, O(1) each
The bounds test and the "1" test cost O(1) per neighbour.
Variable Definitions
Number of rows, len(grid)
Number of columns, len(grid[0])
Memory Architecture & Bounds
O(1): no recursion
O(R * C): the explicit stack; cells are marked on push, so each cell enters it at most once
O(1): one integer, islands
Boundary Best / Worst Cases
all water: the scan still reads every cell, and stack stays empty.
.
all land: one search pushes every cell, and stack holds about half of them at its peak.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: images and maps with millions of cells. One scan plus one search per island stays , while searching again from every land cell would be quadratic.
, so at most cells. The grid is changed in place, so the only extra memory is the stack, which on an all-land grid grows to about half the cells.
For a very large image, even the explicit stack can hold a large fraction of all cells. Image libraries label components row by row instead, joining labels from the row above with union-find, so memory stays close to one row of labels plus the label table.
Core Algorithmic State Invariants
- Example 2, Island by Island
The scan meets (0, 0) first: islands = 1, and the search turns the 2 x 2 block of land to "0". It then meets (2, 2): islands = 2, a single cell. Last is (3, 3): islands = 3, the pair (3, 3) and (3, 4).
- Diagonal Cells Are Separate
Only up, down, left and right join cells. In [["1", "0"], ["0", "1"]] the two land cells touch only at a corner, so the scan starts two searches and the answer is 2.
Number of Islands (LeetCode 200)
You get an m x n grid grid of '1' (land) and '0' (water) cells, forming a map surrounded on all four sides by water. Count how many islands it contains, where an island is a group of land cells chained together through up/down/left/right neighbors.
Return that count.
Worked Examples
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]1grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]3⚖️Formal Constraints & Bounds
m == grid.lengthn == grid[i].length1 <= m, n <= 300grid[i][j]is'0'or'1'.
Core Insight
Each connected component of '1's forms one island. Sinking visited land cells (e.g. setting them to '0') avoids separate visited set overhead.
Real-World Scenario & Production Applications
Image segmentation in computer vision and counting connected user communities in social networks both rely on connected-component grid flood-fills.
Subproblems & Recurrence Decomposition3 Phases
Iterate over every cell (r, c). Upon discovering an unvisited land cell (grid[r][c] == '1'), increment island count and initiate traversal.
island_count = 0
for r in range(R):
for c in range(C):
if grid[r][c] == "1":
island_count += 1
dfs(r, c)Step-by-Step Execution Trace Table
| Step | Outer Scan Coordinate | Cell State | Flood Fill Action | Cells Sunk to '0' | Island Count |
|---|---|---|---|---|---|
| 1 | (0,0) | Land ('1'), unvisited | Discover Island #1 DFS drain | (0,0), (1,0), (0,1) | 1 |
| 2 | (0,1) | Already sunk ('0') | Skip in | — | 1 |
| 3 | (0,2), (0,3) | Water ('0') | Skip | — | 1 |
| 4 | (0,4) | Land ('1'), unvisited | Discover Island #2 DFS drain | (0,4), (1,4) | 2 |
| 5 | (1,0) | Already sunk ('0') | Skip in | — | 2 |
| 6 | (1,1)–(1,3) | Water ('0') | Skip | — | 2 |
| 7 | (1,4) | Already sunk ('0') | Skip in | — | 2 |
| 8 | (2,0), (2,1) | Water ('0') | Skip | — | 2 |
| 9 | (2,2) | Land ('1'), unvisited | Discover Island #3 DFS drain | (2,2) alone | 3 |
| 10 | (2,3), (2,4) | Water ('0') | Skip | — | 3 (Done) |
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]1| Step | Outer Scan Coordinate | Cell State | Flood Fill Action | Cells Sunk to '0' | Island Count |
|---|---|---|---|---|---|
| 1 | (0,0) | Land ('1'), unvisited | Discover Island #1 DFS drain | (0,0), (1,0), (0,1) | 1 |
| 2 | (0,1) | Already sunk ('0') | Skip in | — | 1 |
| 3 | (0,2), (0,3) | Water ('0') | Skip | — | 1 |
| 4 | (0,4) | Land ('1'), unvisited | Discover Island #2 DFS drain | (0,4), (1,4) | 2 |
| 5 | (1,0) | Already sunk ('0') | Skip in | — | 2 |
| 6 | (1,1)–(1,3) | Water ('0') | Skip | — | 2 |
| 7 | (1,4) | Already sunk ('0') | Skip in | — | 2 |
| 8 | (2,0), (2,1) | Water ('0') | Skip | — | 2 |
| 9 | (2,2) | Land ('1'), unvisited | Discover Island #3 DFS drain | (2,2) alone | 3 |
| 10 | (2,3), (2,4) | Water ('0') | Skip | — | 3 (Done) |
| 1 | R, C = len(grid), len(grid[0]) |
| 2 | islands = 0 |
| 3 | for r in range(R): |
| 4 | for c in range(C): |
| 5 | if grid[r][c] == "1": |
| 6 | islands += 1 |
| 7 | stack = [(r, c)] |
| 8 | grid[r][c] = "0" |
| 9 | while stack: |
| 10 | curr_r, curr_c = stack.pop() |
| 11 | for each in-bounds neighbour (nr, nc) with grid[nr][nc] == "1": |
| 12 | grid[nr][nc] = "0" |
| 13 | stack.append((nr, nc)) |
| 14 | return islands |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Counting islands sounds like a geometry problem, but it's really a foundational graph question wearing a grid costume: every land cell is a node, and two adjacent land cells share an edge.
🏝️ The Analogy: Sinking Each Island as You Count It
Imagine scanning a map left-to-right, top-to-bottom, looking for unclaimed land. The moment you spot one, you know you've found a new island, so you count it — then you immediately "sink" that entire island (and every cell connected to it) so your scan never mistakes it for a second island later. Sinking an entire connected blob is exactly what a flood-fill traversal (BFS or DFS) does: start at one land cell, spread to every reachable neighboring land cell, marking each one visited so it's permanently excluded from future counting.
🔑 The Key Idea in the Code
The outer double-loop only ever increments islands when it lands on land that hasn't already been claimed by an earlier flood-fill — everything the inner while loop touches is turned to "0" so the outer scan glides right over it.
Marking visited on pop instead of push in BFS: Waiting until a cell is popped from the queue to mark it
'0'(or visited). Multiple neighboring cells will discover and enqueue the same cell, causing queue memory to grow exponentially to .Destructive mutation side-effects: Mutating
grid[r][c] = '0'in place when the interviewer specifies that the input grid is immutable or read-only. Clarify whether grid mutation is allowed; if not, maintain an explicitvisitedset.String
'1'vs integer1type mismatch: Checkingif grid[r][c] == 1instead of== '1'. LeetCode providesgridas a list of strings, so integer comparison silently evaluates toFalseon all cells.Python Recursion Limit Crash: for large snake-like islands (N = 300), DFS depth can exceed Python's default recursion limit (1000). A Senior SWE uses an iterative queue (BFS) or
sys.setrecursionlimit(200000)in production systems.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The grid holds "1" (land) and "0" (water), and an island is land "connected horizontally or vertically": the task is to count separate groups of joined cells, which is Flood Fill: one scan for new groups, one search per group.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Between searches, every land cell turned to "0" belongs to an island already counted in islands, and every "1" left belongs to one not counted yet. So the outer scan meeting a "1" means a new island: count it once, then flood it.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
islands += 1belongs in the outer scan, once per search: inside thewhile stackloop it counts cells, not islands.grid[nr][nc] = "0"goes withstack.append((nr, nc)): marking on pop instead lets a cell be pushed by several neighbours before it is ever popped.0 <= nr < R and 0 <= nc < Ccomes beforegrid[nr][nc]: a cell on the edge has neighbours outside the grid:nr = -1silently reads the last row through Python's negative index, andnr = RraisesIndexError.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"Counting islands is counting groups of joined land cells, so I'd use Flood Fill. I scan every cell. When I meet a one, that's land no search has reached, so it starts a new island: I add one to the count and flood that island with a stack search. Every land cell the search reaches is turned to zero as I push it, so the scan never meets that island again, and each island is counted exactly once. The trap is where the counter lives: it goes in the outer scan, once per search, never inside the flood, where it would count cells instead of islands. I use an explicit stack, not recursion, so a big snake-shaped island can't pass the recursion limit. Every cell is read by the scan and pushed at most once, so it's O(R times C) time, and O(R times C) space for the stack in the worst case."
Complexity & Mathematical Proof
O(R * C)
Look at the code: the two for loops read each of the R * C cells once. A land cell enters stack only while it is still "1", and it is turned to "0" at that moment (the first cell right after the scan finds it, every other cell together with stack.append), so each cell is pushed and popped at most once. Each pop checks 4 neighbours with O(1) work. Total: R * C scan steps plus at most 4 * R * C neighbour checks, O(R * C).
O(R * C)
There is no recursion: the search keeps its cells in the explicit stack on the heap. A cell is marked as it is pushed, so it is never in stack twice, and stack holds at most R * C cells; on an all-land grid it grows to about half the cells. The grid is changed in place, so there is no visited set.
T(R, C) = R * C (scan) + R * C (pushes and pops) + 4 * R * C (neighbour checks) = O(R * C)
Derivation Progression
for r in range(R): for c in range(C): R * C cell checks
Each cell is read once; a "1" starts a new island and a search.
grid[nr][nc] = "0" right before stack.append((nr, nc)): at most R * C pushes and pops
A cell turns to "0" as it is pushed, so no later neighbour can push it again.
for dr, dc in 4 directions: at most 4 * R * C checks, O(1) each
The bounds test and the "1" test cost O(1) per neighbour.
Variable Definitions
Number of rows, len(grid)
Number of columns, len(grid[0])
Memory Architecture & Bounds
O(1): no recursion
O(R * C): the explicit stack; cells are marked on push, so each cell enters it at most once
O(1): one integer, islands
Boundary Best / Worst Cases
all water: the scan still reads every cell, and stack stays empty.
.
all land: one search pushes every cell, and stack holds about half of them at its peak.
Graph & Tree Traversal Frontier
Senior SWE Deconstruction & Hardware Caveats
Scale signal: images and maps with millions of cells. One scan plus one search per island stays , while searching again from every land cell would be quadratic.
, so at most cells. The grid is changed in place, so the only extra memory is the stack, which on an all-land grid grows to about half the cells.
For a very large image, even the explicit stack can hold a large fraction of all cells. Image libraries label components row by row instead, joining labels from the row above with union-find, so memory stays close to one row of labels plus the label table.
Core Algorithmic State Invariants
- Example 2, Island by Island
The scan meets (0, 0) first: islands = 1, and the search turns the 2 x 2 block of land to "0". It then meets (2, 2): islands = 2, a single cell. Last is (3, 3): islands = 3, the pair (3, 3) and (3, 4).
- Diagonal Cells Are Separate
Only up, down, left and right join cells. In [["1", "0"], ["0", "1"]] the two land cells touch only at a corner, so the scan starts two searches and the answer is 2.