STEP 15 · GRAPHS · LABEL ONCE, QUERY CHEAPLY · HARD

Making A Large Island

WHAT IT SAYS

You may flip at most one 0 to 1 in a binary grid; return the largest island achievable.

WHAT IT'S REALLY ASKING

"Flipping a zero glues together whatever islands touch it — its merged size is 1 plus the sizes of its DISTINCT neighbouring islands. Every candidate zero asks the same two questions of its neighbours: which island are you, and how big is that island. So answer those questions ONCE for the whole grid — stamp every island with an id and record its size — and each of the m·n candidates becomes four map lookups."

THE INSIGHT LADDER — FROM BRUTE FORCE TO OPTIMAL

Flip each zero and re-measure

O((mn)²) — a full flood per candidate zero

For every 0-cell: flip it, flood-fill from it to measure the island it now belongs to, record the size, unflip; also measure the no-flip baseline. Return the maximum.

WHERE THE WORK IS WASTED — Adjacent candidate zeros re-measure the SAME islands over and over: a large island bordered by a hundred zeros is flooded a hundred times, each flood re-deriving a size that never changes between trials. The queries share almost all their work — every trial's answer decomposes into 'sizes of the fixed islands around me' — yet each trial starts amnesiac and re-explores from scratch. The signature is unmistakable: many queries, each needing a few facts from a STATIC underlying structure. That shape demands a precompute/query split, and re-flooding is what refusing the split costs — quadratic in the grid, against linear for the split.

KEY OBSERVATION — THE UNLOCKlink

Component ids and sizes are the whole vocabulary — precompute them.

Phase one — labelling: one pass over the grid flood-fills each undiscovered island, stamping every cell of island k with id k (write ids ≥ 2 directly into the grid, since 0 and 1 are taken — the output-as-storage economy again) and recording size[k]. Total cost: each cell visited once, O(mn). After this pass, the two questions any algorithm could ask about the static landscape — 'whose cell is this?' and 'how big is that one?' — are O(1) array reads. Phase two — querying: for each 0-cell, its post-flip island is itself plus every island it touches, fused. Collect the ids of its four neighbours into a small SET — the deduplication is load-bearing, not defensive: a zero wedged into a U-shaped island sees the same id from two or three sides, and summing per-neighbour instead of per-distinct-id counts that island multiple times, the single classic bug of this problem. Candidate size = 1 + Σ size[id] over the distinct ids. Four lookups, a set of at most four elements, O(1) per candidate — m·n candidates, O(mn) total. Two boundary cases the phases hand you if you let them: no zeros at all means no flip is possible — the answer is the largest existing island (track it during phase one, or note the all-ones grid answers m·n); and the baseline of 'flip nothing' is subsumed by tracking the max original size alongside the candidates. Name the architecture, because it is the reusable part: this is INDEXING — one linear pass converts the raw grid into a queryable form (id map + size table), and the question's m·n instances each consume the index instead of the raw data. The same split powers the histogram-before-queries, prefix-sums-before-range-queries, and parent-map-before-distance-K moves. The failed approach wasn't wrong to decompose each trial into neighbour-island sizes — it was wrong to recompute the decomposition's ingredients per trial when they were shared, static, and one pass from permanent.

Stamp ids and sizes, then evaluate every zero via a distinct-id sum

O(m·n) time — one labelling pass plus one query pass — O(m·n) for ids and sizes

Pass one: for each cell containing 1 with no id yet, flood-fill writing id (starting at 2) and counting size[id]; track the max original size. Pass two: for each 0-cell, gather distinct neighbour ids, compute 1 + their sizes' sum, update the answer. Return the max (grid of all 1s: m·n).

WHAT YOU TRADED — The index is rented from the grid's IMMUTABILITY between queries — the moment flips become real and sequential (islands actually merging as you go), the static id map rots and union-find's incremental contract takes over (Number of Islands II is exactly that turn of the dial); and writing ids into the grid saves memory at the cost of destroying the input. The transferable lesson: when many queries each need a few facts about shared static structure, build the index first — one pass to make every future question O(1) — and let the query count, not the data size, dominate the second phase.

WATCH THE IDEA RUN

phase label islands once

best island after one flip 0

The brute force flips each 0 and re-floods the whole grid to measure the result — O((mn)²), and it re-discovers the same islands over and over for every candidate.

step 1 / 12

THE PATTERN — SO YOU RECOGNIZE IT NEXT TIME

Index the Static, Query the Candidates

YOU'LL SEE IT AGAIN WHEN

Many what-if candidates, each evaluated from a few facts (ids, sizes, counts) about a structure that does NOT change between candidates.
Naive per-candidate recomputation re-derives shared facts — the cost multiplies queries by data size instead of adding them.
Per-query aggregation must deduplicate (distinct ids), because one underlying object can border a candidate from several directions.

SAME BLUEPRINT, DIFFERENT PROBLEM

Number of Islands II (the same landscape gone genuinely dynamic)All Nodes Distance K (parent-map as the precomputed index)Max Area of Island (phase one alone)Count Sub Islands

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