Greedy Algorithms for Coding Interviews (When They Work)

A greedy algorithm builds a solution one step at a time, always taking the choice that looks best right now and never reconsidering it. When that works, you get a clean O(n) or O(n log n) solution that beats the dynamic-programming alternative on both speed and code length. When it doesn't, greedy quietly returns a wrong answer that passes the sample cases — which is exactly why interviewers like it.

This guide covers what makes the greedy algorithm interview pattern work, how to separate it from DP, the exchange-argument intuition, the signals that flag a greedy problem, and four worked examples with Python and Big-O.

What greedy actually is

Greedy relies on one property: a locally optimal choice leads to a globally optimal solution. If picking the best option available at each step never forces a worse outcome later, you can commit to each choice and move on. No backtracking, no table of subproblems — just a sort (often) followed by a single pass.

When to recognize this pattern

• Intervals. Selecting the most non-overlapping meetings, or merging/removing overlaps.
• Reachability. Jump Game and its variants — "can I get to the end?" or "fewest jumps?"
• Resource loops. Gas station, task scheduling with cooldowns, assigning cookies to children.
• "Maximize/minimize" with an obvious ordering. If sorting by one key makes the answer fall out in a linear pass, suspect greedy.

When greedy works vs when it fails (greedy vs DP)

The dividing line is whether an early choice can trap you. Consider making change for 11 cents with coins {1, 5, 6, 9}. Greedy takes 9, then needs two 1s — three coins. The optimum is 5 + 6 — two coins. Greedy fails because taking the biggest coin first ruled out a better combination. With canonical coin systems like US currency, greedy happens to be correct; with arbitrary denominations it is not, and you need DP.

The mental test: can you construct a small input where the greedy choice loses? If yes, greedy is wrong. If you try a few and can't break it — and you can sketch why — greedy is probably safe.

Property	Greedy	Dynamic programming
Choices	Commit once, never revisit	Keep every option that might matter
Typical cost	O(n) or O(n log n)	Often O(n²) time and O(n) space
Needs	Greedy-choice property + sort key	Overlapping subproblems + optimal substructure
Risk	Wrong answer if property fails	Slower, but always correct here

The exchange-argument intuition

To convince an interviewer (and yourself) that greedy is correct, use an exchange argument. Assume some optimal solution differs from the greedy one. Show you can swap the greedy choice in for whatever the optimal solution did first, without making it worse. If every difference can be exchanged away like that, the greedy solution is at least as good as any optimum — so it is optimal. You rarely write a full proof in an interview, but saying "here's the swap that shows it never hurts" is exactly what earns the nod.

Worked examples

Non-overlapping intervals

Problem: Given intervals, remove the fewest so the rest don't overlap.

Sort by end time and keep an interval whenever it starts at or after the last kept end. Finishing earliest leaves the most room for the rest — the exchange argument.

def eraseOverlapIntervals(intervals):
    intervals.sort(key=lambda x: x[1])
    kept_end = float('-inf')
    removed = 0
    for start, end in intervals:
        if start >= kept_end:
            kept_end = end        # keep it
        else:
            removed += 1          # overlaps, drop it
    return removed

O(n log n) for the sort, O(1) extra space. Sorting by start time instead is the classic mistake — it breaks the greedy choice.

Jump Game

Problem: Each value is the max jump length from that index. Can you reach the last index?

Track the farthest index reachable so far. If you ever stand on an index beyond that reach, you're stuck.

def canJump(nums):
    reach = 0
    for i, step in enumerate(nums):
        if i > reach:
            return False          # can't even get here
        reach = max(reach, i + step)
    return True

O(n) time, O(1) space. The greedy insight is that only the farthest reach matters, not which path produced it.

Gas Station

Problem: Circular route with gas[i] and cost cost[i] to the next station. Find a start index you can complete the loop from, or -1.

If total gas is at least total cost, a solution exists. Whenever the running tank goes negative, no station in the failed stretch can be the start — jump the candidate to the next station.

def canCompleteCircuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    tank = 0
    start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1          # restart after the failure
            tank = 0
    return start

O(n) time, O(1) space. The greedy leap — skipping every station in a failed prefix — is what turns an O(n²) brute force into one pass.

Task Scheduler

Problem: Given tasks and a cooldown n between identical tasks, find the minimum total time (tasks plus idles).

The most frequent task dictates the skeleton. Lay it out with gaps of size n, then fill the gaps greedily. The answer is a formula on the max frequency, unless there are so many tasks the gaps disappear.

from collections import Counter

def leastInterval(tasks, n):
    counts = Counter(tasks)
    max_freq = max(counts.values())
    max_count = sum(1 for c in counts.values() if c == max_freq)
    slots = (max_freq - 1) * (n + 1) + max_count
    return max(slots, len(tasks))

O(n) time, O(1) space (at most 26 distinct tasks). The max(...) guards the case where tasks are dense enough that no idling is needed.

Common pitfalls

• Assuming greedy without proof. Always try to break it with a counterexample first, especially on "min coins / min cost" problems — those are often DP in disguise.
• Wrong sort key. Interval scheduling needs end time, not start time. The sort key is the algorithm.
• Confusing "looks optimal" with "is optimal." A choice that wins the sample cases can still be globally wrong.
• Skipping the edge cases. Empty input, a single element, and the "everything overlaps" case catch off-by-one errors.

FAQ

When should I use a greedy algorithm?

Use greedy when a locally optimal choice provably leads to a globally optimal solution — typically interval problems, activity selection, jump game, gas station, and some scheduling tasks. If choosing the best-looking option now can force a worse outcome later, greedy is wrong and you likely need dynamic programming.

How is greedy different from dynamic programming?

Greedy commits to one choice at each step and never reconsiders, running fast in O(n) or O(n log n). DP explores overlapping subproblems and keeps every option that might matter, usually costing more time and memory. Greedy only works when the problem has the greedy-choice property; DP handles the cases where earlier choices must be revisited.

What is the exchange argument?

It is the standard way to prove a greedy algorithm is correct. You assume an optimal solution differs from the greedy one, then show you can swap in the greedy choice without making the solution worse. If every difference can be exchanged away, the greedy solution is at least as good as optimal.

Why does sorting matter for greedy problems?

Many greedy algorithms only work once the input is ordered by the right key — by end time for interval scheduling, by ratio for fractional knapsack. Picking the correct sort key is usually the whole insight; after sorting, a single linear pass produces the answer.

How do I know if greedy is safe in an interview?

Try to construct a small counterexample where the greedy choice loses. If you cannot break it after a couple of tries and you can sketch an exchange argument, greedy is likely safe. If a counterexample appears quickly, switch to dynamic programming.