Greedy

Greedy is a bet: the best move right now is part of some best overall plan. That bet is called the greedy-choice property, and it's the entire deal. If it holds, you can commit to each local decision and never revisit it — one pass, no backtracking, no table of subproblems.

Concrete example: you're a cashier giving change in coins of 1, 5, 10, 25. Greedy says "always hand over the biggest coin that fits." For US coins this is provably optimal. Now change the coin set to {1, 3, 4} and ask for 6: greedy gives 4 + 1 + 1 (three coins) but the optimum is 3 + 3 (two). Same code, different universe — because the greedy-choice property held in one coin system and not the other.

def make_change(amount, coins=(25, 10, 5, 1)):
    used = 0
    for c in coins:               # biggest first
        used += amount // c       # commit greedily, never revisit
        amount %= c
    return used

So the skill is never "write a greedy loop." It's "decide whether this problem lets me get away with one."

In an interview you don't need a formal proof — you need a convincing exchange argument, delivered in two sentences:

"Take any optimal solution that disagrees with my greedy choice. I can swap the greedy choice in without making the solution worse. So some optimal solution agrees with greedy at every step."

Walk through it on activity selection (pick the maximum number of non-overlapping meetings): greedy picks the meeting that ends earliest. Suppose an optimal schedule starts with some other meeting M. The greedy pick ends no later than M, so it conflicts with nothing that M didn't already conflict with — swap it in, the schedule is still valid and still the same size. Repeat the argument down the line and the fully-greedy schedule is optimal.

The interview script:

1. State the greedy rule out loud ("always extend with the earliest-ending meeting").
2. Say why a swap can't hurt ("ending earlier only leaves more room for the rest").
3. Test it against a hostile example before coding. If you can't break it in 30 seconds of trying, code it. If you can break it, you just saved yourself from a confidently wrong solution — pivot to DP.

That third step matters most. Interviewers love candidates who attack their own idea before defending it.

Both greedy and dynamic programming exploit optimal substructure (the best answer is built from best answers to subproblems). They differ in how many options they keep alive:

Litmus tests that scream DP, not greedy:

• The counterexample hunt succeeds ({1, 3, 4} coins).
• The answer depends on a budget or capacity being shared across choices (knapsack).
• "Number of ways" anything — greedy picks one way; counting needs all of them.

And a signal for greedy: the input gets sorted by some key and then consumed in order (intervals by end time, deadlines, ratios). If sorting by one key makes every later decision independent of the past, you've probably found the greedy-choice property.

When in doubt in an interview: sketch the DP first. Then notice — out loud — whether the recurrence always picks the same branch. If it does, the DP collapses into a greedy, and you've shown both tools in one answer.

Maximum subarray sum is the crossover episode: it's usually filed under DP, but the famous one-pass solution is a greedy decision made n times.

At each element you face exactly one choice: extend the best streak ending at the previous element, or abandon it and start fresh here. The greedy rule: a negative running streak can never help whatever comes next — drop it.

def best_streak(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)   # extend the streak, or cut your losses
        best = max(best, cur)
    return best

The exchange argument in one line: if cur < 0, any subarray that drags that prefix along is improved by deleting it — so the optimal subarray never starts inside a negative streak.

Notice the DP reading of the same code: cur is dp[i] = "best sum of a subarray ending exactly at i", and the recurrence dp[i] = max(nums[i], dp[i-1] + nums[i]) only ever needs the previous value, so the table shrinks to one variable. Greedy and 1-D DP are the same animal here, seen from two angles — which is exactly why this topic comes right before the DP weeks.