Greedy Algorithms

A greedy algorithm builds a solution by repeatedly making the locally best choice and never reconsidering it. When it works, it is the simplest and fastest approach, often $O(n)$ or $O(n\log n)$. When it does not work, it gives wrong answers silently, which is why greedy problems are risky: the code is short, and the difficulty is entirely in knowing that the greedy choice is correct. This chapter teaches the standard greedy patterns and, more importantly, how to justify them.

1. When greedy works

Two properties together make greedy correct:

1. Greedy choice property. A globally optimal solution can be reached by making the locally best choice.
2. Optimal substructure. After making that choice, the remaining problem is a smaller instance of the same problem, and its optimal solution combines with the choice to give an optimal whole.

In an interview you rarely write a full proof, but you should be able to give the core argument. There are two common arguments.

Exchange argument. Take any optimal solution that does not make the greedy choice, and show you can swap in the greedy choice without making the solution worse. So there is always an optimal solution that agrees with greedy. Repeating this shows greedy is optimal.

Greedy stays ahead. Show that after each step, the greedy solution is at least as good as any other solution's partial progress, so it cannot fall behind.

2. How to tell greedy from dynamic programming

Always try to break your greedy idea with a small counterexample. For coin change with coins [1, 3, 4] and amount 6, "take the largest coin" gives 4, 1, 1 (three coins), but 3, 3 (two coins) is better, so greedy fails for that coin system. For the standard coin systems (such as 1, 5, 10, 25), greedy happens to work, but you cannot assume it.

3. Pattern A: sort by a key, then sweep

Activity selection / non-overlapping intervals. Choose the maximum number of non-overlapping intervals. Greedy: sort by end time, and always take the interval that ends earliest and does not overlap what you have. Why: the earliest-ending interval leaves the most room for the rest (exchange argument: swap any chosen first interval for the earliest-ending one without losing anything).

def max_non_overlapping(intervals):
    count, last_end = 0, float("-inf")
    for start, end in sorted(intervals, key=lambda x: x[1]):
        if start >= last_end:
            count += 1
            last_end = end
    return count

assert max_non_overlapping([[1, 2], [2, 3], [3, 4], [1, 3]]) == 3
assert max_non_overlapping([[1, 2], [1, 2], [1, 2]]) == 1
assert max_non_overlapping([]) == 0

Sorting by start time instead would fail: one very long interval that starts first would block many short ones.

Minimum arrows to burst balloons. Balloons are intervals on a line. An arrow at $x$ bursts all balloons covering $x$. Sort by end, shoot at the earliest end, and skip all balloons that overlap that point.

def min_arrows(points):
    arrows, last = 0, float("-inf")
    for start, end in sorted(points, key=lambda p: p[1]):
        if start > last:                   # not burst by the previous arrow
            arrows += 1
            last = end                     # shoot at the earliest end
    return arrows

assert min_arrows([[10, 16], [2, 8], [1, 6], [7, 12]]) == 2
assert min_arrows([[1, 2], [3, 4], [5, 6], [7, 8]]) == 4
assert min_arrows([[1, 2], [2, 3], [3, 4], [4, 5]]) == 2

Assign cookies. Children have greed factors, cookies have sizes. Maximise the number of satisfied children. Sort both, and give each child the smallest cookie that satisfies them.

def find_content_children(greed, cookies):
    greed.sort(); cookies.sort()
    child = 0
    for c in cookies:
        if child < len(greed) and c >= greed[child]:
            child += 1                     # this cookie satisfies the least greedy unsatisfied child
    return child

assert find_content_children([1, 2, 3], [1, 1]) == 1
assert find_content_children([1, 2], [1, 2, 3]) == 2

4. Pattern B: track the best reachable

Jump game. Maintain the furthest reachable index. If the current index is beyond it, you are stuck.

def can_jump(nums):
    furthest = 0
    for i, jump in enumerate(nums):
        if i > furthest:
            return False
        furthest = max(furthest, i + jump)
    return True

assert can_jump([2, 3, 1, 1, 4]) is True
assert can_jump([3, 2, 1, 0, 4]) is False

Jump game II asks for the minimum number of jumps. Treat it as BFS by levels without a queue: within the current jump's reach, track the furthest you could get; when you reach the end of the current reach, you must jump again.

def min_jumps(nums):
    jumps = current_end = furthest = 0
    for i in range(len(nums) - 1):
        furthest = max(furthest, i + nums[i])
        if i == current_end:               # we must jump to go beyond this point
            jumps += 1
            current_end = furthest
    return jumps

assert min_jumps([2, 3, 1, 1, 4]) == 2
assert min_jumps([2, 3, 0, 1, 4]) == 2
assert min_jumps([1]) == 0

Gas station. A circular route with gas at each station and a cost to reach the next. Find a starting station that lets you complete the circuit, or -1. Two facts: if total gas is less than total cost, it is impossible. Otherwise, if the tank runs negative at station $i$ when starting from $s$, no start between $s$ and $i$ works, so try $i+1$.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                       # cannot reach i+1 from any start so far
            start = i + 1
            tank = 0
    return start

assert can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]) == 3
assert can_complete_circuit([2, 3, 4], [3, 4, 3]) == -1

5. Pattern C: process the most constrained or largest first

Task scheduler. Tasks with cooldown $n$ between identical tasks: find the minimum time. The most frequent task determines a skeleton of (max_freq - 1) blocks of length n + 1, and the rest fill the gaps. The answer is at least the number of tasks.

from collections import Counter

def least_interval(tasks, n):
    counts = Counter(tasks).values()
    max_freq = max(counts)
    num_max = sum(1 for c in counts if c == max_freq)          # tasks tied for the highest frequency
    return max(len(tasks), (max_freq - 1) * (n + 1) + num_max)

assert least_interval(["A", "A", "A", "B", "B", "B"], 2) == 8
assert least_interval(["A", "A", "A", "B", "B", "B"], 0) == 6
assert least_interval(["A", "A", "A", "A", "A", "A", "B", "C", "D", "E", "F", "G"], 2) == 16

Partition labels. Split a string into as many parts as possible so that each letter appears in at most one part. Record the last index of each letter. Extend the current part to cover the last occurrence of every letter inside it, and cut when the current index reaches the part's end.

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    result, start, end = [], 0, 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])           # the part must extend to the last use of ch
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    return result

assert partition_labels("ababcbacadefegdehijhklij") == [9, 7, 8]
assert partition_labels("eccbbbbdec") == [10]

Candy. Each child needs at least one candy, and a child with a higher rating than a neighbour must get more. Two passes: left to right ensures the right neighbour rule, right to left ensures the left rule, taking the max.

def candy(ratings):
    n = len(ratings)
    give = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            give[i] = give[i - 1] + 1
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            give[i] = max(give[i], give[i + 1] + 1)
    return sum(give)

assert candy([1, 0, 2]) == 5
assert candy([1, 2, 2]) == 4
assert candy([1, 3, 2, 2, 1]) == 7

The "scan from both sides and combine" technique solves several problems where each element depends on both neighbours, such as trapping rain water and product except self.

6. Pattern D: greedy with a heap

When the "best available" choice changes as you go, keep candidates in a heap.

Connect ropes with minimum cost (Huffman style): always combine the two shortest. Meeting rooms II and IPO (pick the most profitable affordable project) use a heap of candidates.

import heapq

def find_maximized_capital(k, w, profits, capital):
    projects = sorted(zip(capital, profits))              # by required capital
    available, i, n = [], 0, len(projects)
    for _ in range(k):
        while i < n and projects[i][0] <= w:              # all projects we can now afford
            heapq.heappush(available, -projects[i][1])
            i += 1
        if not available:
            break
        w -= heapq.heappop(available)                     # take the most profitable
    return w

assert find_maximized_capital(2, 0, [1, 2, 3], [0, 1, 1]) == 4
assert find_maximized_capital(3, 0, [1, 2, 3], [0, 1, 2]) == 6

7. Pattern E: build the best sequence

Remove $k$ digits to make the smallest number. Greedy with a stack: if the current digit is smaller than the one on top, removing the larger earlier digit makes the number smaller. Pop while you still can.

def remove_k_digits(num, k):
    stack = []
    for d in num:
        while k and stack and stack[-1] > d:
            stack.pop()
            k -= 1
        stack.append(d)
    if k:
        stack = stack[:-k]                    # still need to remove: drop from the end
    return "".join(stack).lstrip("0") or "0"

assert remove_k_digits("1432219", 3) == "1219"
assert remove_k_digits("10200", 1) == "200"
assert remove_k_digits("10", 2) == "0"

Largest number from digits, lexicographically smallest subsequence, wiggle subsequence and queue reconstruction by height all follow this idea: decide what to place first by a clear ordering rule, often with a stack or a sort.

8. Proving a greedy, in practice

A short template for explaining it in an interview:

1. State the greedy rule. "Always pick the interval that ends earliest."
2. Give the intuition. "It leaves the maximum room for later intervals."
3. Sketch the exchange argument. "Suppose an optimal solution picks a different first interval. Replace it with the earliest-ending one. It ends no later, so it overlaps nothing the original did not, and the count is unchanged. So some optimal solution starts with the greedy choice."
4. Test it on a tricky case, including a counterexample you tried and why it does not break the rule.

If you cannot find the argument, fall back on DP, which is correct without a special structural property.

9. Common mistakes

• Assuming greedy works without testing a counterexample.
• Sorting by the wrong key (start versus end versus length), which is the most common error in interval problems.
• Tie-breaking carelessly when keys are equal. Ties can change the outcome.
• Local optimum, global failure, such as the coin example. Greedy is not a default.
• Forgetting the feasibility check (gas station: total gas versus total cost).
• Off-by-one in boundaries, such as < versus <= for touching intervals.
• Leading zeros and the empty-result edge case in digit-building problems.
• Giving a greedy solution with no justification. Interviewers often ask "why is this correct?".

10. Practice set

1. Non-overlapping intervals, minimum arrows to burst balloons, merge intervals.
2. Assign cookies, boats to save people, two city scheduling.
3. Jump game I and II, gas station.
4. Task scheduler, partition labels, candy.
5. Best time to buy and sell stock II (sum of positive differences).
6. Remove $k$ digits, remove duplicate letters, largest number.
7. Queue reconstruction by height, minimum number of platforms.
8. Connect sticks, IPO, course schedule III.
9. Hand of straights, divide array into consecutive subsequences.
10. Lemonade change, valid parenthesis string (a two-bound greedy).