Coding interview pattern
Greedy
Make the locally optimal choice at each step when it provably yields the global optimum.
The idea
How the greedy pattern works
A greedy algorithm builds a solution by always taking the choice that looks best right now, never reconsidering. This is dramatically simpler and faster than DP or search, but it is only correct when the problem has the greedy-choice property: a locally optimal pick is always part of some globally optimal solution. The whole challenge is proving (or convincing yourself) that the property holds, because a greedy that looks right but is wrong fails on adversarial inputs.
The most reliable signals that greedy works are interval and scheduling problems and problems with a clear sort-then-sweep structure. Interval scheduling (maximise non-overlapping meetings) is solved by sorting on end time and greedily taking each compatible interval. Jump-game reachability, gas-station circuits, and many assignment problems also yield to a single greedy pass once you find the right ordering.
In an interview, justify the greedy with an exchange argument: assume an optimal solution differs from the greedy choice, then show you can swap in the greedy choice without making the solution worse, which means the greedy choice is safe. If you cannot construct that argument, be suspicious; the problem may actually need DP. State this reasoning explicitly, because choosing greedy without justification is a common way to get a correct-looking but unconvincing answer.
Recognition
When to reach for it
- Sorting the input by some key exposes an obviously safe first choice.
- The problem is interval scheduling, partitioning, or a one-pass assignment.
- You can argue via exchange that the local choice never hurts the optimum.
- DP would work but is overkill and a sort-then-sweep is provably correct.
Cost
Time & space complexity
| Operation | Time | Space |
|---|---|---|
| Sort then sweep | O(n log n) | O(1) or O(n) |
| Single linear pass (already ordered) | O(n) | O(1) |
| Heap-assisted greedy | O(n log n) | O(n) |
Worked example
Walkthrough: Non-overlapping intervals (remove the fewest to make the rest disjoint)
- 1Sort the intervals by their end time.
- 2Track the end of the last interval you kept, starting at negative infinity.
- 3Scan in order: if an interval starts at or after the last kept end, keep it and update the end.
- 4Otherwise it overlaps, so count it as a removal and skip it.
- 5Keeping the interval that ends earliest leaves the most room for the rest, which the exchange argument proves is optimal.
Translatable skeleton
The shape in pseudocode
Language-agnostic on purpose. Translate it to your language of choice.
sort by key; best = init; for item in sorted: if compatible(item, best): take(item); update(best)Practice
Curated problem set
Work these in order, easy to hard. Each is chosen to drill a different facet of the pattern.
| Problem | Level | Why it fits |
|---|---|---|
| Best Time to Buy and Sell Stock | Easy | Track the min price; greedily bank each gain. |
| Jump Game | Medium | Track the farthest reachable index. |
| Non-overlapping Intervals | Medium | Sort by end, keep the earliest finisher. |
| Gas Station | Medium | Single pass with a running tank and a reset point. |
| Partition Labels | Medium | Extend the partition to each char's last index. |
| Task Scheduler | Medium | Greedily schedule the most frequent task first. |
Avoid these
Common pitfalls
- Assuming greedy works without an exchange argument, then failing edge cases.
- Sorting on the wrong key (start vs end) and breaking correctness.
- Using greedy where the optimum genuinely needs DP.
- Missing a tie-break that the proof of correctness depends on.
In the interview
How to communicate it live
Recognising the pattern is half the score; saying the right things out loud is the other half. These are the sentences that earn the signal.
Before committing to greedy, give the exchange argument out loud, assume an optimal solution differs from your choice and show you can swap your choice in without making it worse; that proof is the difference between a lucky answer and a correct one.
Name the sort key and why it is the right one, for example sort by end time so the earliest finisher leaves the most room; the wrong key silently breaks correctness.
If you cannot construct the exchange argument, say so and consider DP instead; flagging the uncertainty is better than asserting a greedy that fails on adversarial input.
Also searched as
greedy algorithm interview - interval scheduling greedy - exchange argument
Last reviewed by the site editor: June 2026
An external resource we recommend. AlgoExpert is not affiliated with us and we earn nothing from this link.
Sources
- Greedy Algorithms (Chapter 4, Algorithms) Jeff Erickson, University of Illinois Urbana-Champaign
- Greedy Algorithms I (lecture slides for Kleinberg and Tardos, Algorithm Design) Kevin Wayne, Princeton University
- Interval scheduling Wikipedia
Next up
Patterns that pair well with this one
Real problems rarely match a single pattern. Interviewers like to combine this one with these.
- Sliding Window
Track a contiguous subarray or substring without re-scanning it from scratch.
- Two Pointers
Walk two indices toward or alongside each other to avoid a nested loop.
- Binary Search
Halve the search space each step over any monotonic condition, not just sorted arrays.
- Dynamic Programming
Solve overlapping subproblems once, store the results, and build the answer up.
Round out your prep
See all coding patterns, the coding questions for your role, and the behavioral round.