What is a greedy algorithm, and when does the greedy choice work?

beginner

← All Sorting, Searching & Recursion questions

Re-explain

A greedy algorithm builds an answer step by step, always taking the option that looks best. It never revisits a choice, which keeps it fast and simple, usually O(n log n) after a sort, sometimes O(n).

Greedy works when two things hold. The first is the greedy-choice property, where a locally best pick is part of some overall best answer. The second is optimal substructure, where solving what remains after that pick gives the full solution.

Making change in US coins works greedily. You take the biggest coin that fits, 25 cents first, then 10, 5 and 1. It fails on unusual coin sets, where a smaller first coin wins.

An unproven greedy pick can return a wrong answer with no error, so test it against a slower exact method.

Rewriting in plainer words…

This answer doesn't lend itself to a diagram - it reads best . No credits were charged.

Why there's no diagram: “”

The interactive diagram is below the answer - jump to diagram ↓ · Below it, the related concept . Jump to it ↓

The diagram below the answer is the concept . Jump to it ↓

Tailored explanation · switch back to · ·

What should the new diagram focus on?

Guided practice for Sorting, Searching & Recursion One question at a time. Answer out loud, get graded, see what you missed.

How well did you know this?

AI:

Saved in this browser - sign in to keep your review list.

How should your speech become text?

Listening… your words appear above as you speak - tap Stop when you're done.

Recording · cr - tap Stop & transcribe when you're done.

Transcribing with AI…

Voice:

Keep going - a few more words and AI can grade it.

Interview lens How interviewers actually use this question

Likely follow-ups

How would you prove a greedy choice is correct for a problem like interval scheduling? Name the exchange argument, which swaps an optimal answer's first pick for the greedy pick and shows the result is still valid and no worse.
Give a coin set where greedy change-making fails. What would you use instead? Coins 1, 3 and 4 making 6: greedy takes 4+1+1, but 3+3 uses fewer coins. Dynamic programming over every amount finds the true minimum.
How does greedy differ from dynamic programming when both rely on optimal substructure? DP solves and compares many subproblems before it chooses. Greedy commits to one pick up front, which is safe only with the greedy-choice property.
Why do so many greedy solutions start with a sort, and how do you pick the sort key? Sorting puts the best candidate next, and the key decides correctness. Interval scheduling sorts by earliest end time, not by start time or length.
When is a greedy heuristic acceptable even though it may not be optimal? When exact search is too slow, as on NP-hard problems like set cover, and the greedy result has a known bound or measures well on real data.

What you can say

A greedy algorithm builds its answer one step at a time, always taking the option that looks best right now and never going back to change a choice.
Because it never revisits a choice it stays fast and simple, usually O(n log n) for a sort up front and sometimes O(n).
It only gives the right answer when two properties hold, the greedy-choice property and optimal substructure.
That means the locally best pick has to be part of some optimal answer, and solving what remains after it has to give you the full solution.
Making change in US coins works greedily, where you take the biggest coin that fits each time, but on unusual coin sets a smaller first coin can give a better answer.
The risk is that an unproven greedy pick fails silently with a wrong answer and no error, so I'd check it against a slower exact method before I trust it.

Weak answers to avoid

Defines greedy but never says when it works Anyone can say "pick the best option each step". The points are in the conditions, so name the greedy-choice property and optimal substructure.
Claims greedy always finds the optimum It can return a wrong answer with no error. Say it is correct only when both properties hold, and give a case where it fails, like an unusual coin set.
Argues correctness from a few examples Passing a few hand-picked cases proves nothing. Back the pick with a proof such as an exchange argument, or test it against a slower exact method.
Confuses greedy with dynamic programming Both need optimal substructure, but DP compares many subproblem answers while greedy commits to one pick. Say which property lets greedy skip that work.

Interview lens

Likely follow-ups, what you can say, and the weak answers to avoid.

Want a quick review of the fundamentals? See the Sorting, Searching & Recursion cheatsheet.

← Back to all Sorting, Searching & Recursion questions

Pro · $10/mo

51 of 61 Sorting, Searching & Recursion answers are in Pro.

Full answers, code samples, and AI explanations that go simpler or deeper. Cancel anytime.

Full answers + code
AI explanations, simpler or deeper
1,000 AI credits / month
Cancel anytime

Get Pro → See plans & pricing →