Greedy Algorithm Interview Pattern: How to Tell When Greedy Works
Greedy algorithms are seductive in interviews. The idea is simple: at each step, make the choice that looks best right now and never look back. When greedy works, it produces short, fast solutions. When it doesn't, it produces confident, wrong answers.
This guide covers the greedy algorithm interview pattern: how to recognize it, how to check whether your greedy choice is safe, the classic templates, and how to justify your approach so the interviewer trusts it.
What makes a problem greedy
A greedy approach is correct when two things are true:
- Greedy choice property: some locally optimal choice is part of at least one globally optimal solution.
- Optimal substructure: after making that choice, the remaining problem is a smaller version of the same problem.
You don't need to say these terms in an interview, but you should be able to explain the idea in plain words: "Choosing this option first never makes the final answer worse."
Signals in the prompt
Greedy is worth considering when you see:
- Scheduling or selecting intervals ("maximum number of non-overlapping meetings")
- "Minimum number of" something to cover a range (jumps, arrows, platforms)
- Problems where sorting by one key makes the decision obvious
- Resource assignment ("assign cookies to children," "boats to people")
- Running state where you can commit early, such as a gas station circuit
Signals that greedy is risky: the prompt asks for the number of ways, the best value across many overlapping sub-choices, or anything where an early choice can block a better later one. Those usually point to dynamic programming.
Test your greedy choice before coding
The most useful habit: try to break your greedy rule with a small counterexample before you write code.
Take coin change with coins [1, 3, 4] and target 6. "Always take the largest coin" gives 4 + 1 + 1 (three coins), but 3 + 3 uses two. Greedy fails, so this is a DP problem.
Say this process out loud: "My greedy rule is to take the largest coin. Let me try a small case to see if it breaks... it does, so I'll use DP." That's a strong signal even though you discarded the idea.
If you try two or three tricky cases and the rule holds, explain why it holds, then code it.
Template 1: interval scheduling
Problem: select the maximum number of non-overlapping intervals.
Greedy rule: sort by end time, then repeatedly pick the interval that finishes earliest and doesn't overlap the last one picked.
def max_non_overlapping(intervals):
intervals.sort(key=lambda x: x[1])
count, last_end = 0, float("-inf")
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return count
Why it works: the interval that ends first leaves the most room for everything else. Any optimal solution can swap its first interval for the earliest-ending one without losing anything. That's the "exchange argument," and a one-sentence version of it is usually enough in an interview.
Sorting by start time or by length is a common trap. Try a counterexample with one long interval that starts early and covers several short ones.
Template 2: reach and jump problems
Problem: can you reach the last index if each value is the maximum jump length?
Greedy rule: track the farthest index reachable so far. If the current index ever exceeds it, you're stuck.
def can_reach_end(nums):
farthest = 0
for i, jump in enumerate(nums):
if i > farthest:
return False
farthest = max(farthest, i + jump)
return True
The minimum-jumps variant extends this by counting how many times you have to "commit" to a new window of reachable indices.
Template 3: sort and match
Problem: assign items to people so the most people are satisfied (for example, cookies to children by size).
Greedy rule: sort both lists, then use two pointers to match the smallest sufficient item to each person in order.
The justification: using a bigger item than necessary can only hurt later matches.
Template 4: running balance
Problem: gas stations in a circle; find a starting station that lets you complete the loop.
Greedy rule: if the total gas is less than total cost, no answer exists. Otherwise, track the running balance; whenever it drops below zero, the next station becomes the new candidate start.
This one benefits from a clear explanation: "If I can't get from A to B, then no station between A and B can be the start either, because I'd arrive there with at least as much fuel as starting fresh."
How to justify greedy in an interview
Interviewers often ask "how do you know this is correct?" Have a short structure ready:
- State the rule: "I always pick the interval that ends earliest."
- Give the intuition: "It leaves the most room for the rest."
- Sketch the exchange: "Any optimal answer could swap its first pick for mine without getting worse."
- Mention a failed alternative: "Sorting by start time breaks on this case."
That's thirty seconds, and it turns a hunch into a reasoned argument.
Complexity
Most greedy solutions are dominated by sorting: O(n log n) time. The greedy pass itself is usually O(n). Space is often O(1) beyond the sort, or O(n) if sorting creates a copy. State both.
Common mistakes
- Coding a greedy rule without testing a counterexample
- Sorting by the wrong key
- Using greedy on counting or "number of ways" problems
- Not explaining why the rule is safe
Practice the reasoning, not just the templates
Greedy problems reward the habit of proposing, testing, and justifying. Rehearse that loop out loud with a timer: state the rule, try to break it, then explain why it holds. Luna Interview gives you a structured place to practice that kind of spoken reasoning and stay calm when an interviewer challenges your approach.
Quick checklist
- [ ] Greedy rule stated in one sentence
- [ ] Two or three counterexamples tried
- [ ] Exchange-argument intuition ready
- [ ] Correct sort key chosen and explained
- [ ] DP considered if greedy breaks
- [ ] Complexity stated, including the sort
Greedy is less about being clever and more about being careful. Test the shortcut before you trust it.
Rehearse with an AI interview copilot, then browse commonly reported interview questions.