When to use it#
Look for the structural evidence below before naming the pattern. The constraints and invariant - not a keyword - make the choice defensible.
Recognition signals
- Earliest finish
- Best immediate boundary
- No need to revisit
When another approach fits better
- A local choice changes future options in ways the state does not summarize
- No exchange, stay-ahead, or cut-style proof supports commitment
How it works#
Enumerate all choice subsets/orders and evaluate complete outcomes.
Propose the local choice and actively search for a counterexample.
Give an exchange or stay-ahead argument.
Choose ordering and state that make the proof executable in one pass.
InvariantAfter each choice, there exists an optimal completion consistent with every choice made so far.
Example and template#
Jump Game
Requires a crisp invariant for why the farthest reachable point is sufficient.
Open the full problem brief- Reach
current farthest = 4Every index up to the active boundary is reachable.
- Scan candidate
farthest = max(4, i+jump[i])Keep the best future boundary without committing to a full path.
order candidates by proof-relevant key
state = initial boundary
for candidate in order:
if candidate preserves feasibility or improves boundary:
commit candidate
return committed result- Time
- Often O(n log n) for sorting plus O(n) scan
- Space
- Usually O(1) extra beyond output/sort
- Assumptions
- The local-choice proof holds for the exact constraints and sort key.
Pitfalls#
Common wrong approaches
Picking the largest/smallest visible value is not correct without a structural proof.
The code can be locally consistent while violating the exchange argument.
Edge cases
- No feasible solution
- Tied candidates
- Zero-gain choice
- Whether an empty selection is permitted
Interview narration
- “I think this local boundary is safe, and here is the exchange argument.”
- “After each step an optimal completion still agrees with my chosen prefix.”
- “Sorting cost dominates; the scan itself is linear.”
Practice#
Jump Game
Requires a crisp invariant for why the farthest reachable point is sufficient.
Practice this problemSelect the maximum number of nonoverlapping meetings.
Reveal the pattern decision
Choose earliest finish time because replacing any first chosen meeting with it leaves at least as much room for the suffix.
Transfer problem
Assign refueling stops to minimize stop count with stations passed over time.
Checkpoint: Use a max-heap of available fuel; the greedy choice is delayed until additional reach is necessary.
Follow-up variations
- Return the committed choices
- Show a counterexample where the analogous local rule fails
Error-log prompts
- Where was the correctness argument?
- Did the implementation's ordering match the proof?