The greedy idea

Take the best-looking step and never look back

A greedy algorithm makes the choice that looks best right now and never reconsiders it. No exploring alternatives, no backtracking, no table of results - just walk forward taking the locally best option each time.

The appeal is obvious. Greedy solutions are short, fast, and usually take a single pass. Where backtracking explores an exponential space and dynamic programming fills a table, greedy walks straight through in O(n log n) or better.

The catch is equally obvious once stated: the locally best step is not always part of the globally best answer. Sometimes taking a slightly worse step now opens a much better path later. Greedy cannot see that, because it never looks back.

So the entire skill in this chapter is not writing greedy code - that part is easy. It is knowing whether greedy is allowed on the problem in front of you.

Where it works, and where it fails

Coin change makes the difference concrete, and it is worth burning into memory because the same code is right or wrong depending on the input rather than the logic.

Making change with coins of 1, 5, 10 and 25, greedy is perfect: always take the largest coin that fits. For 30 it takes 25 then 5 - two coins, and no arrangement does better.

Now change the coin set to 1, 3 and 4, and ask for 6. Greedy takes 4, then 1, then 1 - three coins. But 3 + 3 is two coins. The greedy choice of 4 was locally best and globally wrong, because taking it made the remainder awkward.

Nothing about the algorithm changed. Only the coin set did. That is why 'greedy works for coin change' is a statement about your coins, not about coin change.

int greedyCoins(int[] coins, int amount) {   // coins DESC
    int used = 0;
    for (int c : coins) {
        while (amount >= c) { amount -= c; used++; }
    }
    return amount == 0 ? used : -1;
}

greedyCoins(new int[]{25, 10, 5, 1}, 30);
greedyCoins(new int[]{4, 3, 1}, 6);

coins {25,10,5,1}, amount 30
  take 25 -> 5 left
  take 5  -> 0 left
  greedy = 2 coins        optimal = 2   CORRECT

coins {4,3,1}, amount 6
  take 4  -> 2 left
  take 1  -> 1 left
  take 1  -> 0 left
  greedy = 3 coins        optimal = 2 (3+3)   WRONG

How to know greedy is safe

Two properties must hold. They sound abstract, so take them slowly - between them they explain every greedy proof you will ever read.

Greedy choice property: some optimal solution contains the greedy first choice. Not that greedy stumbles into the optimum by luck, but that taking the greedy step never rules the optimum out.

Optimal substructure: once you have taken that step, the rest of the problem is a smaller version of the same problem, and solving that optimally gives you an optimal whole.

In practice you prove the first with an exchange argument: take any optimal solution that does not start with the greedy choice, swap in the greedy choice, and show the result is no worse. If you can do that, greedy is safe. If the swap makes things worse, you have just found your counterexample - and you need dynamic programming instead, which is the next chapter.

The exchange argument, done concretely

'Prove greedy is safe' sounds like mathematics you do not have time for in an interview. In practice it is one sentence, and it is worth walking through once on a real problem.

Take interval scheduling: pick the most non-overlapping meetings. Greedy takes the one that finishes earliest. Here is the argument that it is safe.

Suppose some optimal schedule exists that does not start with the greedy choice. Swap its first meeting for the greedy one. The greedy meeting finishes no later than the one you removed, so it cannot conflict with anything the optimal schedule took afterwards. The swapped schedule is still valid and still the same size - so it is also optimal, and it starts with the greedy choice.

That is the whole technique: show that swapping in the greedy choice never makes things worse. If you can, greedy is safe. If the swap does make things worse, you have just constructed your counterexample - which is equally useful, because it tells you to reach for dynamic programming instead.

// greedy: sort by END time, take anything that starts after the last finish
Arrays.sort(meetings, Comparator.comparingInt(m -> m[1]));

meetings  (1,3) (2,5) (4,7) (6,8) (8,9)

greedy by END:      (1,3) (4,7) (8,9)   -> 3 meetings
greedy by START:    (1,3) (4,7) (8,9)   -> 3   (works here)
greedy by SHORTEST: (2,5)...            -> 2   BROKEN

counterexample for shortest-first:
  (1,4) (3,5) (4,7)
  shortest is (3,5), which blocks BOTH others -> 1 meeting
  correct answer: (1,4) and (4,7)             -> 2 meetings

Recap

Greedy takes the best-looking step and never reconsiders. That makes it fast and short - and frequently wrong.

It is safe when two properties hold: some optimal solution contains the greedy first choice, and the remaining problem is a smaller version of the same problem.

The practical routine is to spend five minutes actively trying to break your rule on a tiny input before committing to it. The coin example is four numbers long; the interval counterexample is three. If you cannot break it quickly, greedy is probably fine.