Greedy

To schedule the most meetings, is choosing the earliest finish safe? Examples are not a proof. Show that replacing the first meeting of an optimal schedule leaves room for all later meetings.

Every greedy problem has to pass three checks:

1. You can name the choice. Say in one sentence what you pick at each step: the interval that ends earliest, the position that reaches farthest, the lowest price so far. If you can't say it, it isn't a greedy algorithm yet.
2. You can say why it's safe. Why this choice never throws away the optimum. Two arguments cover most problems: stays ahead, where some quantity the greedy maintains is never worse than in any other plan after each step; and the exchange argument, where you take any optimal solution, swap its first choice for the greedy one, and show the result is no worse.
3. If you can't argue it, test it. When the proof won't come together, compare against brute force on small inputs. A counterexample means the problem wants DP.

The article goes in this order, and each step adds exactly one idea:

When to Use This Pattern

Brute force enumerates every plan: which intervals to keep, in what order, where to jump at each step. That's usually exponential. DP merges the plans that reach the same state, but each state often still looks back at many predecessors, so O(n²) is common. Greedy is faster because it proves that each step only needs one candidate.

Take Jump Game (LC 55, where nums[i] is the farthest you may jump right from i) with nums = [2, 3, 1, 1, 4]. The DP asks "can I reach i? only if some reachable j can jump to it", which rescans everything before every i. Greedy keeps a single number, farthest: the farthest index reachable using cells 0..i.

As long as i <= farthest, i is reachable, and we don't care which cell we jumped from. Dropping the "jumped from where" information turns O(n²) into O(n). The reason we're allowed to drop it is the safety argument from the second check.

Recognition Checklist

• The problem asks for an optimum (most, fewest, largest) that breaks into a sequence of "which one do I pick" decisions
• You can say "at each step pick the most X one" and explain why that never loses
• The input is intervals or time ranges, and after sorting each item only needs to be compared with the last one kept
• The DP you wrote only uses the previous state, or only the best one so far
• Each step takes an extreme value from a candidate set that keeps changing
• A brute-force comparison on small inputs found no counterexample

Before You Code

Answer these three on paper before writing code. They map onto the three checks: the first decides what the code looks like, the second convinces you it's right, and the third stops you when the second was wrong.

1. What is the greedy choice? One sentence: "at each step, pick X". For sorting problems, also say what you sort by.
2. Why is it safe? Pick one argument and say it out loud. Stays ahead: name the quantity the greedy maintains and explain why no other plan can beat it at this step. Exchange: take any optimal solution, swap the first choice where it differs from greedy for the greedy choice, and show the swap breaks no constraint and doesn't make the answer worse.
3. Does a brute-force check find a counterexample? Decide how the brute force works (all subsets, all orders, or just the DP) and compare on random small inputs.

Try it on LC 435 Non-overlapping Intervals (remove the fewest intervals so the rest don't overlap; touching endpoints don't count as overlap) with intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]:

• Greedy choice: the fewest removals is n minus the most you can keep. Sort by end time, and keep an interval whenever it doesn't overlap the last one kept.
• Why it's safe: let A be the earliest-ending interval in some optimal solution and G the earliest-ending interval overall, so G.end <= A.end. Swap A for G. Every other interval in that optimal solution starts after A ends, so it also starts after G ends; nothing conflicts and the count is unchanged. So picking G first never loses, and what's left is "keep choosing among intervals that start after G ends", where the same argument applies again.
• Brute-force check: try subset sizes from largest to smallest and return the first size with a pairwise non-overlapping subset. Swap the greedy for "sort by start time" and the comparison quickly finds a counterexample such as [[0, 10], [1, 2], [3, 4]]: sorting by start keeps [0, 10] first, both others conflict with it, and you keep 1 when the optimum keeps 2.

The testing habit is worth making routine. Write the brute force in the dumbest way that can't be wrong. Keep inputs to six items or fewer with small values, so the brute force runs and any counterexample is short enough to trace by hand. Fix the random seed so a failure reproduces. The classic counterexample is coin change: coins [1, 3, 4] making 6, where "take the largest coin first" gives 4 + 1 + 1, three coins, while 3 + 3 uses two. That one is a DP problem.

Step 3 turns 435 into code.

Best Time to Buy and Sell Stock (LeetCode 121)

Given nonnegative daily prices, buy at most once and sell on a later day; return maximum profit. No trade is allowed, so falling prices give zero. Do not sum profits from several trades or return trading dates.

Input: prices = [4, 2, 5, 1, 3]. Expected: 3 (buy at 2, sell at 5).

Each day, the question is: if I sell today, what is the best profit? That means buying at the cheapest day before or on today.

1. Walk it by hand

2. Read the rule off the table

• Every row first updates min_price with today's price.
• Then it computes the profit of selling today, p - min_price, and keeps the larger of that and best.
• min_price only includes days up to today, so a low price that comes later (row 4) is never used for an earlier sale.

3. Turn each row into code

def max_profit(prices):
    min_price = float("inf")
    best = 0
    for p in prices:
        min_price = min(min_price, p)
        best = max(best, p - min_price)
    return best

Core Templates

All five steps follow the same routine: answer the three questions, then run the three checks from the top: you can name the choice, you can say why it's safe, and testing finds no counterexample.

Step 1: One Variable That Stays Ahead

Problem: given daily stock prices, buy once and sell once; return the maximum profit (LC 121).

The input is a list of daily prices prices (nonnegative integers). Buy at most once and sell at most once, and return the maximum profit. The buy must come before the sell. If no trade makes money, you may skip trading and return 0.

For example, [7, 1, 5, 3, 6, 4] → 5: buy at 1 on day 2 and sell at 6 on day 5. [7, 6, 4] → 0: the price only falls, so don't trade.

Only one transaction is allowed here. LC 122 allows any number of transactions, and there you add up every rising stretch; here you can't.

The three questions:

• Greedy choice: if I sell today, buy on the cheapest day up to and including today.
• Why it's safe: stays ahead. min_price is the minimum of all prices so far; buying on any earlier day costs at least that much, so no plan that sells today can beat today's price - min_price.
• Brute-force check: try every i < j and take the maximum prices[j] - prices[i], O(n²).

So each day does two things: update min_price with today's price, then update best with today's selling profit. Updating first means "buy and sell today" is allowed, which earns 0 and never changes the answer.

def max_profit(prices):
    min_price = float("inf")       # positive infinity: the first price is smaller and replaces it
    best = 0                       # not trading earns 0
    for p in prices:
        min_price = min(min_price, p)     # lowest price up to today
        best = max(best, p - min_price)   # best profit if we sell today
    return best


assert max_profit([7, 1, 5, 3, 6, 4]) == 5   # examples from the statement
assert max_profit([7, 6, 4]) == 0
assert max_profit([4, 2, 5, 1, 3]) == 3
assert max_profit([7, 6, 4, 3, 1]) == 0
assert max_profit([5]) == 0
assert max_profit([]) == 0

O(n) time, O(1) extra space.

What if you buy at the global minimum and sell at the highest price after it? In [4, 2, 5, 1, 3] the global minimum is 1 on day 4, and the best price after it is 3, a profit of 2. The real answer buys at 2 on day 2 and sells at 5 on day 3, a profit of 3. min_price may only contain today and earlier days, which is why it has to be updated during the scan instead of computed up front.

One more of the same: Jump Game (LC 55).

The input is a nonempty array nums, where nums[i] is the maximum number of cells you may jump right from index i: any distance from 0 to nums[i] is allowed, not just the full one. Starting at index 0, return whether you can reach the last index.

For example, [2, 3, 1, 1, 4] → True: jump 1 to index 1, then 3 to index 4. [3, 2, 1, 0, 4] → False: however you jump, the farthest you get is index 3, and nums[3] = 0 can't move you. [0] → True: you start on the goal.

Think first: The previous problem kept one number while scanning, "the lowest price so far". When this scan reaches index i, what single number is enough? Can the reachable indices have a gap (reach 5 but not 3)?

def can_jump(nums):
    farthest = 0                     # farthest index reachable using nums[0..i]
    for i, step in enumerate(nums):  # enumerate: index i and value nums[i] together
        if i > farthest:             # can't even reach i, so nothing after it either
            return False
        farthest = max(farthest, i + step)
    return True


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

One step further: the fewest jumps (LC 45)

Jumps work as before: nums[i] is the maximum distance you may jump right from index i. This time the last index is guaranteed reachable; return the fewest jumps needed.

For example, [2, 3, 1, 1, 4] → 2: 0 → 1 → 4, jumping 1 cell and then 3. With a single element (such as [0]) the answer is 0: you're already on the goal.

Note that always jumping the full distance is not optimal. In [2, 3, 1, 1, 4], jumping the full 2 cells to index 2 leaves only 1-cell jumps after it, 3 jumps in total.

Think first: Treat "indices reachable in 1 jump", "indices reachable in 2 jumps", and so on as layers. Layer 0 is just index 0. Which indices make up layer 1? How do you get layer 2's right end from layer 1? At what point in the scan must you add a jump?

def jump(nums):
    jumps = cur_end = farthest = 0   # chained assignment: all three start at 0
    for i in range(len(nums) - 1):   # skip the last cell: standing on the goal needs no jump
        farthest = max(farthest, i + nums[i])
        if i == cur_end:             # current layer done, jump into the next one
            jumps += 1
            cur_end = farthest
    return jumps


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

Step 1 recap

• What it solves: one scan that maintains a single "best so far" value answers the whole problem, with no looking back.
• The key line: min_price = min(min_price, p); in Jump Game, farthest = max(farthest, i + step).
• What the variations change: 121 tracks the lowest price; 55 tracks the farthest reachable index instead and stops when i > farthest; 45 adds cur_end to split reachable indices into layers and adds a jump each time a layer ends.
• Easiest mistake: looping to len(nums) in 45 counts an extra jump while standing on the goal. Loop to len(nums) - 1.

Step 1 problems need no sorting and no explicit DP. The next step comes from the other direction: write the DP first, then see whether it shrinks to a single variable.

Step 2: Derive a choice from the state transition

Problem: find the non-empty contiguous subarray with the largest sum (LC 53).

The input is a nonempty integer array nums. Return the largest sum of a contiguous subarray (a number, not the subarray itself). The subarray must be contiguous and contain at least one element.

For example, [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 6, from [4, -1, 2, 1]. [-2, -1] → -1: even when everything is negative you must pick something, so pick the largest, -1. Returning 0 would mean picking nothing.

You can't skip negatives in the middle; that would give a subsequence, not a subarray.

Write the DP first. Define dp[i] as the largest sum of a subarray ending at i, which must include nums[i]. Why "must end at i": a subarray is contiguous, so dp[i] can only extend a subarray ending at i−1. If dp[i-1] didn't have to end at i−1, appending nums[i] could leave a gap.

dp[i] has only two sources: extend dp[i-1], or start fresh at nums[i]. dp[i] = max(dp[i-1] + nums[i], nums[i]).

The three questions:

• Greedy choice: if the running sum before you is negative, drop it and start over at the current element. dp[i-1] + x < x is the same as dp[i-1] < 0.
• Why it's safe: this is just the DP transition, so correctness comes from the DP. The greedy part is noticing that dp[i] depends only on dp[i-1], so the whole table collapses into one variable cur.
• Brute-force check: sum every (i, j) pair.

The answer is the maximum over all dp[i], not the last one, so a separate best tracks the global maximum.

def max_sub_array(nums):
    best = cur = nums[0]             # cur is dp[i]: best sum of a subarray ending here
    for x in nums[1:]:               # slice nums[1:]: index 1 to the end (makes a copy)
        cur = max(cur + x, x)        # a negative prefix gets dropped; restart at x
        best = max(best, cur)        # the answer is the max over all dp[i]
    return best


assert max_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert max_sub_array([-2, -1]) == -1   # example from the statement
assert max_sub_array([5, 4, -1, 7, 8]) == 23
assert max_sub_array([-3, -1, -2]) == -1
assert max_sub_array([5]) == 5

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

O(n) time. nums[1:] copies the array, so strictly it uses O(n) extra space; for i in range(1, len(nums)) makes it O(1).

What if best starts at 0? The all-negative [-3, -1, -2] returns 0, which means choosing the empty subarray, and the problem doesn't allow that. Both best and cur start at nums[0].

One more of the same: Gas Station (LC 134).

A circular route has n gas stations. At station i you can take gas[i] liters, and driving from station i to the next one (the one after the last station is station 0) costs cost[i] liters. The tank has no limit and starts empty; at each station you refuel first, then drive on. Return the index (from 0) of the station you can start at and drive one full loop back to, or -1 if there is none. When a solution exists it is unique.

For example, gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2] → 3: starting at station 3, the fuel left after each leg is 3, 6, 4, 2, 0, never negative. gas = [2, 3, 4], cost = [3, 4, 3] → -1: total gas 9 is less than total cost 10.

Enough total fuel only means a solution may exist; it doesn't make every start valid. In the first example total gas 15 equals total cost 15, yet only station 3 works.

Think first: Brute force simulates a loop from every start, O(n²). Suppose you start at start and the tank goes negative for the first time after the leg from station i. Can some station k between start and i be the start? Think about whether the tank is positive, negative or zero when you drive from start to k.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1                    # not enough fuel in total, no start works
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                 # no station in start..i can be the start
            start, tank = i + 1, 0   # simultaneous assignment: 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
assert can_complete_circuit([5], [4]) == 0

Variation: maximum sum circular subarray (LC 918)

The input is a nonempty integer array, treated as a ring whose end connects back to its start. A subarray may wrap from the end back to the start, but each position is used at most once, so no going around twice. Return the largest sum of a nonempty subarray.

For example, [5, -3, 5] → 10: take the last 5 and wrap around to the first 5. [-3, -2, -3] → -2: everything is negative, so take just the -2.

Think first: The best segment either avoids the seam where the end joins the start, or crosses it. If it avoids the seam, it's plain LC 53. If it crosses the seam, what shape is the part that is not chosen? How is its sum related to the chosen segment's sum?

def max_subarray_circular(nums):
    best_max = cur_max = best_min = cur_min = nums[0]
    for x in nums[1:]:
        cur_max = max(cur_max + x, x)
        best_max = max(best_max, cur_max)
        cur_min = min(cur_min + x, x)   # same DP, tracking the smallest segment
        best_min = min(best_min, cur_min)
    if best_max < 0:                    # all negative: the wrap case is the empty array
        return best_max
    return max(best_max, sum(nums) - best_min)   # no wrap vs wrap


assert max_subarray_circular([5, -3, 5]) == 10
assert max_subarray_circular([1, -2, 3, -2]) == 3
assert max_subarray_circular([-3, -2, -3]) == -2
assert max_subarray_circular([3]) == 3

Step 2 recap

• What it solves: write the "ending at i" DP, notice dp[i] depends only on dp[i-1], and collapse the table into one variable; the transition itself is the greedy choice.
• The key line: cur = max(cur + x, x): drop the running sum when it's negative.
• What the variations change: 134 applies "drop a negative prefix" to the fuel tank, jumping the start to i + 1 on running dry, and uses the total to cover the wrap back; 918 turns the wrapping case into "total minus the smallest segment", found with the same DP using min instead of max.
• Easiest mistake: starting best at 0. All-negative input then returns the empty subarray's 0; start from nums[0], and add the all-negative check in 918.

Advanced: Longest Increasing Subsequence in O(n log n) (LC 300)

The input is an integer array. Return the length of the longest strictly increasing subsequence. A subsequence may skip elements but can't reorder them.

For example, [10, 9, 2, 5, 3, 7, 101, 18] → 4, one of them being [2, 3, 7, 101]. [2, 2] → 1: strictly increasing, so two equal numbers can't follow each other.

This is another way of replacing a DP with a greedy. The standard DP sets dp[i] to the length of the longest increasing subsequence ending at i and looks back at every j, O(n²). It's correct, but it examines every subproblem.

Record something different: tails[k] is the smallest ending value among increasing subsequences of length k + 1. The greedy choice: among subsequences of the same length, a smaller ending is better, because more numbers can extend it later (stays ahead). For each new number x:

• If x is larger than every value in tails, the longest subsequence grows by one.
• Otherwise find the first tails[k] that is >= x and replace it with x.

Why exactly entry k: tails[k-1] < x, so x can extend that length-k subsequence into one of length k + 1 ending at x, and the old ending tails[k] >= x is no better. A later entry tails[k+1] can't change: a length-(k + 2) subsequence ending at x would need a length-(k + 1) one ending below x, but even the smallest such ending, tails[k], is >= x.

tails stays strictly increasing, so "the first >= x" is a binary search (the first-occurrence search from Step 2 of the binary search article). Python's bisect_left(a, x) does exactly that: in a sorted list a, it returns the first position whose value is >= x, or len(a) when everything is smaller. bisect_right would be wrong: it returns the first position > x, so [7, 7, 7] would extend three times and return 3, while strictly increasing forbids equal neighbors.

from bisect import bisect_left


def length_of_lis(nums):
    tails = []                       # tails[k]: smallest ending of an increasing run of length k+1
    for x in nums:
        k = bisect_left(tails, x)    # first position with tails[k] >= x; len(tails) if none
        if k == len(tails):
            tails.append(x)          # larger than every ending, extend
        else:
            tails[k] = x             # same length, now with a smaller ending
    return len(tails)


assert length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]) == 4
assert length_of_lis([2, 2]) == 1    # example from the statement
assert length_of_lis([0, 1, 0, 3, 2, 3]) == 4
assert length_of_lis([7, 7, 7]) == 1
assert length_of_lis([]) == 0

nums = [10, 9, 2, 5, 3, 7, 101, 18]:

One binary search per number, O(n log n). tails isn't necessarily a real subsequence: [3, 4, 1] ends with tails = [1, 4], but 1 comes after 4. Its length is the answer.

So far we've scanned in the order the input arrives. For intervals that order means nothing, so you first impose an order yourself, which is Step 3.

Step 3: Sort, Then Compare With the Last One

Problem : LC 435 , remove the fewest intervals so the rest are pairwise non-overlapping. (Pro lesson)

Variation: merge intervals (LC 56)

The input is a list of intervals, not sorted. Merge every group of overlapping intervals and return the merged list. (Pro lesson)

Step 3 recap

What it solves : sort the intervals first; afterwards each interval only needs one comparison with "the last one kept" or "the last merged o… (Pro lesson)

Step 4: A Changing Candidate Set, Use a Heap

Problem : given meetings as (start, end) , find the fewest meeting rooms needed ( LC 253 ). (Pro lesson)

Step 4 recap

What it solves : each step takes the minimum or maximum of a changing candidate set, and a heap makes each of those O(log n). (Pro lesson)

Step 5: Constraints From Both Sides, Scan Twice or Track a Range

Problem : children stand in a row with ratings; each gets at least one candy, and a child rated higher than a neighbor gets more than that n… (Pro lesson)

Step 5 recap

What it solves : when each position is constrained from both sides, handle each direction separately, or skip choosing altogether and track… (Pro lesson)

All Five Steps Together

Step Greedy choice Why it's safe Preparation before the scan Representative problems Step 1 Maintain one best-so-far value (lowest price, fa… (Pro lesson)

One Problem, Many Disguises

LC 452 in the table is easy to confuse with 435, so here is its statement first. (Pro lesson)

Common Pitfalls

Sorting by start time for "most non-overlapping intervals". One interval that starts early and ends late blocks a whole run behind it; (Pro lesson)

Say It in the Interview

Lead with the greedy choice, give the exchange or stays-ahead reason in a sentence, then state complexity and the endpoint convention: I'll… (Pro lesson)