Greedy algorithms

Overview

A greedy algorithm builds a solution step by step, always making the choice that looks best right now, and never reconsiders it. When it works it is usually the simplest and fastest solution: often a sort followed by one pass.

The hard part is knowing when greedy is correct. It works when the problem has the greedy-choice property (a locally best choice is part of some optimal solution) and optimal substructure. You justify it with an exchange argument: show that any optimal solution can be changed to include the greedy choice without getting worse. If you cannot, use DP.

When to use it

• Scheduling or selecting intervals: earliest finish, fewest overlaps.
• Assigning resources: match smallest to smallest, largest to largest.
• Reachability with maximum reach tracking (jump game, gas station).
• Building the lexicographically smallest or largest result.
• The problem has a clean exchange argument; otherwise consider DP.

Problem patterns it solves

Where it is used in real software

Key terms

Greedy choice property

A locally optimal choice can be extended to a globally optimal solution.

Exchange argument

Show swapping part of an optimal solution for the greedy choice does not make it worse.

Optimal substructure

After the greedy choice, the rest is a smaller instance of the same problem.

Counterexample

A small input where greedy fails, proving you need another approach.

Designing and verifying a greedy solution

1. 1
   Guess the greedy rule

   Earliest end, smallest first, largest first, best ratio, farthest reach.

2. 2
   Try to break it

   Test 3 to 5 small hand examples, including tricky ones. One counterexample means switch to DP.

3. 3
   Argue exchange

   Take any optimal solution; replace its first choice with the greedy one and show it stays valid and no worse.

4. 4
   Sort if needed

   Many greedy rules need sorted input: O(n log n).

5. 5
   Scan once

   Apply the rule while maintaining a small state: last end, reach, balance.

Gas station (134)

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]

Total gas (15) >= total cost (15), so a solution exists, and it starts at 3. If you run out between start and i, no station in that range can be a valid start, because each of them would arrive at i with even less gas.

Implementation

1function canJump(nums) {2  let reach = 0;3  for (let i = 0; i < nums.length; i++) {4    if (i > reach) return false;          // stuck before i5    reach = Math.max(reach, i + nums[i]);6  }7  return true;8}9 10function canCompleteCircuit(gas, cost) {11  let total = 0, tank = 0, start = 0;12  for (let i = 0; i < gas.length; i++) {13    const diff = gas[i] - cost[i];14    total += diff;15    tank += diff;16    if (tank < 0) {17      start = i + 1; // nothing in [start, i] can work18      tank = 0;19    }20  }21  return total >= 0 ? start : -1;22}23 24// 135. Candy: two passes, each fixes one neighbor constraint25function candy(ratings) {26  const n = ratings.length;27  const give = new Array(n).fill(1);28  for (let i = 1; i < n; i++) if (ratings[i] > ratings[i - 1]) give[i] = give[i - 1] + 1;29  for (let i = n - 2; i >= 0; i--) if (ratings[i] > ratings[i + 1]) give[i] = Math.max(give[i], give[i + 1] + 1);30  return give.reduce((a, b) => a + b, 0);31}32 33// 881. Boats to Save People: heaviest with lightest if possible34function numRescueBoats(people, limit) {35  people.sort((a, b) => a - b);36  let boats = 0, light = 0, heavy = people.length - 1;37  while (light <= heavy) {38    if (people[light] + people[heavy] <= limit) light++;39    heavy--;40    boats++;41  }42  return boats;43}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Applying greedy without checking a counterexample.

  Fix: Always test small tricky inputs, like coins [1, 3, 4] for amount 6.

• Sorting by the wrong key.

  Fix: Interval selection sorts by end, not start. Test both on an example.

• Single pass for two-sided constraints.

  Fix: Candy needs a left pass and a right pass.

Interview questions

Practice problems