STEP 15 · GRAPHS · IMPLICIT GRAPH, SINK AS YOU COUNT · MEDIUM

Number of Islands

WHAT IT SAYS

Count the islands in a binary grid, where an island is a group of 1s connected horizontally or vertically.

WHAT IT'S REALLY ASKING

"Nobody hands you nodes and edges — the grid IS the graph, with neighbours reachable by ±1 arithmetic on coordinates, no adjacency list ever built. And the visited set? Sink each island as you discover it — flip its 1s to 0s — and the input becomes its own bookkeeping. Count the launches; each one is a new island announcing itself."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Extract the graph, then count components

O(m·n) time — but with an O(m·n) construction phase and two parallel structures

Convert the grid into an explicit graph: number each land cell, build an adjacency list by linking each to its land neighbours, allocate a visited array, then run the standard component-counting traversal over the constructed structure.

WHERE THE WORK IS WASTED — The adjacency list stores what coordinate arithmetic already knows: cell (r, c)'s neighbours are (r±1, c) and (c±1, r) — four additions and bounds checks, computable on demand, forever. Materialising them trades a formula for a data structure, paying allocation, indirection, and a node-numbering scheme to translate between grid positions and graph indices — translation layers being where off-by-ones breed. The visited array is the second redundancy: the grid cell itself has a spare state (water) that a processed land cell can adopt, making the input its own marker. Two structures built; zero information added.

KEY OBSERVATION — THE UNLOCKlink

Neighbours are arithmetic; visited is mutation; islands are launches.

Three economies stack, and together they compress this problem to a dozen lines. First, the implicit graph. A graph algorithm needs exactly two capabilities: enumerate a node's neighbours, and test node validity. On a grid both are formulas — neighbours by offset arithmetic on (r, c), validity by bounds-plus-value check. DFS and BFS consume neighbours one at a time and never ask for the global edge set, so the adjacency list was answering a question no traversal asks. This is the same move as Word Ladder's mutate-and-lookup: generate neighbours at the moment of need, from the state itself. Grids, word graphs, sliding puzzles — implicit graphs all, and building them explicitly is always the beginner's tax. Second, sinking. The traversal must not revisit; the standard answer is a visited array; the grid's answer is better: a visited land cell becomes water ('1' → '0'), after which the validity formula itself — 'is this cell a 1?' — rejects it. Flood Fill's output-as-marker trick, except here the mutation isn't even the deliverable, just recycled storage. One subtlety carried over: mark on ENQUEUE (or first touch), not on dequeue, or two frontier cells race to enqueue the same neighbour twice. Third, counting by launches — the Provinces logic transplanted to the implicit setting. Each traversal launched from an unsunk land cell consumes exactly one maximal island (exhaustive by construction, contained because reachability defines the island), and the sweep guarantees every island is met at its first-scanned cell while still unsunk. Launches and islands correspond one-to-one; the counter counts launches. The traversal does no 'computation' at all — discovery IS the event, sinking IS the record, and the answer is how many times discovery fired.

Sweep, launch on land, sink the island

O(m·n) time — each cell touched a constant number of times — O(m·n) worst-case frontier, O(1) beyond it

For each cell: if it holds '1', increment the count and flood-sink from it — iterative stack/queue turning every reachable '1' to '0' via 4-neighbour offsets with bounds checks. Return the count. (Recursion works but a grid-length snake of land recurses m·n deep; the explicit stack is the production choice.)

WHAT YOU TRADED — Sinking destroys the input — copy first or count-and-restore if the grid outlives the call, at which point the visited array un-retires; and the implicit-graph economy is rented from the regularity of grids: irregular adjacency (real networks) genuinely needs the list. The transferable lesson: before building graph infrastructure, ask what the algorithm actually consumes — traversals need only next-neighbours and validity, both of which regular state spaces provide as formulas, and the input's spare states often provide the marking for free.

WATCH THE IDEA RUN

launches = islands 0

visited set the grid itself

There is no graph here. Nobody handed you nodes or an edge list — just a rectangle of digits. So build the graph out of nothing: a cell's neighbours are (r±1, c) and (r, c±1). Adjacency is arithmetic, not a lookup.

step 1 / 30

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Formulas Over Structures

YOU'LL SEE IT AGAIN WHEN

The 'graph' is a regular state space — grid, board, word set — where neighbours are computable by O(1) arithmetic on the state itself.
The traversal consumes neighbours on demand and never queries the global edge set, so materialising adjacency adds cost without information.
Processed elements can adopt a spare input state (sink to water, delete from set), letting the validity test double as the visited check.

SAME BLUEPRINT, DIFFERENT PROBLEM

Number of Provinces (the explicit-adjacency twin — count launches there too)Flood Fill (the sinking mechanism isolated)Max Area of Island (same traversal, measure instead of count)Surrounded Regions

The bar isn't "solved it once." It's "could rebuild it from the observation."