A grid problem can be a graph problem. A grouping problem can be a problem about equal keys. A question about the smallest feasible capacity can become a search for the first true result of a monotone predicate.
Reduction means building such a translation carefully enough that solving the translated problem gives a valid answer to the original one. The familiar algorithm is useful only if the translation preserves the relationship the question cares about.
Think of using a transit map. It omits the exact shape of streets but preserves the stations and connections needed to plan a journey. A map that accidentally joins two unconnected lines can produce an impossible route. A reduction may omit irrelevant detail, but it must preserve relevant connections.
Name both problems and the bridge between them
“This looks like a graph” is a clue. To turn it into a reduction, answer:
- What is an object in the new representation?
- Which relationships become edges, equalities, or constraints?
- How does an answer in the new representation become the required answer?
- Why does the translation neither invent nor lose valid answers?
Also calculate the translation’s cost. A representation that expands a compact input into billions of objects may erase the benefit of using a familiar solver.
Reduce islands to connected components
The original problem gives a grid of '1' land and '0' water. An island consists of land cells connected by up, down, left, or right steps through land.
Use this mapping:
| Grid concept | Graph concept |
|---|---|
| A land cell | A vertex |
| Two land cells sharing a horizontal or vertical side | An undirected edge |
| A sequence of land steps | A graph path |
| An island | A connected component |
| Number of islands | Number of connected components |
The correspondence works in both directions. Every legal land path becomes a graph path because each step follows an edge. Every graph path becomes a legal land path because edges connect only side-sharing land cells. Thus two land cells belong to the same island exactly when their vertices belong to the same connected component.
Connected-component algorithms explore reachable vertices and start a new exploration whenever they encounter an unvisited component. Princeton’s graph reference describes this component structure and traversal approach. Algorithms, 4th Edition: Undirected Graphs
The reduction tells us what to count: one completed reachability exploration per new component, not one row, one run, or one land cell.
You do not need to build every graph explicitly
The graph can stay implicit. Represent a vertex by its row and column. Generate at most four neighbors when you need them, checking bounds and whether the cell is land.
For a rectangular grid with R rows and C columns, there are at most RC land vertices and only a constant number of incident neighbor relationships per cell. A complete scan plus traversal therefore takes O(RC) time when each land cell is scheduled at most once. A visited structure and a traversal stack can require O(RC) additional space in the worst case.
This is a practical benefit of thinking in representations: recognizing a graph does not require allocating a general graph library object for every cell.
The boundary conditions are part of the translation. In [['1', '0'], ['0', '1']], the diagonal cells are two islands under four-direction connectivity. Adding diagonal edges would solve a different problem. If a variant allows eight directions, then the mapping must change accordingly.
Reduce anagram membership to key equality
Two lowercase English words are anagrams when their character counts match. Sorting the characters creates a canonical representation:
| Word | Key |
|---|---|
eat |
aet |
tea |
aet |
ate |
aet |
tan |
ant |
Why is equality of keys enough? Equal character multisets sort into the same sequence. Conversely, identical sorted sequences contain the same characters with the same multiplicities. The key neither merges different character multisets nor splits equal ones.
Now grouping anagrams becomes grouping equal keys. That is a reusable operation supported by a map.
Notice the difference between the key and the original data. You still keep the original words in each group because those are the requested output. A canonical representation can discard character order for comparison without discarding the word that must be returned.
A character-count vector is another valid key under a specified alphabet. Its serialization must preserve boundaries: simply joining decimal counts without separators can make different vectors indistinguishable. Representation details belong in the correctness argument.
Binary search needs a more precise connection
Searching a sorted array by repeatedly narrowing an interval is the binary-search algorithm itself. It is useful as a pattern, but calling it a reduction without identifying a second problem adds little explanation.
A clearer reduction starts with a different question:
A nonempty list of ordered packages with nonnegative integer weights must be shipped within a positive integer number of days,
D. Each day takes the next consecutive packages up to a capacity. What is the smallest integer capacity that works?
Define feasible(capacity) to mean that a left-to-right packing scan can ship all packages within D days. With nonnegative weights, filling each day with as many next packages as fit uses the fewest days for that fixed capacity: taking fewer today cannot allow more of the ordered prefix to have been shipped by today, and the same argument continues through later days.
If capacity c works, any larger capacity also works; it can at least reproduce the same daily groups. This gives a sequence of false answers followed by true answers. The original optimization problem becomes finding the first true capacity.
For weights [3, 2, 2] and D = 2, capacity 3 needs three days, while capacity 4 permits [3] then [2, 2]. The minimum is 4. Search bounds can begin at the heaviest package and end at the sum of all weights.
The important reduction is minimum capacity → first true value of a monotone feasibility test. The feasibility scan is still work: if it takes O(n) and the integer search range has W candidates, the overall search costs O(n log W), not merely O(log W).
Keep cue scan, decomposition, and reduction distinct
| Move | Question | Islands example |
|---|---|---|
| Cue scan | What facts does the wording give me? | Land connects through four specified directions |
| Decompose | Which smaller responsibilities can I solve? | Scan for a starting cell; explore its reachable land |
| Reduce | Which known problem preserves this task? | Islands correspond exactly to graph components |
You may perform all three while designing the same solution. Their boundaries help you notice what remains unproved: a cue is not a mapping, and a mapping is not yet an implementation.
Outside exercises, canonicalization appears when grouping equivalent records from different sources. Deciding to ignore letter case or whitespace changes which records become equal. Before normalizing, ask whether that distinction is genuinely irrelevant under the contract.
Practice the move
A network contains people and undirected “knows” relationships. You must count groups linked by chains of acquaintances. Identify the vertices, edges, and answer mapping.
People become vertices, relationships become edges, and acquaintance groups become connected components. Physical proximity or shared names should not create edges unless the problem says they do. The solver transfers because the relationships match, not because the story sounds similar.