patternDSA/Greedy Algorithms

Core Pattern → Pattern 24

Greedy Algorithms

At each step, make the locally optimal choice and never look back. No exhaustive search, no memoization. Provably correct when the greedy choice property holds — swapping a greedy choice for any other can't improve the result.

Frequency:★★★★☆

·~30 min·Intermediate·6 problems

Prev Subsets

The Core Shock

DP explores every possibility. Greedy makes one irrevocable choice per step and never looks back — and provably gets the optimal answer.

Dynamic Programming

Explore all

Try every subproblem, cache results. Correct for overlapping subproblems — but O(n²) or O(n·k) time and space.

Greedy

Choose once

Sort + scan. One pass. Each decision is final and locally optimal. O(n log n) or O(n) — nothing cached.

Greedy works when the problem has the greedy choice property: choosing the locally best option at each step leads to a globally optimal solution. Prove it with the exchange argument — assume an optimal solution doesn't include your greedy choice, then show swapping your choice in doesn't make things worse.

The Exchange Argument

The proof template — almost every greedy problem uses this.

Suppose there is an optimal solution OPT that differs from greedy solution G at some step. Greedy chose X; OPT chose Y (where X ≠ Y). Show that swapping Y for X in OPT produces a solution that is at least as good as OPT. This means X is safe to choose — the greedy step never loses.

Pair Chain (sort by end)

OPT picks interval A with end_A > end_B (ours). Swap A for B — B ends sooner, leaving at least as much room for future intervals. Chain length unchanged.

Parentheses balance

Greedily match ')' with nearest available '(' — any delay in matching only risks having no '(' available later. Matching early is always safe.

Remove Duplicate Letters

If we can pop a larger char (it appears later), doing so now puts a smaller char earlier = lexicographically better. Never worse.

Largest Palindromic Number

Using higher digits in the half gives a larger number. Using one odd-frequency digit as center adds one digit. Both locally maximal choices are globally optimal.

The 3-Step Framework

Sort → scan → decide — 95% of greedy problems follow this shape.

Identify the greedy criterion and sort

What ordering makes local choices lead to global optimum? For intervals: sort by end time (leaves max room). For frequency problems: sort by count descending. For string construction: process digits/chars in value order. The sort is almost always the key insight.

# Intervals: sort by end
pairs.sort(key=lambda x: x[1])

# Frequency: Counter + sorted keys
for d in '9876543210': ...

# Stack greedy: last occurrence map
last = {ch: i for i, ch in enumerate(s)}

If you're unsure of the criterion, ask: which choice minimizes regret? Ending earliest (intervals) means you leave the most options open. Smallest lexicographic chars first (string) means you can't do better.

Make the greedy choice — commit irrevocably

Scan the sorted input. At each element, make the locally optimal decision using only the current state (last selected end, current open counter, stack top, etc.). Never re-examine a past choice. The state is minimal — usually one or two variables.

# Interval greedy: one variable tracks frontier
if start > last_end:
    count += 1
    last_end = end

# Parentheses: two counters
if ch=='(': open += 1
elif open > 0: open -= 1
else: close += 1

Greedy state is tiny. If you're tracking a lot of variables or re-examining past elements, you may have drifted into DP territory. Greedy decisions depend only on current element + one accumulator.

Prove correctness or know the known-correct patterns

For interviews: either know the exchange argument for your specific problem, or recognize a known greedy pattern (interval scheduling, Huffman, Dijkstra, Kruskal). You don't need a formal proof — just explain why a non-greedy choice can't do better.

# Known greedy patterns:
# Interval scheduling → sort by end time
# Connect ropes / Huffman → min-heap (always cheapest pair)
# Jump Game → track max reachable position
# Gas Station → circular greedy with deficit tracking
# Coin change (canonical coins) → largest coin first

Greedy fails for: 0/1 knapsack, coin change with arbitrary denominations, shortest path with negative edges. If subproblems overlap and choices affect future choices in a complex way — use DP.

Pattern Recognition

'Maximum selection', 'minimum cost', 'locally optimal choice' = greedy candidate.

Greedy Works

"Max non-overlapping intervals" → sort by end

"Min additions to make string valid" → counter scan

Valid Palindrome II → two-pointer with one skip

"Largest palindromic number" → pair-and-center

"Remove duplicate letters" → stack + last occurrence

Connect ropes minimum cost → always cheapest two

"Jump Game" — track max reachable index

Coin change with canonical coins (1,5,10,25)

Greedy Fails (use DP)

0/1 knapsack — items can't be partially chosen

Coin change with arbitrary denominations

Longest increasing subsequence — greedy misses jumps

Edit distance — multi-character decisions interact

Matrix chain multiplication — subproblem overlap

Pair chain: start > last_end not start >= last_end

Duplicate letters: must check last[top] > i (safe to pop)

Palindrome construction: leading zeros edge case

On this page