Greedy Techniques — How the Pattern Works
Greedy algorithms construct a globally optimal solution incrementally by committing to the locally best choice at each step without backtracking. Correctness relies on two properties—greedy-choice safety (verified via an exchange argument showing no alternative decision yields a strictly better downstream state) and optimal substructure. When both hold, greedy techniques collapse exponential O(2^n) or O(n!) searches and O(n^2) dynamic programming tables into O(n) single/dual-pass scans or O(n log n) sort-and-heap passes.
- Optimization prompts requesting a minimum or maximum count, cost, profit, or numerical/lexicographical value where candidates admit a strict ranking (by value, marginal delta a - b, or pairwise concatenation order).
- Reachability or minimum-jump interval problems where reaching index r automatically makes every earlier index 0..r reachable.
- Capacity-constrained pairing, assignment, or circular prefix-sum problems where an exchange argument proves matching extremes (lightest with heaviest) or discarding negative-balance prefixes never eliminates an optimal solution.
- Deferred-selection or sequence-minimization problems where past options can be buffered in a max-heap or monotonic stack and committed/evicted only when fuel runs short or an inversion appears.
- Directional boundary or two-neighbor inequality problems where right-hand limits constrain left-hand splits (right-to-left scan) or independent left and right passes resolve bidirectional constraints.
- Assuming greedy works without proving the exchange property: on non-canonical coin systems like [6, 5, 1] for target 10, greedy picks 6 + 1 + 1 + 1 + 1 (5 coins) instead of the optimal 5 + 5 (2 coins), which requires dynamic programming.
- Sorting by raw value instead of marginal difference or custom pairwise order: Two City Scheduling must sort by costA - costB rather than costA, and Largest Number must compare b + a vs a + b rather than numeric value.
- Breaking ties on the wrong side or forgetting leading-zero normalization: Maximum Swap must swap with the rightmost occurrence of the largest suffix digit (1993 -> 9913, not 9193), while Largest Number, Largest Palindromic Number, and Remove K Digits must collapse leading zeros ('00' -> '0').
- Scanning in the wrong direction when constraints propagate asymmetrically: upper-bounded array splitting (Minimum Replacements) requires a right-to-left scan, whereas bidirectional neighbor rules (Candy) require both a left-to-right pass and a right-to-left pass combined with max.
def greedy_reach_scan(nums):
reach = 0
for i, step in enumerate(nums):
if i > reach:
return False
reach = max(reach, i + step)
return Truedef sort_and_pair(items, limit):
items.sort()
left, right = 0, len(items) - 1
groups = 0
while left <= right:
if items[left] + items[right] <= limit:
left += 1
right -= 1
groups += 1
return groupsimport heapq
def deferred_greedy(target, fuel, stations):
reach, i, stops, passed = fuel, 0, 0, []
while reach < target:
while i < len(stations) and stations[i][0] <= reach:
heapq.heappush(passed, -stations[i][1])
i += 1
if not passed:
return -1
reach -= heapq.heappop(passed)
stops += 1
return stopsdef remove_k_inversions(seq, k):
stack = []
for ch in seq:
while k > 0 and stack and stack[-1] > ch:
stack.pop()
k -= 1
stack.append(ch)
return stack[:-k] if k else stack