Connected Components (Number of Islands / Flood Fill)
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.
Flood Fill
2D grid / graph ➔ outer unvisited discovery ➔ consume full component| 1 | from typing import Callable, Dict, Hashable, Iterable, List |
| 2 | |
| 3 | |
| 4 | def flood_fill(cells: Iterable[Hashable], is_land: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Hashable]]) -> Dict[Hashable, int]: |
| 5 | """Flood Fill: label every land cell with the number of its group of connected land |
| 6 | cells. |
| 7 | Precondition: neighbors is symmetric. If b is a neighbour of a, then a is a |
| 8 | neighbour of b. |
| 9 | Groups are numbered 0, 1, 2, ... in scan order, so the number of groups is |
| 10 | max(group.values()) + 1. |
| 11 | V = cells. T = the cost of one is_land or neighbors call (neighbors yields at most T |
| 12 | cells). |
| 13 | Time: O(V * T) | Space: O(V) |
| 14 | """ |
| 15 | # Maps every already-searched land cell to its group number |
| 16 | group: Dict[Hashable, int] = {} |
| 17 | count = 0 |
| 18 | |
| 19 | for cell in cells: |
| 20 | # 1. Find An Unlabeled Land Cell: |
| 21 | # A cell with no group yet and is_land(cell) true has not been reached by any |
| 22 | # earlier search, so it starts a brand-new group. |
| 23 | if is_land(cell) and cell not in group: |
| 24 | # A new group: count grows once per search, not per cell |
| 25 | group[cell] = count |
| 26 | stack = [cell] |
| 27 | |
| 28 | # 2. Flood The Whole Group: |
| 29 | # The loop keeps running until stack is empty, so every cell reachable from |
| 30 | # this one is labeled before the outer loop is allowed to move on. |
| 31 | while stack: # Inner search uses up the whole group |
| 32 | curr = stack.pop() |
| 33 | for nxt in neighbors(curr): |
| 34 | if is_land(nxt) and nxt not in group: |
| 35 | group[nxt] = count # Label on push, not on pop |
| 36 | stack.append(nxt) |
| 37 | |
| 38 | # 3. Advance The Group Counter: |
| 39 | # count only changes once the whole group has been labeled, so the next |
| 40 | # brand-new cell starts the next number. |
| 41 | count += 1 |
| 42 | |
| 43 | return group |
"0" belongs to an island already counted in islands, and every "1" left belongs to one not counted yet.Scan every cell, and when you meet a "1" that no search has reached, add one to islands and flood that cell's whole island with the inner stack search. The inner search turns every connected land cell to "0", so the outer scan never meets that island again and counts it exactly once. The trap is where the counter lives: islands += 1 belongs in the outer scan, once per search, never inside the inner loop, where it would count cells instead of islands.
See it run
Counting islands: one search for each unvisited land cell
islands 0
Each circle is a grid cell, and a line joins two neighbouring land cells. A cell that is turned to 0 keeps its place, so you can see which island it belonged to.
nowthe cell the scan or the search is looking aton stacka land cell already turned to 0 that waits for its neighbours to be searchedcounteda land cell of an island that is already counted, turned to 0
The outer scan visits cells row by row. islands starts at 0 and the stack is empty.
Gotcha 1 of 4
- The trap
Gotcha 1: Adding to
islandsinside the inner search loopMistakeif 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1": grid[nr][nc] = "0" islands += 1 stack.append((nr, nc))Fixif 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1": grid[nr][nc] = "0" stack.append((nr, nc))What happens: The outer scan adds 1 to
islandsfor the first cell of an island. The inner loop then adds 1 again for every other cell it reaches. Soislandsends as the number of land cells, not the number of islands.islands += 1belongs in the outer scan, once per new search.Example: Number of Islands (LC 200): grid = [["1", "1"], ["0", "1"]]Mistake: returns 3Fix: returns 1
- Land is added one cell at a time and the count is asked after every addition, as in Number of Islands II (LC 305), so scanning the whole grid again each time is too slow. See Union-Find
Deep Dive
Why one search per unvisited cell counts each island once
A grid is a graph. Each cell is a node, and two cells that touch up, down, left or right are joined by an edge when both are land. An island is a connected component: a set of land cells in which every cell can reach every other cell through land.
The outer scan looks at every cell. When it finds a "1", no earlier search has reached that cell. If an earlier search had reached it, the cell would already be "0". So this cell belongs to an island that is not counted yet, and islands += 1 is right.
The inner search then turns every land cell of that island to "0". It does not stop until stack is empty, and the cells of one island are all connected, so the whole island is turned. The scan can never meet a cell of this island as a "1" again. So each island adds exactly 1.
Example: in Number of Islands (LC 200), the grid [["1","1","0","0"],["0","1","0","1"],["1","0","0","1"]] has 3 islands. The first island is (0, 0), (0, 1) and (1, 1). The second is (1, 3) and (2, 3). The third is (2, 0), which has no land neighbour.
One trace: the scan, the stack and the counter
The board draws the 12 cells of the grid above. A line joins two touching land cells. A cell that turns to "0" stays where it is, so you can see which island it belonged to.
The scan finds a 1 at (0, 0), so islands becomes 1. The search pops (0, 0) and pushes its only land neighbour (0, 1). It pops (0, 1) and pushes (1, 1). It pops (1, 1), which has no land neighbour left. The stack is empty, and the first island is finished.
The scan then reaches (0, 1) and (1, 1). Both are "0" now, so they are not counted again. That is the step marked as the trap on the board.
At (1, 3) the scan finds the second island, and at (2, 0) it finds the third. islands is 3 at the end. The search made 6 pops, one for each land cell.
The trap: where islands += 1 lives
islands counts searches, so it changes once for each search, in the outer scan. If islands += 1 is placed inside the inner loop, it runs once for each cell that is pushed, so it counts cells.
For the grid in the trace, the outer scan adds 3, one for each island. The inner loop adds 1 for each pushed cell: 3 more. The wrong code returns 6. The correct answer is 3.
A second trap is the moment of marking. The blueprint turns a cell to "0" when it is pushed, not when it is popped. If the mark waits until the pop, a cell can be pushed by several neighbours before it is popped. The count is still right, but the stack holds the same cell more than once, and the work grows.
The bounds check must come first: 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1". From the bottom row, nr = R, and grid[R] raises an IndexError. A negative index does not raise an error. It reads the last row, which is worse.
The cost, and the neighbouring card
Each cell is pushed at most once, because it turns to "0" at the push. Each popped cell looks at 4 neighbours. The time is O(R * C), and the space is O(R * C) for the stack in the worst case, a grid of all land.
The blueprint uses a stack and not a recursive dfs. A recursive search on a 40 by 40 island of land goes more than 1000 calls deep, and Python's default limit is 1000. Number of Islands (LC 200) allows grids of 300 by 300.
The same outer loop and inner search work on any graph. Nodes replace cells, and the neighbour list replaces the four directions. Number of Provinces (LC 547) and Number of Connected Components in an Undirected Graph (LC 323) use this shape. Max Area of Island (LC 695) counts the pops of each search and keeps the largest.
When land is added one cell at a time and the count is asked after every addition, as in Number of Islands II (LC 305), a new scan every time is too slow. That problem needs the Union-Find card.
60-Second Pitch
"I treat the grid as a graph. An island is a group of land cells that are connected through up, down, left and right neighbours. I scan every cell. When I find a 1, no search has reached it, so it starts a new island and I add 1 to islands. Then I search from that cell with a stack, and I turn every connected land cell to 0 as I push it. The scan cannot meet that island again, so it counts once. The counter changes only in the outer scan, once for each search. The time is O(R * C), because each cell is pushed at most once, and the space is O(R * C). I use an explicit stack because a recursive search can pass Python's limit on a large island."
Common Questions
- Why do you add to
islandsin the outer scan and not in the inner search? islandscounts the searches. One search covers one whole island, so the scan adds 1 when it starts a search. The inner search runs once for each cell of the island. Adding there would count cells, and the grid[["1","1"],["0","1"]]would return 3 and not 1.- What are the time and space complexity?
O(R * C) time, because each cell is turned to
"0"and pushed at most once, and each pop checks 4 neighbours. The space is O(R * C) for the stack in the worst case, a grid that is all land.- Do you change the input grid? Is that allowed?
The blueprint changes it, because turning a cell to
"0"is the record of visited cells and it needs no extra space. If the input must stay as it is, copy it first, or use a separatevisitedset. The set costs O(R * C) extra space.- How do you change it to find the size of the largest island?
Count the pops of each search, and keep the largest count. The outer scan stays the same. This is Max Area of Island (LC 695). The count of pops of one search is the number of cells in that island.
- When does this approach stop being enough?
When land is added one cell at a time and the island count is needed after every addition, as in Number of Islands II (LC 305). Scanning the whole grid after each addition is too slow. Union-Find keeps the groups and merges them as cells are added.
SWE Reasoning
Spot it
- The task counts or labels separate groups: islands, provinces, regions, rooms you can reach.
- The input is a grid or a graph, and "connected" means touching or linked through neighbours.
- The groups do not change while you count them.
- Each group can be found by starting at one unvisited item and visiting everything it can reach.
- The answer is a count, a label for each item, or the size of the largest group.
The invariant, step by step
- The outer scan looks at the cells one by one.
islandsis the number of searches that have finished. - A cell that is still
"1"has not been reached by any search. A cell reached by a search was turned to"0". - When the scan finds a
"1", it starts one search, andislandsgrows by 1. That is the only place whereislandschanges. - The inner search turns every land cell connected to the start into
"0". It stops only whenstackis empty. - When the search ends, every cell of that island is
"0". Between searches, every"0"that was land belongs to an island already counted, and every"1"belongs to one not counted yet. - The scan ends after the last cell, so every island was found by exactly one search.
islandsis the answer.
Traps
islands += 1inside the inner loop. It counts land cells and not islands.- Marking a cell when it is popped. The same cell is pushed several times. The count is right, and the work grows.
- Reading
grid[nr][nc]before the bounds check. A row past the end raises an IndexError, and a negative index reads the last row. - A recursive
dfson a large island. It goes deeper than Python's limit of 1000. Use astack. - Using 8 directions by mistake. In this problem a diagonal touch does not join cells.
[["1","0"],["0","1"]]has 2 islands.
Practice
Connected Components (Number of Islands / Flood Fill)
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.
Flood Fill
2D grid / graph ➔ outer unvisited discovery ➔ consume full component| 1 | from typing import Callable, Dict, Hashable, Iterable, List |
| 2 | |
| 3 | |
| 4 | def flood_fill(cells: Iterable[Hashable], is_land: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Hashable]]) -> Dict[Hashable, int]: |
| 5 | """Flood Fill: label every land cell with the number of its group of connected land |
| 6 | cells. |
| 7 | Precondition: neighbors is symmetric. If b is a neighbour of a, then a is a |
| 8 | neighbour of b. |
| 9 | Groups are numbered 0, 1, 2, ... in scan order, so the number of groups is |
| 10 | max(group.values()) + 1. |
| 11 | V = cells. T = the cost of one is_land or neighbors call (neighbors yields at most T |
| 12 | cells). |
| 13 | Time: O(V * T) | Space: O(V) |
| 14 | """ |
| 15 | # Maps every already-searched land cell to its group number |
| 16 | group: Dict[Hashable, int] = {} |
| 17 | count = 0 |
| 18 | |
| 19 | for cell in cells: |
| 20 | # 1. Find An Unlabeled Land Cell: |
| 21 | # A cell with no group yet and is_land(cell) true has not been reached by any |
| 22 | # earlier search, so it starts a brand-new group. |
| 23 | if is_land(cell) and cell not in group: |
| 24 | # A new group: count grows once per search, not per cell |
| 25 | group[cell] = count |
| 26 | stack = [cell] |
| 27 | |
| 28 | # 2. Flood The Whole Group: |
| 29 | # The loop keeps running until stack is empty, so every cell reachable from |
| 30 | # this one is labeled before the outer loop is allowed to move on. |
| 31 | while stack: # Inner search uses up the whole group |
| 32 | curr = stack.pop() |
| 33 | for nxt in neighbors(curr): |
| 34 | if is_land(nxt) and nxt not in group: |
| 35 | group[nxt] = count # Label on push, not on pop |
| 36 | stack.append(nxt) |
| 37 | |
| 38 | # 3. Advance The Group Counter: |
| 39 | # count only changes once the whole group has been labeled, so the next |
| 40 | # brand-new cell starts the next number. |
| 41 | count += 1 |
| 42 | |
| 43 | return group |
"0" belongs to an island already counted in islands, and every "1" left belongs to one not counted yet.Scan every cell, and when you meet a "1" that no search has reached, add one to islands and flood that cell's whole island with the inner stack search. The inner search turns every connected land cell to "0", so the outer scan never meets that island again and counts it exactly once. The trap is where the counter lives: islands += 1 belongs in the outer scan, once per search, never inside the inner loop, where it would count cells instead of islands.
See it run
Counting islands: one search for each unvisited land cell
islands 0
Each circle is a grid cell, and a line joins two neighbouring land cells. A cell that is turned to 0 keeps its place, so you can see which island it belonged to.
nowthe cell the scan or the search is looking aton stacka land cell already turned to 0 that waits for its neighbours to be searchedcounteda land cell of an island that is already counted, turned to 0
The outer scan visits cells row by row. islands starts at 0 and the stack is empty.
Gotcha 1 of 4
- The trap
Gotcha 1: Adding to
islandsinside the inner search loopMistakeif 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1": grid[nr][nc] = "0" islands += 1 stack.append((nr, nc))Fixif 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1": grid[nr][nc] = "0" stack.append((nr, nc))What happens: The outer scan adds 1 to
islandsfor the first cell of an island. The inner loop then adds 1 again for every other cell it reaches. Soislandsends as the number of land cells, not the number of islands.islands += 1belongs in the outer scan, once per new search.Example: Number of Islands (LC 200): grid = [["1", "1"], ["0", "1"]]Mistake: returns 3Fix: returns 1
- Land is added one cell at a time and the count is asked after every addition, as in Number of Islands II (LC 305), so scanning the whole grid again each time is too slow. See Union-Find
Deep Dive
Why one search per unvisited cell counts each island once
A grid is a graph. Each cell is a node, and two cells that touch up, down, left or right are joined by an edge when both are land. An island is a connected component: a set of land cells in which every cell can reach every other cell through land.
The outer scan looks at every cell. When it finds a "1", no earlier search has reached that cell. If an earlier search had reached it, the cell would already be "0". So this cell belongs to an island that is not counted yet, and islands += 1 is right.
The inner search then turns every land cell of that island to "0". It does not stop until stack is empty, and the cells of one island are all connected, so the whole island is turned. The scan can never meet a cell of this island as a "1" again. So each island adds exactly 1.
Example: in Number of Islands (LC 200), the grid [["1","1","0","0"],["0","1","0","1"],["1","0","0","1"]] has 3 islands. The first island is (0, 0), (0, 1) and (1, 1). The second is (1, 3) and (2, 3). The third is (2, 0), which has no land neighbour.
One trace: the scan, the stack and the counter
The board draws the 12 cells of the grid above. A line joins two touching land cells. A cell that turns to "0" stays where it is, so you can see which island it belonged to.
The scan finds a 1 at (0, 0), so islands becomes 1. The search pops (0, 0) and pushes its only land neighbour (0, 1). It pops (0, 1) and pushes (1, 1). It pops (1, 1), which has no land neighbour left. The stack is empty, and the first island is finished.
The scan then reaches (0, 1) and (1, 1). Both are "0" now, so they are not counted again. That is the step marked as the trap on the board.
At (1, 3) the scan finds the second island, and at (2, 0) it finds the third. islands is 3 at the end. The search made 6 pops, one for each land cell.
The trap: where islands += 1 lives
islands counts searches, so it changes once for each search, in the outer scan. If islands += 1 is placed inside the inner loop, it runs once for each cell that is pushed, so it counts cells.
For the grid in the trace, the outer scan adds 3, one for each island. The inner loop adds 1 for each pushed cell: 3 more. The wrong code returns 6. The correct answer is 3.
A second trap is the moment of marking. The blueprint turns a cell to "0" when it is pushed, not when it is popped. If the mark waits until the pop, a cell can be pushed by several neighbours before it is popped. The count is still right, but the stack holds the same cell more than once, and the work grows.
The bounds check must come first: 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == "1". From the bottom row, nr = R, and grid[R] raises an IndexError. A negative index does not raise an error. It reads the last row, which is worse.
The cost, and the neighbouring card
Each cell is pushed at most once, because it turns to "0" at the push. Each popped cell looks at 4 neighbours. The time is O(R * C), and the space is O(R * C) for the stack in the worst case, a grid of all land.
The blueprint uses a stack and not a recursive dfs. A recursive search on a 40 by 40 island of land goes more than 1000 calls deep, and Python's default limit is 1000. Number of Islands (LC 200) allows grids of 300 by 300.
The same outer loop and inner search work on any graph. Nodes replace cells, and the neighbour list replaces the four directions. Number of Provinces (LC 547) and Number of Connected Components in an Undirected Graph (LC 323) use this shape. Max Area of Island (LC 695) counts the pops of each search and keeps the largest.
When land is added one cell at a time and the count is asked after every addition, as in Number of Islands II (LC 305), a new scan every time is too slow. That problem needs the Union-Find card.
60-Second Pitch
"I treat the grid as a graph. An island is a group of land cells that are connected through up, down, left and right neighbours. I scan every cell. When I find a 1, no search has reached it, so it starts a new island and I add 1 to islands. Then I search from that cell with a stack, and I turn every connected land cell to 0 as I push it. The scan cannot meet that island again, so it counts once. The counter changes only in the outer scan, once for each search. The time is O(R * C), because each cell is pushed at most once, and the space is O(R * C). I use an explicit stack because a recursive search can pass Python's limit on a large island."
Common Questions
- Why do you add to
islandsin the outer scan and not in the inner search? islandscounts the searches. One search covers one whole island, so the scan adds 1 when it starts a search. The inner search runs once for each cell of the island. Adding there would count cells, and the grid[["1","1"],["0","1"]]would return 3 and not 1.- What are the time and space complexity?
O(R * C) time, because each cell is turned to
"0"and pushed at most once, and each pop checks 4 neighbours. The space is O(R * C) for the stack in the worst case, a grid that is all land.- Do you change the input grid? Is that allowed?
The blueprint changes it, because turning a cell to
"0"is the record of visited cells and it needs no extra space. If the input must stay as it is, copy it first, or use a separatevisitedset. The set costs O(R * C) extra space.- How do you change it to find the size of the largest island?
Count the pops of each search, and keep the largest count. The outer scan stays the same. This is Max Area of Island (LC 695). The count of pops of one search is the number of cells in that island.
- When does this approach stop being enough?
When land is added one cell at a time and the island count is needed after every addition, as in Number of Islands II (LC 305). Scanning the whole grid after each addition is too slow. Union-Find keeps the groups and merges them as cells are added.
SWE Reasoning
Spot it
- The task counts or labels separate groups: islands, provinces, regions, rooms you can reach.
- The input is a grid or a graph, and "connected" means touching or linked through neighbours.
- The groups do not change while you count them.
- Each group can be found by starting at one unvisited item and visiting everything it can reach.
- The answer is a count, a label for each item, or the size of the largest group.
The invariant, step by step
- The outer scan looks at the cells one by one.
islandsis the number of searches that have finished. - A cell that is still
"1"has not been reached by any search. A cell reached by a search was turned to"0". - When the scan finds a
"1", it starts one search, andislandsgrows by 1. That is the only place whereislandschanges. - The inner search turns every land cell connected to the start into
"0". It stops only whenstackis empty. - When the search ends, every cell of that island is
"0". Between searches, every"0"that was land belongs to an island already counted, and every"1"belongs to one not counted yet. - The scan ends after the last cell, so every island was found by exactly one search.
islandsis the answer.
Traps
islands += 1inside the inner loop. It counts land cells and not islands.- Marking a cell when it is popped. The same cell is pushed several times. The count is right, and the work grows.
- Reading
grid[nr][nc]before the bounds check. A row past the end raises an IndexError, and a negative index reads the last row. - A recursive
dfson a large island. It goes deeper than Python's limit of 1000. Use astack. - Using 8 directions by mistake. In this problem a diagonal touch does not join cells.
[["1","0"],["0","1"]]has 2 islands.