The static count is a flood fill
Treat each land cell as a node and each pair of land cells that touch on a side as an edge. An island is then a connected component, and the number of islands is the number of components. The BFS or DFS choice does not matter for correctness here, because you only need to reach every cell once.
int numIslands(char[][] grid) {
int rows = grid.length, cols = grid[0].length, count = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
Deque<int[]> stack = new ArrayDeque<>();
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] != '1') continue;
count++;
grid[r][c] = '0';
stack.push(new int[] {r, c});
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int[] d : dirs) {
int nr = cell[0] + d[0], nc = cell[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == ) {
grid[nr][nc] = ;
stack.push( [] {nr, nc});
}
}
}
}
}
count;
}
The explicit stack is deliberate. A recursive DFS on a 1,000 by 1,000 grid that is all land can recurse up to a million frames deep, which overflows a default thread stack. Overwriting the grid saves a visited array, but it destroys the input. Say so, and offer a separate boolean[][] if the caller needs the grid back.
Rerunning per addition is the baseline to beat
Now cells turn from water to land one at a time, and you report the count after each change. The obvious answer is to recompute the number of islands with a fresh flood fill after every addition. With k additions on an R × C grid, that is O(k × R × C). If both k and R × C are around ten thousand, that is a hundred million cell visits, and most of them confirm nothing has changed.
Each addition is local. A new land cell can only join the islands of its four neighbours, and joining sets is the one operation union-find makes cheap.
Union-find makes each addition local
Keep a parent array over cell ids, r * cols + c, with a sentinel meaning "water". When a cell becomes land:
- If it is already land, the count does not change. Report it and move on.
- Otherwise make it its own set and add one to the count.
- For each of its four neighbours that is land, find both roots. If the roots differ, union them and subtract one. If they match, do nothing.
Trace it on a 3 × 3 grid with additions at (0,0), (0,1), (1,2), (2,1) and then (1,1). The first cell gives 1. The second joins it, so the count stays 1. The next two land apart from everything, giving 2 and then 3. The centre cell then touches three separate islands. It adds one and removes three, so the count is 1.
Decrement on a merge, not on a neighbour
Two small mistakes give wrong counts, and both pass the obvious samples.
The first is subtracting one for every land neighbour. Picture an upside-down U: land at (0,0), (0,1), (0,2), (1,0) and (1,2). That is one island. Add (1,1), and it touches three land cells that already share a root. The correct count stays 1. Subtracting once per neighbour gives 1 + 1 − 3 = −1. The a == b check is the line that matters, and it is why the root lookup cannot be skipped.
The second is adding the same position twice. Real input streams repeat, and without the already-land guard the count rises by one for an island that does not exist. The new cell then becomes a fresh root, overwriting the parent link the old one had.
What the amortised cost is made of
Each addition does one make-set and at most four unions, so the total is O(R × C + k × α(R × C)) time. Here α is the inverse Ackermann function, which is at most four for any input that fits in memory. The R × C term is the parent array, which you can avoid by keying a hash map on the cell id when the grid is huge and sparse.
That bound needs both optimisations together. Union by rank alone keeps trees at logarithmic height, so a find costs O(log n). Path compression alone gives O(log n) amortised. Together they give the near-constant amortised bound, which is Tarjan's result. The path halving in the code is a one-pass form of path compression with the same bound, and it avoids a recursive find. The word is amortised: a single find can still walk a long path, and the compression it does is what pays for later finds.
The count changes in exactly two places: plus one when a new cell becomes land, minus one when a union joins two different roots. Every bug in this problem breaks one of those two rules.
© 2026 Preptima. Originally published at preptima.com (opens in a new tab).