// Greedy

core idea

Greedy makes one irreversible, locally-best choice per step and never reconsiders it — no backtracking, no trying alternatives, no remembering the runner-up. That only pays off when you can prove the local choice never costs you the global optimum. Skip the proof and greedy still runs, still returns an answer, and is sometimes silently wrong — which is what makes it more dangerous to reach for on instinct than a pattern that simply fails loudly. The proof almost always takes one of three shapes:

when to reach for it

• A single forward pass with one running variable — a minimum, a frontier, a running total — is enough. You never need to remember every option seen, only the best one so far.
• The question asks for a max/min produced by an irreversible sequence of choices: “maximum profit from one transaction”, “minimum jumps to the end”, “can you complete the circuit”.
• You can state the exchange or never-regret argument in one sentence. If you can’t, you likely need dynamic programming instead — DP keeps every option alive until it’s provably dominated; greedy throws options away the moment it moves on.
• Sorting first turns the problem into one clean pass — intervals is the deepest example of this move.

universal templates

Track & decide — the shape behind three of the four problems below:

public int TrackAndDecide(int[] nums)
{
    var best = InitialBest();          // the answer if we stopped right now
    var running = Seed(nums[0]);       // the one number greedy needs to remember

    for (int i = 1; i < nums.Length; i++)
    {
        best = Combine(best, running, nums[i]);   // score this step against what's tracked
        running = Update(running, nums[i]);       // fold today into the running invariant
    }
    return best;
}

running is a minimum (cheapest price seen), a maximum (furthest reachable index), or a running sum (fuel remaining) depending on the problem — the shape of the loop never changes, only what Update and Combine compute.

Extend a boundary until it closes — Partition Labels’ shape:

public List<int> ExtendUntilClose(string s, Dictionary<char, int> lastIndex)
{
    var result = new List<int>();
    int start = 0, end = 0;

    for (int i = 0; i < s.Length; i++)
    {
        end = Math.Max(end, lastIndex[s[i]]);   // widen to cover this item's whole span
        if (i == end)                            // nothing after i can pull the boundary further
        {
            result.Add(end - start + 1);
            start = i + 1;
        }
    }
    return result;
}

problems

Four problems, three proof shapes: buy-sell-stock and jump-game are both never-regret arguments with different running invariants, gas-station is restart-past-failure, and partition-labels is the boundary-close template wearing an interval-merge costume.

1. 01Best Time to Buy and Sell StockeasyLC #121

   Track the cheapest buy so far; every day asks "sell today?"

2. 02Jump GamemediumLC #55

   Furthest-reachable frontier — one variable, one pass.

3. 03Gas StationmediumLC #134

   If you run dry at i, no start before i works — restart at i+1.

4. 04Partition LabelsmediumLC #763

   Greedy + hashmap: extend the partition to each char's last index.