← Learn DSA · Lesson 8 of 11
Greedy
Take the best-looking option now — when you can prove that is safe.
The idea
A greedy algorithm makes the choice that looks best right now and never reconsiders. When that works it is the simplest and fastest thing available. When it does not, it produces a confident wrong answer, which is worse than being slow.
So the real content of this topic is not the code — the code is a loop — it is knowing when greedy is safe. Two properties have to hold:
Greedy choice property — a globally optimal solution can be reached by making the locally optimal choice at each step. Nothing you pick now blocks the best outcome later.
Optimal substructure — after making that choice, what remains is the same problem on a smaller input.
Coin change makes the danger concrete. With coins 25, 10, 5 and 1, taking the largest coin that fits is optimal for every amount. Add a 20 and remove the 10, and 40 greedily becomes 25 + 5 + 5 + 5 — four coins where 20 + 20 is two. Same algorithm, same code, wrong answer, because the coin system changed.
In an interview the useful move is to try to break it. Construct a small counterexample. If you cannot, say why the greedy choice is safe. If you can, you have just discovered that the problem is dynamic programming.
Most correct greedy solutions begin by sorting — by end time, by ratio, by deadline — because the sort is what makes "best right now" well defined.
Walkthrough
Largest coin first, never reconsidered. This is optimal for these coins — and the lesson above shows a coin set where the identical code is wrong.
What it costs
- time
- Usually O(n log n), dominated by the sort that makes the choice well defined
- space
- O(1) beyond the sort
Greedy is normally the cheapest correct approach when it is correct at all. The cost of using it wrongly is not performance — it is a wrong answer that passes small tests.
When to reach for it
- You can argue that a locally best choice never blocks a globally best outcome.
- Interval scheduling: pick the earliest finishing time, repeatedly.
- The problem asks for a maximum count or minimum count and the items have a natural priority order.
- Huffman coding, minimum spanning trees, and the fractional knapsack — all provably greedy.
Rather than the obvious alternative
Dynamic programming
The direct trade. DP explores the choices greedy skips, at a real cost in time and space. Use greedy when you can prove skipping is safe, DP when you cannot — and a single counterexample decides it.
Backtracking
Exhaustive and always correct, and exponential. Greedy is what you use when the structure of the problem means you never need to reconsider.
How to spot it
- The problem asks for a maximum or minimum count, and items have an obvious ordering.
- It is about scheduling, intervals, or deadlines.
- Sorting the input makes the right choice at each step obvious.
- You can construct an exchange argument: swapping any other choice for the greedy one does not make things worse.
Where it goes wrong
Assuming greedy works because it passes the examples
Sample inputs are small and forgiving. Spend thirty seconds trying to build a counterexample before committing — that is the whole decision.
Sorting by the wrong key
Interval scheduling sorts by *end* time. Sorting by start, or by duration, is a correct-looking algorithm that gives wrong answers.
Greedy on 0/1 knapsack
The ratio-first choice is optimal for the fractional version and wrong for the 0/1 version. The two problems look identical and are not.
Try it
Two short checks. They run the same way the practice problems do — write the function, press Run.
Given sorted-descending weights and a capacity, return how many items you can take, largest first, without exceeding capacity.
Tests
4 cases, 1 hidden| call | type | expected | result |
|---|---|---|---|
| takeGreedy([5,3,2], 8) | takes two | 2 | — |
| takeGreedy([3,2,1], 10) | takes all | 3 | — |
| takeGreedy([9], 4) | takes none | 0 | — |
| withheld | hidden | withheld | — |
Hidden cases run too — their inputs aren't listed here, so aim for a general solution rather than one fitted to the cases above.
Hints
Stuck? Hints open one at a time, each giving a little more away.
2 hints left
Practise it
- Best Time to Buy and Sell Stockeasy
- Jump Gamemedium