Greedy

How it works

A greedy algorithm makes the locally best choice at each step and never revisits it. When it works it is the simplest and fastest solution available, usually a sort followed by one pass. The hard part is not the code; it is knowing the local choice is safe.

The standard justification is an exchange argument: take any optimal solution that disagrees with your first greedy choice, and show you can swap in the greedy choice without making it worse. If that always works, greedy is optimal.

Greedy often hides behind a running quantity. In jump games you track the farthest reachable index; in gas-station circuits you reset the start whenever the running fuel goes negative; in maximum subarray you drop a prefix the moment its sum turns negative.

Be suspicious when small counterexamples come easily. Coin change with arbitrary coin values is the classic trap: picking the largest coin first fails, and the problem needs DP. Always test the greedy rule on a few tricky inputs before trusting it.

How to attack it

1. 1State the greedy rule in one sentence (always take the earliest end, the largest gap, the cheapest next).
2. 2Try to break it with two or three small counterexamples.
3. 3Sort by the key the rule depends on, if any.
4. 4Maintain the running quantity that the rule reads in one pass.
5. 5Sketch the exchange argument, or fall back to DP if it fails.

Template

A skeleton to adapt, not a solution to paste. Write it from memory a few times.

def can_reach_end(jumps):
    # Track the farthest index reachable so far.
    farthest = 0
    for i, step in enumerate(jumps):
        if i > farthest:
            return False               # stuck before reaching i
        farthest = max(farthest, i + step)
    return True


def circuit_start(gain, cost):
    # If the total is negative no start works; otherwise reset on deficit.
    if sum(gain) < sum(cost):
        return -1
    start, tank = 0, 0
    for i in range(len(gain)):
        tank += gain[i] - cost[i]
        if tank < 0:                   # no station in start..i can be the start
            start, tank = i + 1, 0
    return start


def max_subarray(nums):
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)          # drop a negative prefix
        best = max(best, cur)
    return best

What it costs