Greedy algorithms

The trade greedy makes

DP explores every relevant option and keeps whichever turns out best. Greedy skips that entirely: at each step, take whatever looks best right now, commit to it, and never reconsider. That's a huge shortcut when it works — usually O(n log n) instead of DP's O(n²) or worse — but it only produces the correct answer for problems with a specific mathematical property.

The property that has to hold: the greedy-choice property

A problem is safe for greedy only if a locally optimal choice is always part of some globally optimal solution — choosing it never closes off the best overall answer. If that's not provably true, greedy will find a valid answer, just not always the best one, and it will fail silently — no error, just a wrong result on some input you didn't test.

Worked example: Activity/Interval scheduling

Maximize the number of non-overlapping intervals you can select. The greedy choice: always take the interval that finishes earliest among the remaining valid options.

function maxNonOverlapping(intervals) {
  const sorted = [...intervals].sort((a, b) => a[1] - b[1]); // sort a copy by FINISH time — the entire trick

  let count = 0, lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) { // this one doesn't conflict with our last pick
      count++;
      lastEnd = end;
    }
  }
  return count;
}

Why finish time and not start time or duration: picking whatever finishes earliest leaves the maximum possible room for everything that comes after — any other choice can only leave equal or less room. That's the actual proof sketch, and being able to say it is what separates "I memorized this" from "I understand why it's safe."

Proving the rule: the exchange argument and staying ahead

The sketch above, "finishing earliest leaves the most room", is the idea of a proof. When an interviewer asks "why is that optimal?", you want it in three or four sentences. Two shapes of argument cover almost every greedy rule you will meet, and it helps to see both on the same problem.

The exchange argument: swap in the greedy choice

Take any best schedule and call it O, with its intervals in time order. Let g be the interval the greedy rule picks first, the one that finishes earliest of all. If O already starts with g, there is nothing to show. If not, O starts with some interval o1, and g finishes no later than o1 does, because g finishes earliest of all. Everything else in O starts at or after the end of o1, so it also starts at or after the end of g. Replace o1 with g: no overlap appears, and the count is unchanged. So some best schedule contains the greedy first choice. Now throw away g and every interval that overlaps it. What is left of O is still a valid schedule for the intervals that remain, so the same argument applies to the smaller problem, and repeating it shows the greedy schedule is a best one.

The pattern to copy is: pick an arbitrary best solution, change it so that it agrees with the greedy choice, and show it did not get worse. It suits rules that decide "what goes first" or "who gets matched with whom", and it is the argument behind the cookie, boat and queue problems later in this chapter.

Staying ahead: greedy is never behind

The second shape compares the greedy answer with any other answer step by step and shows it is never behind. For scheduling, let greedy pick g1, g2, ... and let any valid schedule pick o1, o2, ..., both in time order. Claim: the end of gi is never later than the end of oi. For i = 1 this is the rule itself. If it holds for i, then oi+1 starts after oi ends, which is not before gi ends, so oi+1 was available when greedy chose its next interval. Greedy picks the earliest finish among the available ones, so gi+1 ends no later than oi+1. If the other schedule had more intervals than greedy, its extra interval would start after greedy's last end and greedy would not have stopped, a contradiction. So greedy has at least as many.

This one suits a process that moves forward and is summarised by a single number: a finish time, the farthest index reached, the fuel left. Jump Game is the same proof in miniature, because after each step the greedy "farthest reachable" is at least what any other strategy has reached.

Hunting for a counterexample before you trust a rule

A proof takes minutes to write, and a counterexample takes seconds to find if you let the machine look. Keep a slow, obviously correct brute force next to the greedy rule, feed both random small inputs, and stop at the first disagreement. Small inputs matter: counterexamples to greedy rules usually need only three to five items, and a narrow range of values forces the ties and touching endpoints where rules break.

function bruteMaxNonOverlapping(intervals) {
  const n = intervals.length;
  let best = 0;
  for (let mask = 0; mask < (1 << n); mask++) { // every subset of the intervals
    const chosen = [];
    for (let i = 0; i < n; i++) if (mask & (1 << i)) chosen.push(intervals[i]);
    chosen.sort((a, b) => a[0] - b[0]);
    let ok = true;
    for (let i = 1; i < chosen.length; i++) {
      if (chosen[i][0] < chosen[i - 1][1]) { ok = false; break; } // overlaps its neighbour
    }
    if (ok) best = Math.max(best, chosen.length);
  }
  return best;
}

function findCounterexample(greedy, brute, makeInput, tries = 2000) {
  for (let t = 0; t < tries; t++) {
    const input = makeInput();
    if (greedy(input) !== brute(input)) return input; // the first input where they disagree
  }
  return null;
}

Try it on the tempting wrong key, sorting by start time:

function maxNonOverlappingByStart(intervals) {
  const sorted = [...intervals].sort((a, b) => a[0] - b[0]); // the tempting but wrong sort key
  let count = 0, lastEnd = -Infinity;
  for (const [start, end] of sorted) {
    if (start >= lastEnd) {
      count++;
      lastEnd = end;
    }
  }
  return count;
}

Calling findCounterexample(maxNonOverlappingByStart, bruteMaxNonOverlapping, makeInput) with a generator of five or fewer random intervals finds a failing input within a few dozen tries: in a run of 20,000 random inputs about one in ten disagreed with the brute force. The shape to expect is [[1, 10], [2, 3], [4, 5]]: sorted by start, the long interval comes first and blocks the other two, so the rule returns 1 while the best schedule has 2. The same call with the finish-time rule returns null.

Worked example: Jump Game — can you reach the end?

function canJump(nums) {
  let farthestReachable = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > farthestReachable) return false; // stuck — can't even reach index i
    farthestReachable = Math.max(farthestReachable, i + nums[i]);
  }
  return true;
}

The greedy insight: you never need to know which path gets you furthest, only the single number "furthest index reachable so far" — tracking every possible path (which DP would do) is unnecessary work because only the maximum ever matters for future decisions.

Jump Game II: the fewest jumps, one boundary at a time

Now the end is always reachable and you want the fewest jumps to get there. Trying every sequence of jumps is exponential, and a DP over "fewest jumps to each index" is O(n²) because each index looks at all the indices it can jump to. The greedy view is a breadth-first search without the queue. Look at the set of indices reachable with j jumps. It is a block that starts at index 0 and ends at some index currentEnd: if you can land on an index, you can also land on any earlier one with no more jumps, by jumping a bit shorter. The block reachable with j + 1 jumps therefore ends at the farthest reach i + nums[i] of any index i inside the current block.

So scan left to right, keep the farthest reach seen so far, and every time you step past the end of the current block you must spend one more jump, and the new block ends at that farthest reach.

function jump(nums) {
  let jumps = 0, currentEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) { // the last index reachable with the current number of jumps
      if (farthest <= i) return -1; // nothing beyond i is reachable
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

Dry run: jump([2, 3, 1, 1, 4])

The first jump covers indices 1 to 2. Looking inside that block, index 1 reaches farthest (1 + 3 = 4), so the second jump covers the last index, and the answer is 2. You never decide which index to jump from; you only record how far the best one could have taken you. The loop is O(n) time and O(1) space, and the proof is the staying-ahead argument above: after every jump, currentEnd is as far as any strategy with that many jumps could be.

Worked example: Gas Station

function canCompleteCircuit(gas, cost) {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    tank += diff;
    if (tank < 0) {       // can't reach the next station from any point up to here
      start = i + 1;       // so the answer, if any, must start AFTER i
      tank = 0;
    }
  }
  return total >= 0 ? start : -1; // total < 0 means no valid start exists anywhere
}

Dry run: gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]

total ends at 0 (≥ 0, so a valid start exists) and the last reset left start = 3 — station 3 is the answer. Every candidate start before index 3 failed somewhere on the way to it, so none of them could ever have worked either, which is exactly the argument below.

This one's greedy argument is subtler: if the tank goes negative arriving at station i, starting from any station between the current start and i would also fail, because each of those partial sums was non-negative up to the point of failure — so it's always safe to jump the candidate start forward to i + 1 without missing a valid answer.

Candy: two passes, one constraint each

Children stand in a line with ratings. Each gets at least one candy, and a child with a higher rating than a neighbour must get more candy than that neighbour. Find the fewest candies. Each child has two constraints, one against the left neighbour and one against the right, and they pull against each other. Trying to satisfy both in one pass is where people get stuck. Split them: handle the left neighbours in one pass and the right neighbours in another, always giving the smallest number that works.

Left to right, a child rated higher than the one on their left gets one more than that child, and everyone else stays at 1. Now every left constraint holds, and each number is the smallest that makes it so. Then right to left, a child rated higher than the one on their right needs more than that child. But they may already hold a larger number from the first pass, and lowering it would break a left constraint. So the second pass raises the number to the larger of what it has and what the right neighbour requires.

function candy(ratings) {
  const n = ratings.length;
  const give = new Array(n).fill(1); // everyone gets at least one

  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) give[i] = give[i - 1] + 1; // beat the left neighbour
  }
  for (let i = n - 2; i >= 0; i--) {
    if (ratings[i] > ratings[i + 1]) give[i] = Math.max(give[i], give[i + 1] + 1); // and the right one
  }
  return give.reduce((sum, x) => sum + x, 0);
}

Dry run: ratings [1, 0, 2]

The total is 5. The second pass shows why the Math.max matters. With ratings [1, 3, 4, 5, 2] the first pass gives [1, 2, 3, 4, 1]. At the peak, 5 is higher than the 2 on its right, which needs only 1 + 1 = 2 candies, but the peak already holds 4 from the climb. Assigning 2 would break the rule with the 4-rated neighbour on its left, so the second pass keeps 4 and the total is 11. Children with equal ratings do not constrain each other: [1, 2, 2] gets [1, 2, 1], which is 4. Time is O(n) and space is O(n) for the array of candies.

Partition Labels: each letter's last occurrence sets the cut

Cut a string into as many parts as possible so that no letter appears in more than one part, and return the size of each part. A letter that appears twice forces everything between its first and last occurrence into one part. Chasing those overlaps is the same merging problem as intervals, but there is a shortcut: you only need the last index of each letter. Walk the string, keep the farthest last-occurrence of any letter you have passed, and the moment the walk reaches that index, every letter in the part ends here, so you can cut.

function partitionLabels(s) {
  const last = new Map();
  for (let i = 0; i < s.length; i++) last.set(s[i], i); // last index of each letter

  const sizes = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i])); // the part must reach this letter's last occurrence
    if (i === end) { // nothing inside the part reaches beyond here: cut
      sizes.push(end - start + 1);
      start = i + 1;
    }
  }
  return sizes;
}

Dry run: partitionLabels("abcabdd")

last occurrences: a = 3, b = 4, c = 2, d = 6

The result is [5, 2]. Cutting at the earliest possible point is safe because any valid partition must put everything up to that end into one part, so a cut anywhere earlier is impossible and a later one only makes the parts fewer. The first loop is O(n) and the second is O(n), with at most one entry per distinct letter in the map. A common slip is to use each letter's first occurrence, or to return the cut positions when the question asks for the sizes.

Sort, then match from the right end: Assign Cookies and Boats

A large family of greedy problems is "sort, then pair things off". The skill is deciding which end to serve first. Two small examples show how the exchange argument picks it.

Assign Cookies

Each child has a greed factor, each cookie has a size, and a child is happy with a cookie at least as big as their greed. Each cookie goes to at most one child. Maximise the number of happy children. Serve the least greedy child first, with the smallest cookie that satisfies them. A cookie too small for the least greedy child is too small for everyone, so it is thrown away. Why is the smallest sufficient cookie a safe choice? In any best plan, if that cookie went to another child, or to nobody, give it to the least greedy child instead. If the least greedy child held a different cookie, that cookie is at least as big as this one, so it still satisfies whoever received this one. The number of happy children does not drop, and the bigger cookies stay available for greedier children.

function findContentChildren(greed, cookies) {
  const children = [...greed].sort((a, b) => a - b);
  const sizes = [...cookies].sort((a, b) => a - b);
  let child = 0;
  for (let cookie = 0; cookie < sizes.length && child < children.length; cookie++) {
    if (sizes[cookie] >= children[child]) child++; // the smallest cookie that satisfies the least greedy child
  }
  return child;
}

With greed [1, 2, 3] and cookies [1, 1], the first cookie satisfies the child with greed 1, and the second is too small for the child with greed 2 and is dropped, so the answer is 1. Time is O(n log n + m log m) for the two sorts, and the matching pass is linear.

Boats to Save People

Each boat carries at most two people and a total weight of at most limit, and every person alone fits. Use the fewest boats. Look at the heaviest person H and the lightest person L. If L and H cannot share a boat, no one can share with H, so H rides alone. If they can, pair them, and the exchange argument says that is safe. Suppose some best plan has H with a partner P and L with a partner Q. Regroup the four as (L, H) and (P, Q). Since L weighs no more than P, L + H is at most P + H. Since Q weighs no more than H, P + Q is at most P + H. Both are within the limit because P + H was, and the number of boats is the same.

function numRescueBoats(people, limit) {
  const weights = [...people].sort((a, b) => a - b);
  let light = 0, heavy = weights.length - 1, boats = 0;
  while (light <= heavy) {
    if (weights[light] + weights[heavy] <= limit) light++; // the lightest rides with the heaviest
    heavy--; // the heaviest always leaves in this boat
    boats++;
  }
  return boats;
}

Dry run: numRescueBoats([3, 2, 2, 1], 3)

sorted weights: [1, 2, 2, 3]

The loop condition is light <= heavy, so the final person, when both pointers meet, still gets a boat. Time is O(n log n) for the sort and O(n) for the two-pointer sweep. The code assumes every person's weight is at most limit; if that were not promised, you would first have to say what to do about someone who cannot ride at all.

Queue Reconstruction by Height: place the tallest first

Each person is a pair [h, k]: height h, and exactly k people in front of them who are at least as tall. Rebuild a queue that satisfies everyone. The trick is to build the queue in the order that makes each placement final. When you place a person, consider only taller or equal people: if you have inserted people from tallest to shortest, then everyone already in the queue is at least as tall, so inserting at index k puts exactly k of them in front. People inserted later are shorter, so they never change the count of anyone placed before.

Sort by height descending. Break ties by k ascending, so that among equal heights the one with fewer people in front goes in first and the next one counts it correctly.

function reconstructQueue(people) {
  const sorted = [...people].sort((a, b) => b[0] - a[0] || a[1] - b[1]); // tallest first, fewer-in-front first
  const queue = [];
  for (const person of sorted) {
    queue.splice(person[1], 0, [...person]); // k taller people are already placed: insert at index k
  }
  return queue;
}

Dry run: [[7, 0], [4, 4], [7, 1], [5, 0], [6, 1], [5, 2]]

Check the pair [6, 1]: in the final queue, exactly one person before it, the 7, is at least as tall. Each splice shifts the elements after the insertion point, so the worst case is O(n²) for the inserts on top of the O(n log n) sort. If the tie-break were k descending, the person with more people in front would go in first and be shifted out of position by the one inserted after. The code sorts a copy and stores copies of the pairs, so the caller's data is never changed.

Minimum Arrows to Burst Balloons: the same shape as interval scheduling

Each balloon is a horizontal span [xStart, xEnd], and an arrow shot straight up at x bursts every balloon whose span contains x, ends included. Find the fewest arrows. Sort by the right end and shoot the first arrow at the right end of the first balloon: that is as far right as an arrow can go while still hitting it, so it hits as many later balloons as possible. Every balloon whose start is at or before that point is burst. The first balloon that starts after it needs a new arrow, again at its right end.

function findMinArrowShots(points) {
  if (points.length === 0) return 0;
  const sorted = [...points].sort((a, b) => a[1] - b[1]); // by right end
  let arrows = 1, arrowAt = sorted[0][1]; // shoot at the first balloon's right end
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i][0] > arrowAt) { // starts after the arrow: not hit, so shoot again
      arrows++;
      arrowAt = sorted[i][1];
    }
  }
  return arrows;
}

Dry run: [[10, 16], [2, 8], [1, 6], [7, 12]]

sorted by right end: [1, 6], [2, 8], [7, 12], [10, 16]

The answer is 2. The arrow count equals the largest number of balloons that can be picked so that no two share a point, which is the scheduling problem from earlier with one change: here two spans that only touch, like [1, 2] and [2, 3], share the point 2 and one arrow bursts both, so the test is a strict >, where the scheduling code used >=. The intervals chapter lines up this touching rule for every interval problem side by side. Time is O(n log n).

Greedy on counts: Task Scheduler and Reorganize String

Some greedy problems are about how often each item occurs, and the busiest item sets the shape of the whole answer. Both problems below have a heap solution (always take the most frequent item that is allowed), which the heaps chapter covers. Here is the version that needs no heap, with the reason it works.

Task Scheduler: the busiest task sets the frame

Each task takes one time unit, the CPU may idle, and two runs of the same task must be at least n units apart. Return the fewest units. Let the most frequent task occur m times. Its occurrences need m - 1 gaps, and each gap, together with the run before it, spans n + 1 units: A _ _ A _ _ A for n = 2. The last occurrence closes the frame, along with any other task that is tied for the highest count. So the frame has length (m - 1) × (n + 1) + withMax, where withMax is how many tasks occur exactly m times. No schedule can be shorter. The other tasks drop into the empty slots of the frame. If there are so many of them that they do not fit, the schedule never has to idle at all, and the answer is simply the number of tasks.

function leastInterval(tasks, n) {
  const counts = new Map();
  for (const task of tasks) counts.set(task, (counts.get(task) || 0) + 1);

  let maxCount = 0;
  for (const count of counts.values()) maxCount = Math.max(maxCount, count);
  let withMax = 0;
  for (const count of counts.values()) if (count === maxCount) withMax++;

  const frame = (maxCount - 1) * (n + 1) + withMax; // the busiest task sets the frame
  return Math.max(tasks.length, frame); // enough other tasks fill every idle slot
}

Dry run: AAABBB with n = 2, then AAABBCCDE with n = 2

The first schedule is A B _ A B _ A B: eight units with two idles. In the second, the other six tasks fill the gaps and spill over, so every unit can be busy, and a valid order exists such as A B C A B C A D E. The code counts with a Map in O(n) time, and only the number of distinct tasks is stored.

Reorganize String: fill the even slots first

Rearrange a string so that no two equal letters are adjacent, or return the empty string if that is impossible. If one letter occurs more than ceil(length / 2) times, no arrangement exists, because that letter would need more slots than there are pairwise non-adjacent positions. Otherwise lay the letters down one letter at a time, most frequent first, into the slots 0, 2, 4, ... and then, when those are full, 1, 3, 5, ...

function reorganizeString(s) {
  const counts = new Map();
  for (const ch of s) counts.set(ch, (counts.get(ch) || 0) + 1);

  const letters = [...counts.keys()].sort((a, b) => counts.get(b) - counts.get(a)); // most frequent first
  if (s.length > 0 && counts.get(letters[0]) > Math.ceil(s.length / 2)) return "";

  const out = new Array(s.length);
  let pos = 0;
  for (const ch of letters) {
    for (let k = 0; k < counts.get(ch); k++) {
      out[pos] = ch;
      pos += 2; // skip a slot so equal letters are never neighbours
      if (pos >= s.length) pos = 1; // evens are full: continue on the odd slots
    }
  }
  return out.join("");
}

Why can a letter never touch itself? Each letter's slots are consecutive in that fill order. A letter that sits entirely in even slots, or entirely in odd slots, has slots two apart. Only a letter that starts on an even slot and runs on into the odd slots could land next to itself, and it would need more occurrences than the letter laid down before it, which the sort order rules out. The first letter cannot wrap, because the check above guarantees it fits in the even slots. For "aaabbc" the fill order gives a at 0, 2, 4, then b at 1 and 3, then c at 5: "ababac". For "aaab" the letter a occurs 3 times, more than ceil(4 / 2) = 2, so the answer is the empty string. Time is O(n + k log k) for k distinct letters.

Valid Parenthesis String: track the range of open brackets

A string holds (, ) and *, where a star may be (, ) or nothing. Is there a way to choose the stars so the brackets balance? Trying every choice is 3^k for k stars. Instead of choosing, track every count of open brackets that is still possible. That set is always a block of consecutive integers, so two numbers describe it: lo, the fewest brackets that could be open, and hi, the most. A ( moves both up by one, a ) moves both down by one, and a star widens the block: it could close one (lo - 1), open one (hi + 1) or do nothing.

Two repairs keep the block honest. If hi drops below 0, even treating every star as an opening bracket leaves a ) with no partner, so the string is invalid. And lo is clamped at 0, because a negative count of open brackets is not a possible state; it only means some of the choices are impossible. At the end the string is valid exactly when 0 is inside the block, and since lo was clamped, that means lo === 0.

function checkValidString(s) {
  let lo = 0, hi = 0; // fewest and most "(" that could still be open
  for (const ch of s) {
    if (ch === "(") { lo++; hi++; }
    else if (ch === ")") { lo--; hi--; }
    else { lo--; hi++; } // a star could close one, do nothing, or open one
    if (hi < 0) return false; // even with every star as "(", a ")" has no partner
    if (lo < 0) lo = 0; // "fewest open" cannot go below zero
  }
  return lo === 0; // some choice of stars closes everything
}

Dry run: checkValidString("(*))")

hi never goes below 0 and lo ends at 0, so the string is valid: read the star as ( and you get (()). The string ")*(" fails at the first character, because hi becomes -1 at once. Forgetting the clamp on lo is the usual bug: "*)" is valid (read the star as (), but without the clamp lo ends at -2 and the string is wrongly rejected. One pass, O(n) time, O(1) space.

Best Time to Buy and Sell Stock II: add up every rise

With as many buy-and-sell pairs as you like (holding at most one share at a time), the profit is the sum of every day-to-day rise. Any profitable transaction from day i to day j is the sum of the daily changes in between, and it cannot beat the sum of the positive daily changes alone, because the positive ones are all of the gain and the negative ones only subtract. Buying at the start of every rise and selling at its end collects exactly the positive changes.

function maxProfitMany(prices) {
  let profit = 0;
  for (let i = 1; i < prices.length; i++) {
    if (prices[i] > prices[i - 1]) profit += prices[i] - prices[i - 1]; // collect every rise
  }
  return profit;
}

For [7, 1, 5, 3, 6, 4] the rises are 1 to 5 (4) and 3 to 6 (3), and the profit is 7. The same answer comes from "buy at 1, sell at 5, buy at 3, sell at 6". Time is O(n), space O(1). The moment a rule is added that changes what a transaction costs or when you may start another, this stops being greedy: a cooldown after selling, a fee per transaction, or a cap on the number of transactions all need a small DP over "holding" and "not holding", which is in DP state machines.

Where greedy is exactly right: fractional knapsack and Huffman coding

Fractional knapsack, and why the 0/1 version is different

You have items with a weight and a value, a bag with a weight limit, and you may take part of an item. Take items in order of value per unit of weight, the best ratio first, and split the last one that does not fit whole. The exchange argument is one line: if a plan uses some weight on a lower-ratio item while a higher-ratio item still has unused weight, move that weight across and the value goes up or stays equal.

function fractionalKnapsack(items, capacity) {
  const sorted = [...items].sort((a, b) => b[1] / b[0] - a[1] / a[0]); // best value per unit of weight first
  let value = 0, room = capacity;
  for (const [weight, worth] of sorted) {
    if (room === 0) break;
    const take = Math.min(weight, room); // all of it, or whatever still fits
    value += worth * (take / weight);
    room -= take;
  }
  return value;
}

With items [weight, value] of [10, 60], [20, 100] and [30, 120] and a limit of 50, the ratios are 6, 5 and 4. Take all of the first (60), all of the second (100), and 20 of the 30 units of the third (80): total 240. Weights must be positive, or the ratio divides by zero.

The identical data under the 0/1 rule, where an item is taken whole or not at all, gives a different story. Ratio order takes the first two items, weight 30 and value 160, and the third no longer fits. But the second and third items together weigh exactly 50 and are worth 220. The splitting freedom is what made greedy safe, and without it the problem is the 0/1 knapsack, which needs the table in the 2D DP chapter.

Huffman coding: always merge the two lightest

A prefix code gives each symbol a bit string so that no code is the start of another. Frequent symbols should get short codes. Huffman's rule builds the best code tree from the bottom: repeatedly take the two lightest nodes, merge them under a new node whose weight is their sum, and put that node back. The total cost of the code, the sum over symbols of frequency times code length, equals the sum of all the merged weights, because each merge adds the weight of everything below it one level deeper.

The standard implementation uses a min-heap. There is a heap-free version that is easy to write: sort the frequencies once, and keep the merged sums in a second queue. The sums come out in non-decreasing order, because each merge takes the two smallest items available and the smallest items only grow, so the second queue stays sorted by itself. At each step the two smallest are among the fronts of the two queues.

function huffmanCost(freqs) {
  if (freqs.length < 2) return 0;
  const leaves = [...freqs].sort((a, b) => a - b);
  const merged = []; // sums come out in non-decreasing order, so a plain queue stays sorted
  let i = 0, j = 0, total = 0;

  const takeSmallest = () => {
    if (j >= merged.length || (i < leaves.length && leaves[i] <= merged[j])) return leaves[i++];
    return merged[j++];
  };

  for (let step = 0; step < freqs.length - 1; step++) {
    const sum = takeSmallest() + takeSmallest(); // merge the two lightest
    merged.push(sum);
    total += sum;
  }
  return total;
}

Dry run: huffmanCost([5, 9, 12, 13, 16, 45])

The cost is 224. With n symbols there are n - 1 merges. Sorting is O(n log n) and the merging is O(n) after it. The heap version is O(n log n) throughout; it is the same loop as the heap exercise on connecting sticks at the lowest total cost. The proof is again an exchange argument: the two rarest symbols can always be made siblings at the deepest level of some best tree.

Where greedy fails: three counterexamples to keep in your head

All three rules sound reasonable, all three work on many inputs, and each fails on an input small enough to write on a whiteboard. Keep these three in mind as a reflex: before you commit to a greedy rule, spend a minute looking for a small input where it fails, which is what the stress test above automates.

Greedy vs DP — how to decide which one a problem wants

Recognizing it in an unseen problem

• "Minimum number of," "maximum number of," where a sorted, greedy-order decision seems natural
• You can articulate why the greedy choice never eliminates the optimal answer — if you can't, don't trust it
• Scheduling, interval, and "assign resources" problems are greedy's home turf
• "Sort, then pair the ends": cookies to children, people to boats, anything where the extreme item should take the partner that costs the least
• One number summarises progress (farthest reach, finish time, fuel, open brackets) → a single pass that keeps only that number, often with a range instead of a choice
• Counts decide the answer (the busiest task, the most frequent letter) → build the frame the busiest item forces, then fit the rest into it
• A rule that sounds right but you cannot prove → test it against a brute force on small random inputs, and keep the three counterexamples above in mind
• Changing the problem slightly (fractions allowed, a cooldown, a fee, a cap on transactions) can flip it between greedy and DP, so re-check the property each time
• When in doubt in an interview: try to prove greedy for a minute; if you can't, say so and switch to DP rather than silently guessing