LeetPrep

Greedy Algorithms in Python: When Taking the Best Now Works

By Published 6 min read

Make change for 6 using coins of 1, 3 and 4. Taking the biggest coin each time gives 4 + 1 + 1, which is three coins. The best answer is 3 + 3, which is two. That single example is the whole difficulty of greedy algorithms: the strategy is always tempting, usually fast, and sometimes quietly wrong. Real skill is not writing the loop. It is knowing, before you commit, whether the loop can be trusted.

This guide starts with that failure, then builds a way to judge a greedy idea, and applies it to Jump Game, Jump Game II, Gas Station and Assign Cookies. Every snippet was run, and Jump Game and Gas Station were also checked against brute-force solvers on 4,000 random inputs each.

First, watch greedy fail

def greedy_coins(coins, amt):
    cnt = 0
    for c in sorted(coins, reverse=True):
        k, amt = divmod(amt, c)
        cnt += k
    return cnt if amt == 0 else -1

greedy_coins([1, 3, 4], 6)         # -> 3   (4 + 1 + 1)
# the true minimum from dynamic programming is 2   (3 + 3)

greedy_coins([1, 5, 10, 25], 63)   # -> 6   (25 + 25 + 10 + 1 + 1 + 1), also optimal

The same code is right for the coins you carry and wrong for the set 1, 3, 4. Nothing in the code changed, only the structure of the input did. When a problem can be solved both ways, the coin problem belongs to dynamic programming, which tries every option instead of betting on one.

When is a greedy choice safe?

Two properties make it safe, and you should be able to say both out loud:

  1. Greedy choice property. Some optimal solution contains your locally best pick.
  2. Optimal substructure. After making the pick, what remains is a smaller problem of the same kind.

The usual way to prove the first is an exchange argument: take any optimal solution that does not use your pick, swap your pick in, and show the result is no worse. For the earliest-finishing interval, that swap is easy to see. Replacing whatever the optimal schedule runs first with the interval that ends earliest cannot create a new clash, because it frees up at least as much time. That is exactly why Non-overlapping Intervals sorts by end.

Practical rule: if you cannot explain in two sentences why swapping your pick into any optimal answer does no harm, hunt for a counterexample on tiny inputs before you code.

Jump Game: track the furthest reach

Each nums[i] is the maximum jump length from index i. Can you reach the last index? The greedy insight is that you never need to know how you get anywhere, only the furthest index reachable so far. If you ever stand on an index beyond that, you are stuck.

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

can_jump([2, 3, 1, 1, 4])   # -> True
can_jump([3, 2, 1, 0, 4])   # -> False

In the second input every path ends on the 0 at index 3, because every route is capped at far = 3. Against a straightforward dynamic-programming reachability check, this version agreed on all 4,000 random arrays.

Jump Game II: count the windows

Now the target is the minimum number of jumps. Think in layers, like BFS. The current jump can land anywhere up to cur_end. While scanning that layer, remember the furthest index any of its cells can reach. When the scan hits cur_end, you must have taken one more jump, and the next layer extends to that furthest point.

def jump(nums):
    jumps = cur_end = far = 0
    for i in range(len(nums) - 1):
        far = max(far, i + nums[i])
        if i == cur_end:
            jumps += 1
            cur_end = far
    return jumps

jump([2, 3, 1, 1, 4])   # -> 2
jump([2, 3, 0, 1, 4])   # -> 2

The loop stops one short of the end on purpose: once you stand on the last index you do not need another jump. This version assumes the end is reachable, as the problem guarantees.

Gas Station: one pass, one insight

Stations sit on a circle. gas[i] is the fuel you collect at station i and cost[i] is the fuel to reach the next one. Find the starting station that completes the loop, or -1.

Two facts give a linear solution. First, if total gas is less than total cost, no start works. Second, if you start at s and your tank first goes negative at station i, then no station between s and i can be a valid start either, because each of them would reach i with even less fuel than you had. So the next candidate is i + 1.

def can_complete_circuit(gas, cost):
    if sum(gas) < sum(cost):
        return -1
    tank = start = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1
            tank = 0
    return start

can_complete_circuit([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])   # -> 3
can_complete_circuit([2, 3, 4], [3, 4, 3])               # -> -1

Trace the first example. The per-station gain is −2, −2, −2, +3, +3. The tank dips negative at stations 0, 1 and 2, pushing the candidate start to 1, 2 and then 3. From station 3 the tank only grows, so the answer is 3. A brute-force simulation from every start agreed with this code on 4,000 random circuits.

Assign Cookies: sort both sides

Children have a greed factor, cookies have a size, and each child gets at most one cookie. Maximise the number of satisfied children. Sort both lists. Walk through cookies from smallest to largest and give each to the least greedy child still waiting, if it is big enough. A cookie that is too small for the least greedy child is too small for everyone, so discarding it loses nothing.

def find_content_children(g, s):
    g.sort()
    s.sort()
    i = 0
    for cookie in s:
        if i < len(g) and cookie >= g[i]:
            i += 1
    return i

find_content_children([1, 2, 3], [1, 1])   # -> 1
find_content_children([1, 2], [1, 2, 3])   # -> 2

A checklist before you trust a greedy idea

  • Can you phrase the pick as “always take the X”? If there is no clean X (largest, earliest, cheapest, furthest), greedy is probably the wrong tool.
  • Does sorting reveal the order? Most greedy solutions are a sort plus one pass, so the sort key is the real idea.
  • Have you tried a counterexample with 3 or 4 elements? The coin case failed at size three.
  • Does a choice ever need to be undone? If yes, think dynamic programming or backtracking, as in the backtracking guide.
  • Is a heap hiding in the loop? Many “pick the best available” problems, such as task schedulers, use a priority queue. See heapq patterns.

Complexity and where to go next

Jump Game, Jump Game II and Gas Station are O(n) time and O(1) space. Assign Cookies is O(n log n) because of the sort. Greedy solutions tend to be short, which is what makes them risky in an interview: the interviewer will ask why it works, and “it passed the examples” is not an answer. Practise the explanation as much as the code. The same idea in graph form is Dijkstra’s algorithm, a greedy method that is only valid when weights are non-negative. To place greedy in a full schedule, see the 30-day study plan.

Keep learning