Number of Islands
Problem statement
You are given a grid where each cell is '1' (land) or '0' (water). Count the islands. An island is a group of land cells joined by up, down, left or right steps; diagonal cells don't join. Everything outside the grid counts as water.
Return the number of separate islands.
Think of each '1' as a healthy host in a rack map and each '0' as a failed or empty slot: the question becomes "how many separate groups of connected hosts are left?"
Examples
Example 1
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Explanation: Every '1' can reach every other '1' through up/down/left/right steps, so they all form a single island.
Example 2
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Explanation: The 2 × 2 block at the top left is one island, the single '1' in the middle is a second, and the two '1's at the bottom right are a third. They only touch diagonally, so they stay separate.
Hints
Approach
Optimal: Union-find
Intuition
Turn the question around. Start by assuming every land cell is its own island, so the count equals the number of '1's. Now look at each pair of land cells that sit next to each other. If they are in different islands, merge the two islands into one — and the count drops by one.
A union-find (disjoint-set) keeps track of which island each cell belongs to. Number each cell r * cols + c. Every cell points to a parent, and following parents leads to the island's representative, its root. find returns the root; union attaches one root under the other. We only need to check the neighbour below and the neighbour to the right: the scan reaches every adjacent pair that way exactly once.
Steps
- Give every cell
parent = itself,size = 1. Setcountto the number of'1'cells. - For each land cell
(r, c):- If the cell below is land,
unionthem. - If the cell to the right is land,
unionthem.
- If the cell below is land,
- In
union(a, b): find both roots. If they are the same, do nothing. Otherwise attach the smaller group's root under the larger one and subtract 1 fromcount. - Return
count.
Dry run
Example 2 starts with count = 7 (seven '1' cells).
| cell | union with | merged? | count |
|---|---|---|---|
| (0,0) | below (1,0), right (0,1) | yes, yes | 5 |
| (0,1) | below (1,1) | yes | 4 |
| (1,0) | right (1,1) | no — already one group | 4 |
| (3,3) | right (3,4) | yes | 3 |
(2,2) has no land below or to its right. Answer: 3.
Complexity
Time O(m·n·α(m·n)) - We look at each cell once and try at most two unions (with the cell below and the cell to the right). With path halving and union by size, each union or find costs α, the inverse Ackermann function, which is at most 4 for any real grid. So in practice it is linear in the number of cells, like DFS and BFS.
Space O(m·n) - We store one parent and one size for every cell. There is no stack or queue. The input grid is not changed.
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
parent = list(range(rows * cols))
size = [1] * (rows * cols)
count = sum(row.count("1") for row in grid)
def find(x: int) -> int:
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a: int, b: int) -> None:
nonlocal count
ra, rb = find(a), find(b)
if ra == rb:
return
if size[ra] < size[rb]:
ra, rb = rb, ra
parent[rb] = ra
size[ra] += size[rb]
count -= 1
for r in range(rows):
for c in range(cols):
if grid[r][c] != "1":
continue
if r + 1 < rows and grid[r + 1][c] == "1":
union(r * cols + c, (r + 1) * cols + c)
if c + 1 < cols and grid[r][c + 1] == "1":
union(r * cols + c, r * cols + c + 1)
return count
if __name__ == "__main__":
g1 = [list("11110"), list("11010"), list("11000"), list("00000")]
g2 = [list("11000"), list("11000"), list("00100"), list("00011")]
print(Solution().numIslands(g1)) # 1
print(Solution().numIslands(g2)) # 3RecapThe whole problem in a few lines, for the night before
- Spot it: count separate groups of connected cells (or nodes) in a grid
- Idea: scan every cell; on new land, count it and sink / mark its whole island with DFS or BFS
- Cost: O(m·n) time, O(m·n) space in the worst case
- Trap: recursive DFS on a big all-land grid overflows the stack — use an explicit stack or BFS; and mark cells when you push them, not when you pop
- Remember: union-find handles the "land keeps being added" follow-up
Interview follow-ups
Return the size of the largest island instead of the count.
Keep the same scan. During each island's DFS or BFS, count how many cells you mark, and keep the largest count seen. Time and space stay O(m·n). This is LeetCode's "Max Area of Island".
Land cells are added one at a time. Report the island count after each addition.
Use union-find. When a cell becomes land, add 1 to the count, then union it with each of its up to four land neighbours; each successful union subtracts 1. Each addition costs near O(1), instead of O(m·n) for a full rescan. Watch out for a cell that is added twice — skip it the second time.
The grid is too big for one machine (for example, a 1,000,000 × 1,000,000 map).
Split it into tiles and count islands inside each tile on separate workers. Islands that touch a tile border may be the same island as one in the next tile, so record the labels of border cells. A final step union-finds labels that touch across borders and subtracts the merges from the total.
Frequently asked questions
Every cell has to be looked at at least once, so O(m·n) is the best possible, and all three approaches reach it. A "slower" version would only be a buggy one, such as re-exploring islands you've already counted. The approaches differ in what they trade: in-place marking vs. leaving the input intact, and walking vs. merging.
A recursive DFS is shorter and is accepted on LeetCode. But an all-land 300 × 300 grid can make it 90,000 calls deep. Python's default limit is 1,000, and Java or C++ can also run out of stack on large inputs. An explicit stack keeps the same visiting logic with none of that risk, which is what you'd want in production code.
It depends on the interviewer, so ask. Sinking land to '0' saves the O(m·n) visited grid and is the common interview answer. If the caller still needs the grid afterwards, use a visited grid (the BFS approach) or copy the grid first. Saying this trade-off out loud earns points.
When land keeps appearing and you need the island count after every change. Union-find adds a cell with at most four unions, near O(1), instead of rescanning the grid. For one count on a fixed grid, DFS or BFS is simpler and just as fast. That "count after each addition" version is the harder LeetCode problem Number of Islands II.
Counting connected groups is how you find network partitions, clusters of related alerts, or separate failure domains after an outage. The grid is just a friendly shape for the same question: "how many disconnected pieces is this system in?" It also checks that you can write a graph walk without bugs or stack overflows.