Coding · Union-find
Number of Islands II
- Appears on company lists
- Hard
- 3 sources
Company-tagged lists or prep guides name it; no candidate write-up was found.
Solve it in the playground, with tests
A grid with m rows and n columns starts as all water. You are given a list of cells that turn into land one at a time. After each addition, report how many islands exist, where an island is a group of land cells joined up, down, left or right. On a 3 by 3 grid, adding (0,0), (0,1), (1,2), (2,1), (1,1) gives [1,1,2,3,1]. A cell can appear twice, and adding land that is already land changes nothing. Assume up to 100,000 additions on a grid with up to a million cells.
Restated in our own words, not a quote from Uber or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: how big can the grid and the list of additions be? Can the same cell be added twice? Are diagonal cells connected (I assume not: four directions only)? Do I need the count after every addition, while the list streams in, or only at the end? Can land ever be removed? Are the positions always inside the grid?
I would assume the answer is wanted after every step, additions only, duplicates possible, positions valid, and a grid large enough that rebuilding it on every step is out of the question.
Brute force
Say the obvious answer and why it is too slow.
After each addition, run a flood fill over the whole grid and count the groups. One count costs O(m · n), so k additions cost O(k · m · n). With a million cells and a hundred thousand additions that is about 10^11 cell visits, far beyond a few seconds.
Even a cleverer version that only floods from the new cell has to walk the entire island it joins, which can be huge, and it still has to find out whether two neighbours were already the same island. The slow part is that we keep rediscovering connectivity we already knew.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(k · m · n)
- Time
- O(k · α(k))
- Space
- O(k)
The pattern is union-find with online updates. Land is only ever added, so islands can merge but never split. That is exactly what a disjoint-set structure does well: it supports "merge two groups" and "which group is this cell in" in nearly constant time.
Keep a running island count. When a cell becomes land and it was not land before, it starts as its own group, so add one. Then look at its four neighbours. For each neighbour that is already land, ask the structure to join the two groups. If they were different groups, the join really merged two islands, so subtract one. If they were already the same group, nothing changes. After the four neighbours, the count is the answer for this step.
The invariant is that the count equals the number of distinct group roots among all land cells. Each addition adds one group and each successful merge removes one, so the invariant survives every step. A cell that is already land must be skipped, otherwise we would add a phantom island.
Two standard tricks make find nearly O(1): path halving (while walking up, point each node at its grandparent) and union by size (hang the smaller group under the larger one). Together the amortised cost per operation is the inverse Ackermann function, which is at most 4 or 5 for any real input. I store the parent links in a Map keyed by row * columns + column, so memory grows with the number of added cells, not with the grid, and Map lookups cost O(1) on average. Out loud: "each land cell is a new island, and each successful union removes one."
Walk it through
A dry run on the example, step by step.
| step | add | land neighbours | merges | islands |
|---|---|---|---|---|
| 1 | (0,0) | none | 0 | 1 |
| 2 | (0,1) | (0,0) | 1 | 1 |
| 3 | (1,2) | none | 0 | 2 |
| 4 | (2,1) | none | 0 | 3 |
| 5 | (1,1) | (0,1) (1,2) (2,1) | 3 | 4 - 3 = 1 |
On the 3 by 3 grid, add (0,0): no land neighbours, count 1. Add (0,1): its neighbour (0,0) is land and in a different group, so one merge cancels the new island and the count stays 1. Add (1,2): all of its neighbours are still water, so count 2. Add (2,1): again no land neighbours, count 3.
Add (1,1): the count first rises to 4. Its neighbours (0,1), (1,2) and (2,1) are land, and they belong to three different groups, so three successful merges bring the count to 1. The trace shows every step; the result is [1,1,2,3,1].
The code
Runnable JavaScript, checked against test cases.
function numIslands2(rows, cols, positions) {
const parent = new Map();
const size = new Map();
const find = (cell) => {
while (parent.get(cell) !== cell) {
parent.set(cell, parent.get(parent.get(cell)));
cell = parent.get(cell);
}
return cell;
};
const union = (a, b) => {
let rootA = find(a);
let rootB = find(b);
if (rootA === rootB) return false;
if (size.get(rootA) < size.get(rootB)) [rootA, rootB] = [rootB, rootA];
parent.set(rootB, rootA);
size.set(rootA, size.get(rootA) + size.get(rootB));
return true;
};
const counts = [];
let islands = 0;
for (const [row, col] of positions) {
const cell = row * cols + col;
if (!parent.has(cell)) {
parent.set(cell, cell);
size.set(cell, 1);
islands++;
for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
const r = row + dr;
const c = col + dc;
const inside = r >= 0 && r < rows && c >= 0 && c < cols;
if (inside && parent.has(r * cols + c) && union(cell, r * cols + c)) islands--;
}
}
counts.push(islands);
}
return counts;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- Duplicate addition: the cell is already in the parent map, so we skip all the work and repeat the current count.
- Empty list: the loop never runs and the result is an empty array.
- Border cells: the neighbour test checks the row and column against the grid size before it looks anything up.
- Two neighbours in one island: the second join finds equal roots, returns false, and the count is not reduced twice. This happens when the new cell closes a loop.
- 1 by 1 grid: one cell, no neighbours, the count is 1 and stays 1 for repeats.
- Key size: row * columns + column must stay below 2^53 so it is exact as a JavaScript number.
Follow-ups to expect
Where the interviewer pushes next.
- How would you support removing a land cell, and why does plain union-find fail there?
- If all the additions are known up front, how could you handle removals by processing them in reverse?
- Would you use an array or a Map for the parent links if the grid is a million by a million, and why?
- How would you also report the size of the largest island after each step?
Where candidates slip
The mistakes this problem punishes.
Common mistakes on this problem:
- Not skipping a cell that is already land, which counts an extra island for a duplicate.
- Decreasing the count for every land neighbour instead of only for unions that really merged two groups.
- Calling find on a water cell, or never marking the new cell as its own parent.
- Encoding the cell as row * rows + column, which collides when the grid is not square.
- Skipping both path compression and union by size, so chains grow long and finds get slow.
- Recomputing the count by scanning all roots after each step instead of maintaining it.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.