Given a grid of "1" (land) and "0" (water), return the number of islands: groups of land cells connected horizontally or vertically.
Before you code
Scan the grid. Every time you meet land you haven't seen, you have found a new island, and a flood fill from there marks all of it.
Hints
- Count, then flood with DFS, changing "1" to "0" (or another mark) as you go.
- Mark a cell before recursing into its neighbors.
- For very large grids, use an explicit stack or BFS to avoid deep recursion.
Production & complexity notes
When solving Number of islands on LeetCode (medium), always state your loop or recursion invariant before writing code. Verify how your chosen data structure behaves on degenerate inputs (single-element inputs, all-duplicate keys, strictly monotonic sequences, or maximum constraint sizes up to $10^5$ elements). In production interviews, pair your implementation with an explicit time and auxiliary space complexity proof, explain why alternative brute-force approaches violate the latency budget, and trace how cache locality and memory allocation overhead affect wall-clock throughput on real hardware. Review the step-by-step memory trace in Depth-first search to reinforce the underlying pattern.
What it practices
Flood fill and counting regions, from Depth-first search.