# Number of Islands solved three ways, and the follow-ups Source: https://www.techinterview.org/post/3233476038/number-of-islands-three-ways/ Updated: 2026-07-02 · techinterview.org An interviewer slides over a grid of `1`s and `0`s and asks how many islands it contains, where land connects up, down, left, and right but never diagonally. This is LeetCode 200, and it turns up constantly. In one large sample of verified onsite questions it appeared at more than 40 companies, Google, Amazon, Meta, Bloomberg, Citadel, and CrowdStrike among them. The first working solution takes most candidates about five minutes. What separates a strong loop from a forgettable one is everything the interviewer asks after that. Start by naming the structure out loud. Each land cell is a node, and two land cells share an edge when they sit directly next to each other vertically or horizontally. An island is a connected component. Counting islands is counting connected components in a graph you never bother to build explicitly. Once you say that, the interviewer knows you see the shape of the problem, and the three standard approaches drop out of it. ## DFS, the version you should write first Walk the grid cell by cell. When you hit a `1` you have not seen before, add one to the count and flood-fill its entire component, marking every cell so you do not count it twice. The cleanest way to mark is to sink the land: overwrite each visited `1` with `0` as you go. ``` def num_islands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) count = 0 def sink(r, c): if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1': return grid[r][c] = '0' sink(r + 1, c); sink(r - 1, c) sink(r, c + 1); sink(r, c - 1) for r in range(rows): for c in range(cols): if grid[r][c] == '1': count += 1 sink(r, c) return count ``` Time is O(rows times cols), since every cell is touched a constant number of times. The trap is space. Recursion depth can reach O(rows times cols) when the land forms one long snaking component, and on a million-cell grid that overflows the stack in plenty of languages. The other thing worth flagging before you write a line: sinking the grid mutates the input. Some interviewers want the grid left intact, so ask. If they say leave it alone, swap the overwrite for a `visited` set of coordinates and the rest stays the same. ## BFS, when the recursion stack scares you Same flood fill, queue instead of the call stack. This is what you reach for when the grid is huge and might be a single component, because an iterative queue will not blow the stack the way deep recursion does. ``` from collections import deque def num_islands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) count = 0 for r in range(rows): for c in range(cols): if grid[r][c] != '1': continue count += 1 grid[r][c] = '0' q = deque([(r, c)]) while q: x, y = q.popleft() for nx, ny in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)): if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1': grid[nx][ny] = '0' q.append((nx, ny)) return count ``` The detail to say while you type it: mark a cell visited when you enqueue it, not when you dequeue it. If you wait until dequeue, the same cell gets pushed by several neighbors before any of them processes it, the queue balloons, and in a dense grid you can revisit cells enough times to push the work past linear. This is the single most common BFS bug on this problem, and a careful interviewer is watching the exact moment you flip the cell to `0`. The queue here holds only the active frontier, which on a grid stays bounded by roughly O(min(rows, cols)) rather than the whole component, so memory behaves better than the recursive stack. ## Union-find, the one they actually want later For the plain count, disjoint-set union is overkill and runs slower in practice than a flood fill. Interviewers still steer toward it because of where the question is heading. The idea: give every land cell its own set, then union it with the land cell to its right and the one below it. Scanning only right and down avoids doing each merge twice. The answer is the number of distinct roots among land cells, which you can track with a running counter instead of a final pass. ``` class DSU: def __init__(self, n): self.parent = list(range(n)) self.size = [1] * n self.count = 0 def find(self, x): while self.parent[x] != x: self.parent[x] = self.parent[self.parent[x]] # path halving x = self.parent[x] return x def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return if self.size[ra] < self.size[rb]: ra, rb = rb, ra self.parent[rb] = ra self.size[ra] += self.size[rb] self.count -= 1 ``` Path halving in `find` plus union by size gives you near constant time per operation, bounded by the inverse Ackermann function, which is below 5 for any grid you will ever see. Memorize this structure once. It is the same DSU that solves accounts merge, redundant connection, and the friend-circles family, so the cost of learning it amortizes across a dozen problems. ## Number of Islands II, the follow-up that matters This is LeetCode 305, a premium problem, and the real reason anyone drills union-find for this question. The grid now starts as all water, and you receive a stream of positions where land appears one at a time. After each addition you report the current island count. A flood fill cannot keep up: rerunning DFS or BFS after every operation costs O(k times rows times cols) for k additions, and that is the answer an interviewer is hoping you will reject. Union-find handles each addition in near constant amortized time. Turn the new cell into land, bump the count by one as if it were its own island, then union it with whichever of its four neighbors are already land. Every successful merge drops the count by one. ``` def num_islands2(m, n, positions): dsu = DSU(m * n) land = set() res = [] for r, c in positions: if (r, c) in land: res.append(dsu.count) continue land.add((r, c)) dsu.count += 1 idx = r * n + c for nr, nc in ((r+1, c), (r-1, c), (r, c+1), (r, c-1)): if (nr, nc) in land: dsu.union(idx, nr * n + nc) res.append(dsu.count) return res ``` The reason DFS does not stretch to cover this is the point being tested. A flood fill answers a static question about the grid as it stands right now. Union-find answers an incremental one, where connectivity only ever grows and each new edge cheaply tells you whether two regions just became one. When an interviewer at a place like Google or Citadel opens with the basic count, the dynamic version is often the second half of the same slot, and reaching for DSU before they ask is the move that reads as experience. ## The follow-ups behind the follow-up A few more variations show up often enough to rehearse, usually phrased close to these: - "What if the grid is too big to fit in memory?" Process it in horizontal stripes, keeping union-find state only for the boundary row between the stripe you just read and the next one, then stitch components across the seam. - "Now diagonal contact counts as the same island." Eight directions instead of four. The change is trivial, but it quietly checks whether your direction list lives in one place or is copy-pasted across the code. - "Return the area of the largest island." That is LeetCode 695, the same flood fill while you tally cells per component and keep the max. - "The grid is enormous and almost all water." Iterate over the known land coordinates instead of every cell, so the work scales with the land, not the full rows times cols. It helps to have the tradeoffs straight so you can pick out loud rather than defaulting to whatever you wrote last: | Approach | Time | Extra space | Reach for it when | | --- | --- | --- | --- | | DFS (recursive) | O(rows × cols) | O(rows × cols) stack, worst case | You want the answer on the board fastest and the grid is modest | | BFS (queue) | O(rows × cols) | O(min(rows, cols)) frontier | One giant component could overflow the recursion stack | | Union-find | O(rows × cols · α) | O(rows × cols) | Land arrives over time or you are merging streams of grids | If you only memorize the recursive DFS, you clear the first five minutes and then stall on the part that actually moves the rubric. Write the flood fill until it is muscle memory, then spend your real prep time on the dynamic version, because that is where the interviewer learns whether you understand the problem or just remember an answer.