What is a Greedy Algorithm?
Patterns·6 min read·code in python
A greedy algorithm builds a solution step by step, always taking the choice that looks best right now, the locally optimal option, and never undoing it. When the problem has the greedy-choice property and optimal substructure, these local choices add up to a globally optimal answer; otherwise greedy can fail.
The idea: take the best bite now
A greedy algorithm behaves like a cashier making change: to hand back the fewest coins, you reach for the largest coin that still fits, again and again, without ever reconsidering an earlier pick. That is the whole shape of greedy, sort or prioritize the options, then repeatedly grab whatever looks best at the moment and commit to it. No backtracking, no exploring alternatives.
Because it never revisits a decision, greedy is usually fast and easy to code; the hard part is not the loop but knowing whether those quick local wins actually add up to the best overall answer. Watching a greedy run animate step by step makes the 'commit and never look back' behavior click almost immediately.
When greedy is provably correct
Greedy returns the true optimum only when the problem has two properties. First, the greedy-choice property: a globally optimal solution can always be reached by making a locally optimal choice. Second, optimal substructure: an optimal solution contains optimal solutions to its subproblems. If both hold, committing to the best-looking option at each step is safe.
Interval scheduling (activity selection) is the textbook success. To fit the most non-overlapping meetings into one room, sort by finish time and keep every meeting that starts after the last one you kept ends. A short exchange argument proves it: replacing any other first pick with the earliest-finishing one never leaves you worse off. The same provable local-choice safety underpins Huffman coding, Kruskal's and Prim's minimum spanning trees, and Dijkstra's shortest paths.
When greedy quietly gives the wrong answer
Greedy is seductive because it often looks right on the small inputs you test, then fails on ones you did not. Making change is the canonical trap. With US-style coins {1, 5, 10, 25}, grabbing the largest coin that fits is optimal, but change the set to {1, 3, 4} and ask for 6: greedy takes 4 + 1 + 1 (three coins), while 3 + 3 (two coins) is better. The local choice poisoned the global result.
When earlier choices constrain later ones like this, you need dynamic programming, which reconsiders combinations instead of committing to one. The rule of thumb: never trust greedy until you can back it with an exchange argument or find a counterexample. 'It passed my examples' is not a proof.
The code
def max_meetings(intervals):
# Greedy: repeatedly pick the meeting that finishes earliest.
intervals.sort(key=lambda iv: iv[1]) # sort by finish time
count, last_end = 0, float("-inf")
for start, end in intervals:
if start >= last_end: # no overlap with last pick
count += 1
last_end = end # commit and never look back
return count
# max_meetings([(1, 3), (2, 5), (4, 7), (6, 9)]) -> 3Run it in the browser IDE, free on the platform. Open the IDE
Complexity
| Time | O(n log n): an initial sort or priority queue dominates; the greedy scan itself is a single O(n) pass |
|---|---|
| Space | O(1) extra beyond the input when sorting in place, otherwise O(n) |
Runtime is effectively the same best, worst, and average, because the sort runs regardless of input order. Heap-based greedy algorithms such as Dijkstra cost O((V + E) log V).
When to use it
- Interval or activity scheduling, fitting the most non-overlapping intervals by always keeping the earliest-finishing one.
- Any optimize problem where you can prove an exchange argument that a locally optimal choice is always safe.
- Classic graph and encoding problems that rely on provable local choices: Dijkstra, Kruskal/Prim MST, and Huffman coding.
- Coin change or resource allocation only when the denomination or cost structure is canonical (like standard currency).
Watch out for
- Assuming greedy is optimal without proof. Coins {1, 3, 4} making 6 give greedy 4+1+1 (three coins) when 3+3 (two coins) is better.
- Choosing the wrong priority or sort key, sorting intervals by start time or shortest duration instead of earliest finish gives suboptimal schedules.
- Reaching for greedy when subproblems overlap and choices interact; that situation needs dynamic programming, not a one-pass commit.
Greedy Algorithm: questions we get
Is greedy algorithm hard to learn?
The mechanics are among the easiest of any pattern, sort or prioritize, then loop once, taking the best option at each step. The genuinely hard part is proving your greedy choice is actually correct, which trips up even experienced engineers. Watching a greedy run animate step by step makes the 'commit and never look back' behavior click quickly.
When should I use a greedy algorithm instead of dynamic programming?
Use greedy when you can prove the greedy-choice property, that a locally optimal pick always leads to a global optimum, usually via an exchange argument. If earlier choices constrain later ones in ways that make local decisions unsafe (like coin change with odd denominations), use dynamic programming instead. Greedy is faster and simpler, so it is worth trying to prove it first.
What is the time complexity of a greedy algorithm?
It is usually dominated by an initial sort or a priority queue, so most greedy algorithms run in O(n log n) time with O(1) to O(n) extra space. The greedy scan itself is typically just one linear pass. Heap-based versions like Dijkstra's shortest paths cost O((V + E) log V).
Why does greedy fail for coin change?
Greedy always grabs the largest coin that fits, but that can strand you. With coins {1, 3, 4} making 6, greedy gives 4+1+1 (three coins) while 3+3 (two coins) is optimal. Standard currencies are designed so greedy works; arbitrary coin sets need dynamic programming.
Related concepts
Reading is the easy part. In a batch you build it, say it out loud in a scored mock round and hear what an interviewer would think.
Talk to mentor