A strong answer
The standard solution scans every cell; each unvisited land cell starts a new island, and a flood fill (DFS or BFS) marks all land connected to it. Each cell is visited a constant number of times, so it is O(R × C) time, with the grid itself or a boolean array as the visited set.
At 10¹⁰ cells several things change:
- Recursion depth. A recursive DFS on one huge island can go billions of calls deep. Use BFS or an explicit stack, so the pending work lives on the heap.
- Memory. The grid alone is 10 GB at one byte per cell. Store it as bits, and avoid a separate visited structure by marking in place, if mutation is allowed.
- Streaming. If the grid arrives row by row, process two rows at a time with union-find: label each land cell, union it with land to its left and above, and count components. When a row is finished, any label that no longer touches the current row is a complete island and can be counted and forgotten, so memory is proportional to one row.
- Parallelism. Split the grid into tiles, count islands inside each tile with a flood fill, and record the labels of land on tile borders. Then merge across borders with union-find: two border cells that are adjacent and both land join their islands. The total is the number of union-find sets after merging.
What the interviewer is listening for
- The O(R × C) flood fill, with visited marking.
- Concrete limits at scale: stack depth, memory, input size.
- A row-by-row or tiled design, typically with union-find to merge components.
Common mistakes
- Ignoring recursion depth.
- Proposing to load the whole grid into memory without checking its size.
- Forgetting islands that span tile boundaries.