Greedy

Commit and move on

A greedy algorithm makes the best choice available right now, hoping the sum of local optima is the global optimum. It never reconsiders a past decision — no backtracking, no memo table. That's why it's usually O(n) or O(n log n) with O(1) extra space.

The cleanest interview example is Jump Game (LC 55): can you reach the last index if each value is your max jump length? The entire greedy state is one number — the farthest index reachable so far.

The two properties, and how to prove them

Greedy is only correct when both of these hold:

• Greedy choice property — a locally optimal choice leads to a globally optimal solution. You never need to reconsider.
• Optimal substructure — after making the greedy choice, what remains is a smaller instance of the same problem.

vsGreedy or DP?

P1Exchange argument

Show that swapping any non-greedy choice for the greedy choice does not worsen the solution. The classic: activity selection (pick the maximum number of non-overlapping intervals) — always pick the interval that ends earliest.

P2Greedy stays ahead

By induction, show the greedy solution is at least as good as any alternative after every step. If it's never behind, it can't lose at the end.

When to reach for it

• "Find the minimum number of X to cover/complete something."
• "Schedule tasks or intervals optimally."
• "Maximize/minimize with a simple local rule."
• The problem involves sorting, then making sequential choices.
• The locally optimal move feels obviously correct — and you can argue why.

Sort first, or track a running quantity

Nearly every greedy problem falls into one of two families: sort to make the greedy choice obvious, or track a running quantity in a single pass.

G1Jump Game — track the farthest reach

def can_jump(nums):
    farthest = 0

    for i in range(len(nums)):
        if i > farthest:
            return False          # Can't reach this index
        farthest = max(farthest, i + nums[i])

    return True

G2Jump Game II — BFS-like levels

Minimum number of jumps: treat each jump as a BFS level. Extend the farthest reach while walking the current level; when you hit the level's end, you must jump.

def jump(nums):
    jumps = 0
    curr_end = 0       # End of current jump range
    farthest = 0       # Farthest we can reach

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        if i == curr_end:          # Must jump now
            jumps += 1
            curr_end = farthest

    return jumps

G3Gas Station — track the surplus

If sum(gas) >= sum(cost), a solution exists. Greedy: whenever the running surplus goes negative, none of the stations so far can be the start — restart from the next one.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1

    start = 0
    surplus = 0

    for i in range(len(gas)):
        surplus += gas[i] - cost[i]
        if surplus < 0:
            start = i + 1       # Restart from next station
            surplus = 0

    return start

G4Partition Labels — track the last occurrence

Extend each partition to include the last occurrence of every character seen in it. When the scan index reaches the current partition's end, cut.

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    result = []
    start = end = 0

    for i, ch in enumerate(s):
        end = max(end, last[ch])    # Extend partition
        if i == end:                # Reached the end of partition
            result.append(end - start + 1)
            start = end + 1

    return result

G5Task Scheduler — the frequency formula

The most frequent task dictates the minimum time — lay it out first with cooldown gaps, then fill.

def least_interval(tasks, n):
    from collections import Counter

    freq = list(Counter(tasks).values())
    max_freq = max(freq)
    max_count = freq.count(max_freq)   # How many tasks have max frequency

    # Minimum from formula
    intervals = (max_freq - 1) * (n + 1) + max_count

    # Can't be fewer than total tasks
    return max(intervals, len(tasks))

G6Min Arrows — sort by end point

The interval-scheduling greedy choice in its purest form: sort balloons by end point, shoot at the end of the first unburst balloon, and let one arrow take out everything that overlaps.

Where greedy goes wrong