Greedy vs Dynamic Programming: Four Signals Tell You Before You Code

You stare at the problem. Optimization. "Minimize X given constraint Y." And now you're in the worst place a coding interview can put you: greedy vs dynamic programming, two plausible approaches, no obvious tell.

Both feel right until one of them very much isn't. Pick greedy on a DP problem and you've built a clean solution to the wrong problem. Pick DP on a greedy problem and you've spent 20 minutes writing transitions for something that wanted one sorted pass. The interviewer is looking at you. You are looking at the problem. The problem is not looking back.

Most prep resources skip the diagnostic step entirely. Greedy problems have tells. Pattern recognition first. Proof second. Code last.

Four Signals That Say "Try Greedy First"

These are diagnostics, not rules. The more that apply, the more confident you should be.

Signal 1: There's a natural sorting key. Inputs that become tractable when ordered by a single attribute. Activities sorted by end time. People sorted by weight. Tasks sorted by frequency. When a particular ordering makes a locally obvious choice, that ordering is usually the greedy key.

Signal 2: The ask is "maximize" or "minimize" a single value, not "count all ways." "Count every valid path to the end" requires exploring all branches, so that's DP. "Find the minimum number of jumps to reach the end" only needs the best branch at each step. Counting vs. optimizing is nearly always decisive.

Signal 3: After each choice, the remaining problem looks like a smaller version of itself. After you remove an interval, do you have a clean interval scheduling problem on fewer intervals? If yes, greedy is viable. If your choice changes which remaining items are even valid, you probably need DP.

Signal 4: A small counterexample is hard to construct. Spend two minutes drawing a four-element case and trying to make your greedy rule fail. If you can't, that's meaningful evidence. Not proof, but enough to shift your confidence threshold and commit.

The Exchange Argument: How You Know You're Actually Right

Most engineers who solve greedy problems in interviews can code the solution but can't explain why it works. That explanation is what separates a hire from a strong hire. (It also separates "I'm pretty sure this works" from "I am watching this fail in real time.")

The exchange argument is a 60-second mental test: take any optimal solution, find the first place it differs from your greedy choice, swap those elements, and ask whether the result is at least as good.

Interval scheduling by earliest finish time is the canonical example. Suppose an optimal schedule differs from your greedy schedule at position k. Optimal chose interval O_k, greedy chose G_k. By the greedy criterion, G_k finishes no later than O_k. Replacing O_k with G_k frees up time at the end. Future intervals can only stay the same or expand. The swap cannot hurt. By induction, the greedy schedule matches optimal.

You don't need to formalize this in an interview. Just articulate the swap direction: "Replacing the first differing element with my greedy choice never makes things worse, because my greedy criterion always leaves the most room for future decisions." That sentence is what interviewers are listening for.

The flip side is equally useful. If you try the exchange argument and find a swap that does hurt, you've found your counterexample. That's your signal to reach for DP.

"Sort by start time" and "sort by duration" both fail for interval scheduling, and the exchange argument tells you why. An early-starting interval might extend far into the future, crowding many subsequent choices. A short interval might overlap just as many as a long one. Only end time has the property that swapping to the earlier-ending option never reduces future capacity.

Three Templates Cover Most Interview Problems

Template 1: Sort + Scan

Sort inputs by the greedy key, then make decisions left to right.

# Non-overlapping intervals: remove minimum intervals so none overlap
# Signals: "minimum removals", intervals, clear end-time ordering
def erase_overlap_intervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])   # sort by end time, not start
    removed = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start < last_end:
            removed += 1        # overlap: remove this one
        else:
            last_end = end      # no overlap: take it, update boundary
    return removed

The sorting key is the entire insight. Earliest finish time maximizes intervals kept, which minimizes removals. Say it out loud: "I sort by end time because a later-finishing interval crowds out more future options than an earlier-finishing one."

The same template handles minimum arrows to burst balloons (sort by end, extend coverage greedily) and boats to save people (sort, then pair heaviest with lightest using two pointers from both ends, covered in the Two Pointer Technique post).

Template 2: Reach Tracking

Track the farthest position reachable from the current window. Never revisit.

# Jump Game II: minimum jumps to reach the last index
# Signals: "minimum jumps", bounded reach at each step, one pass feels right
def jump(nums: list[int]) -> int:
    jumps = 0
    current_end = 0    # farthest index reachable with `jumps` jumps
    farthest = 0       # farthest index reachable from within current window
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:        # must take a jump here
            jumps += 1
            current_end = farthest
    return jumps

You never decide which specific index to jump to. The greedy choice is "expand as far as possible from this range." The jump count only increments when you've exhausted your current window. This works because the optimal strategy is always to maximize reach per jump, and there's no benefit to saving reach for later.

Template 3: Frequency Heap

When items have frequencies and the processing order should favor the most common item, use a max-heap.

# Task Scheduler: minimum time with cooldown n between same-type tasks
# Signals: task frequencies drive the answer, cooldown prevents consecutive same tasks
def least_interval(tasks: list[str], n: int) -> int:
    from collections import Counter
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for f in freq.values() if f == max_freq)
    # (max_freq - 1) complete cycles, each of length (n + 1), plus trailing tasks
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

The formula falls directly out of the greedy insight: schedule the most frequent task first, fill cooldown slots with other tasks, repeat. Idle slots appear only when the most frequent task has nothing to pair with. Once you understand the reasoning, you can reconstruct the formula without memorizing it. This same pattern appears in Reorganize String and Minimum Cost to Connect Sticks (Huffman-style: always merge the two smallest, O(n log n) with a min-heap).

The Greedy vs DP Trap: When Weights Change Everything

Weighted interval scheduling is the classic ambush. The problem statement looks almost identical to what you just solved: intervals, pick a non-overlapping subset, optimize something. One version is O(n log n) greedy. The other is O(n log n) DP that you absolutely need to not mix up with the other one at 11am with a tired interviewer watching.

The difference is a single word: weight.

Unweighted: select as many non-overlapping intervals as possible. Greedy by earliest finish. Done.

Weighted: each interval has a value. Maximize total value from a non-overlapping subset. Greedy fails.

Here is the counterexample, size three: intervals A=[0,5], B=[0,2], C=[3,5] with weights 100, 1, 1.

Weighted interval scheduling counterexample: greedy picks B+C for weight 2, optimal picks A alone for weight 100

Greedy by earliest finish picks B (finishes at 2) then C (finishes at 5), total weight 2. Optimal picks A alone, weight 100. The exchange argument breaks here: swapping B for A requires also dropping C, because A overlaps C. The local swap cascades into a non-local restructuring. That's the symptom. When a swap changes more than the two elements being swapped, the greedy choice property is violated and DP is required.

The same distinction separates fractional knapsack (greedy by value-to-weight ratio, items are divisible so the highest-ratio item always contributes without wasting capacity) from 0/1 knapsack (DP, items are all-or-nothing and a high-ratio item might crowd out two smaller ones that fit perfectly).

The surface features are identical. Intervals, weights, maximization. The structural difference is whether making a choice constrains future choices in a way that may force you to give up more than you gain. Look for weights, arbitrary denominations, or any setup where "take the best now" can force you to pass on something far better later.

Gru's plan meme: presented with a coding interview challenge, didn't fall for the obvious hashmap solution, hashmap was the answer, hashmap was the answer

The move every interviewer has seen: you "see through" the obvious approach, pick DP, and spend 10 minutes building transitions for a problem that wanted one sorted scan.

Gas Station: The Wrong Turn and the Fix

Gas station (LC 134) appears to be a simulation until you see the O(n) greedy solution, at which point the whole thing clicks. Getting there involves at least one embarrassing detour.

Naive attempt: try every station as the starting point and simulate the circuit. O(n²). Correct but rejected.

Second attempt, where confidence and wrongness intersect: find the first station with gas[i] > cost[i] and start there. Sounds reasonable. Breaks immediately on any case where stations 0 through k all run a deficit but the valid start falls at k+1. "Start at the first positive" can guess correctly by accident, but it has no reasoning behind it. You'll write this, run it on a test case, it'll pass, and you'll think you're done. You are not done.

The actual greedy insight has two parts. First: if total gas < total cost, return -1. No starting point can work, because the circuit consumes exactly sum(cost) regardless of where you begin. This eliminates impossible cases in O(n).

Second: if a solution exists, a single scan finds it. Track your cumulative tank. Whenever the tank goes negative at station i, none of the stations from your last restart up through i can be valid starts. If any of them worked, you would have reached i with a non-negative tank, which you didn't. Reset the start to i+1 and zero the tank.

def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
    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
            tank = 0
    return start

The correctness proof: by the time you finish the scan, you've proven that every station from 0 to (start-1) fails, and the remaining segment from start to n-1 has enough surplus to cover the deficit you accumulated earlier. When total gas equals total cost, those two pieces perfectly cover each other.

Interviewer cat: 'When you're 30 minutes into the interview and the candidate is still explaining their naive O(n²) gas station solution but you have to stay professional'

This is also what the interviewer looks like while you explain why "start at the first positive station" definitely works on all inputs.

Three Minutes Before You Code

A concrete protocol for any problem that might be greedy:

Name your greedy choice in one sentence. "I will always pick the interval with the earliest finish time." "I will always jump to maximize my farthest reach." If you can't name it clearly, you don't have a greedy algorithm yet. "I think maybe we sort and then do something" is not a greedy choice.
Try two small counterexamples. Draw three to four elements and run your rule by hand. If both pass, your confidence is justified.
State the exchange argument in one sentence. "Swapping my greedy choice for any other leaves at most as much room for the future." If that statement feels right after a moment's thought, go. If it feels shaky, sketch a three-element case to test it.
Pivot at minute three if needed. "I can't quickly prove the greedy choice is correct, so I'll start with DP to guarantee correctness. We can see if there's a greedy optimization afterward." That's a strong answer, not a concession.

SpaceComplexity runs voice-based mock interviews where you practice this exact reasoning out loud. Naming the greedy choice, articulating the swap argument, catching your own counterexamples before the interviewer does. Getting comfortable with the verbal part is half the problem.

Recap

Four signals: natural sorting key, single-value optimization (not counting), decisions that don't box in future choices, hard to construct a small counterexample
Exchange argument: take any OPT, find where it differs from your greedy choice, swap those elements; if the swap never hurts, greedy is provably correct
Three templates: sort + scan (intervals, pairing), reach tracking (jump games, gas station), frequency heap (cooldown scheduling, Huffman-style merging)
The weighted interval trap: adding values to intervals breaks the greedy choice property because a local swap cascades; that's the signal to switch to DP
The three-minute protocol: name the choice, test two examples, state the exchange argument, pivot to DP if stuck

For the formal mechanics and complexity analysis of greedy algorithms, see The Greedy Algorithm. For when dynamic programming is the right tool instead, When to Use Dynamic Programming walks through the exact decision criteria.