What Is a Greedy Algorithm? A Beginner's Guide with Examples
- Greedy algorithms make the locally optimal choice at each step without ever reconsidering past decisions
- Correct only when the problem has both the greedy choice property and optimal substructure — verify both before committing
- Fractional knapsack is solvable greedily; 0/1 knapsack is not — the all-or-nothing constraint breaks the greedy choice property
- Jump Game (LeetCode 55) is the clearest interview example: track maximum reachable index in O(n) time, O(1) space
- Four greedy signals: sorting reveals a processing order, steps are independent, an exchange argument holds, problem asks for a max or min
- When greedy applies it's almost always faster than DP — O(n) or O(n log n) versus O(n²) or O(n·W)
- Interviewers score your justification for the greedy choice, not just whether the code compiles
You have 41 cents to make in change. You reach for a quarter. Then a dime. Then a nickel. Then a penny. Done.
You just ran a greedy algorithm. No backtracking, no second-guessing, no elaborate state table. You grabbed the best available coin at each step and moved on.
A greedy algorithm builds its solution by making the locally optimal choice at every decision point, without ever reconsidering past decisions. It is fast, often elegant, and wrong often enough that knowing when to trust it is the skill that actually separates engineers who pass interviews from engineers who Google the answer afterward.
How the Greedy Algorithm Works
Most problem-solving techniques involve trade-offs between exploring possibilities. Dynamic programming tracks overlapping subproblems across a table. Backtracking explores every branch and prunes the bad ones. Both can be expensive. Both require you to remember things.
Greedy sidesteps all of that. At each decision point, it asks one question: what is the best available option right now? It picks that option, updates its state, and moves forward. No stored history. No looking back.
The result is usually an O(n) or O(n log n) algorithm with O(1) or O(log n) extra space. Most developers' instinct is to reach for DP anyway. Sometimes that is fine. Often it is overkill. Occasionally it gets you a worse complexity than you needed.
The catch is that "best right now" does not always lead to "best overall." A greedy approach is only correct when the problem has two structural properties: the greedy choice property and optimal substructure. Understanding those two properties before you write a line of code is the skill that actually matters.
Coins First, Counterexample Second
Coins available: 25, 10, 5, and 1 cents. Goal: make 41 cents using the fewest coins.
The greedy strategy is to always pick the largest coin that fits.
- 41 cents: take 25. Remaining: 16.
- 16 cents: take 10. Remaining: 6.
- 6 cents: take 5. Remaining: 1.
- 1 cent: take 1. Remaining: 0.
Four coins. Optimal.
def min_coins_greedy(amount: int, denominations: list[int]) -> list[int]: denominations.sort(reverse=True) coins_used = [] for coin in denominations: while amount >= coin: amount -= coin coins_used.append(coin) return coins_used print(min_coins_greedy(41, [25, 10, 5, 1])) # [25, 10, 5, 1]
Clean and O(n) after sorting. Feel good about yourself? Now try denominations of 10, 7, and 1. Make 14 cents.
Greedy picks 10, then four 1s. Five coins. The correct answer is two 7s. Two coins.
Greedy was confidently, completely wrong. This coin system lacks the greedy choice property: picking the largest coin first does not guarantee you stay on the path to the optimal solution. That version of the problem requires dynamic programming.
The Two Properties That Make Greedy Correct
Greedy choice property. A globally optimal solution can be reached by making locally optimal choices. When you pick the best option at each step, you never close off the path to the best final result. US coins have this property because their denominations are structured so larger coins divide cleanly into the remaining space. Arbitrary coin sets often do not.
Optimal substructure. The optimal solution to the overall problem contains optimal solutions to its subproblems. After picking a 25-cent coin on a 41-cent problem, making 16 cents optimally is itself an independent subproblem with an optimal solution. DP also relies on this property, which is exactly why DP is the fallback when the greedy choice property fails.
If a problem has both properties, greedy is correct. If you can confirm optimal substructure but not the greedy choice property, you need DP. If you cannot confirm optimal substructure either, backtracking is about to ruin your evening.
Greedy Fails Here: The 0/1 Knapsack Trap
Two problems that look nearly identical but require completely different approaches. Interviewers love this pair.
Fractional knapsack. You have items with weights and values. You can take fractions of any item. Fill the knapsack to maximize total value. Greedy works. Sort by value-per-unit-weight, take as much of the best item as fits, move to the next.
0/1 Knapsack. Same setup, but every item is all-or-nothing. No fractions. Greedy fails. Taking the highest ratio item first can block you from a combination of smaller items with greater total value. The choice to include item i creates downstream constraints that greedy cannot account for. You need DP.
When greedy fails, you fall back to DP. Some people are clearly more prepared for that than others.
The signal to watch for: if your current choice constrains future choices in a cascading way, greedy is risky. If your current choice only reduces the remaining problem without affecting which future options exist, greedy is likely fine.
Jump Game: The Cleanest Interview Example
LeetCode 55 is the canonical case. You have an array where each element is your maximum jump length from that index. Starting at index 0, can you reach the last index?
[2, 3, 1, 1, 4] → True
[3, 1, 1, 0, 4] → False
The greedy insight: you do not need to simulate every possible path. You just need to track how far you can reach from where you currently stand. Walk the array once. At each position, update the maximum reachable index. If you ever step onto a position beyond your current reach, you are stuck.
def can_jump(nums: list[int]) -> bool: farthest = 0 for i, jump in enumerate(nums): if i > farthest: return False farthest = max(farthest, i + jump) return True
O(n) time, O(1) space. A DP approach also works but costs O(n²) without optimization. Greedy wins because tracking maximum possible reach at each index cannot be improved by taking less. There is nothing to reconsider. You can never regret updating a maximum.
How to Tell Greedy from DP Before You Code
Both techniques apply to problems with optimal substructure. The question is whether the greedy choice property holds. Can you make an irrevocable local choice, reduce the problem to a smaller version of itself, and trust that solving the remainder optimally finishes the job? If yes, greedy applies. If your choice creates complex dependencies on future choices, you need DP.
Testing a small counterexample takes 30 seconds and can save you from implementing the wrong approach entirely. Three or four elements is usually enough.
Four signals that point toward greedy:
- The problem asks for a maximum or minimum with a "take the best first" intuition
- Sorting the input reveals a natural processing order
- Each step is independent: choosing element i does not constrain element i+2 in a cascading way
- A proof by exchange argument works: swapping any two choices in the greedy solution makes it no better
Four signals that push you toward DP instead:
- The problem counts paths or combinations rather than finding a max or min
- A small counterexample breaks the "always take the best" intuition
- You face 0/1 decisions where inclusion or exclusion triggers ripple effects
- The problem involves "at most k" or "exactly k" operations across interdependent choices
For a deeper treatment of the exchange argument proof, the greedy choice property guide walks through it formally. For the DP comparison, greedy vs dynamic programming covers four concrete signals with problem examples.
Greedy Is Almost Always Faster Than DP
When greedy applies, the complexity is almost always better than the DP equivalent.
| Problem type | Typical greedy | Typical DP fallback |
|---|---|---|
| Simple scan (Jump Game, max reach) | O(n) time, O(1) space | O(n²) time, O(n) space |
| Sort-then-scan (activity selection, intervals) | O(n log n) time, O(1) space | O(n²) time, O(n) space |
| Heap-based (task scheduling, k-th best) | O(n log n) time, O(n) space | O(n * k) time, O(n * k) space |
| Classic knapsack (0/1) | Greedy fails | O(n * W) time, O(W) space |
The reason greedy is faster is that it commits to each choice and discards it from memory. DP keeps every subproblem result. When the greedy choice property holds, all that stored state in DP was unnecessary work.
The One Sentence That Fills the Rubric Box
Greedy problems appear at every level. The implementation is rarely the hard part. What trips candidates up is either reaching for DP out of habit (correct but unnecessarily complex) or reaching for greedy without justification (which the interviewer will probe immediately).
You do not need to explain the proof from first principles. One sentence, specific claim, why you cannot do better. That is it.
When you identify a greedy approach, do not just say "I'll greedily take the best option." That tells the interviewer approximately nothing useful. Name the specific local choice and state why it cannot be improved by looking ahead. One sentence is enough: "At each index, tracking the maximum reachable position is always at least as good as any alternative, so we never need to reconsider."
That justification is the difference between a 3 and a 4 on the problem-solving rubric. Interviewers at Google, Meta, and Amazon explicitly score whether you can articulate why your greedy choice is safe. Getting the code right without the explanation leaves the "communication" and "problem-solving" boxes unfilled.
If you want to practice stating that reasoning out loud under pressure, SpaceComplexity runs voice-based mock interviews that score your explanation of the approach, not just your final code.
For problem practice, the top greedy interview problems covers ten problems that each require a different flavor of greedy reasoning. Work through five or six and the pattern-recognition clicks.