Greedy algorithms

Problem

Many problems ask for the best of an exponential number of arrangements: the fewest jumps, the longest feasible tour, the fewest groups. A greedy algorithm replaces the search by one pass in which each decision is final. It works when the problem has two properties. First, the greedy-choice property: some optimal solution contains the locally best first move. Second, optimal substructure: what remains after that move is a smaller problem of the same kind. When both hold, one pass is enough.

Intuition

Imagine packing for a trip with room for one more bag, and you always add the most useful item left. That is fine until two items turn out to be useful only together. The question is never "is this choice good?" but "can taking it ever stop me from reaching the best outcome?". If you can show it cannot, the choice is safe.

There are two reliable ways to show that. In an exchange argument you take any optimal solution that does something different from the greedy one and swap its first differing step for the greedy step. If the result is still valid and no worse, then the greedy choice is part of some optimal solution, and you repeat on what remains. In a stays-ahead argument you compare the greedy partial solution with any other after each step and show that greedy is never behind on the quantity that matters, such as farthest reach. Both are induction: a statement about the first step, then about the rest.

A greedy idea you cannot prove is only a guess. A good habit is to try to break it on a tiny input, three to five elements, before writing any code. Many wrong greedy ideas die on the first small counterexample.

Top row: the jump lengths. Middle row: the farthest reach so far. Amber bars: the indices first reachable with 0, 1, 2 and 3 jumps, which is the breadth-first levels that Jump Game II walks. The diagram scrolls sideways on a narrow screen.

Mechanics

Jump Game: farthest reach

Scan left to right with reach, the farthest index known to be reachable. At index i, if i > reach you cannot even stand here, so the end is unreachable. Otherwise update reach = max(reach, i + nums[i]). The end is reachable exactly when the scan never gets stuck. The proof is a stays-ahead argument: the set of reachable indices is always an unbroken run from 0 to reach, because any index below the reach can be stepped onto by shortening a jump, so one number describes the whole set.

Jump Game II: levels

To count the fewest jumps, treat each jump as one level of a breadth-first search. Level 0 is index 0. Level k+1 is every index past level k's end and up to the farthest reach of anything in level k. You never need a queue: keep the current level's end, the farthest reach seen, and a counter that increments when the scan reaches the end of the level. This is greedy because you commit to the whole range, not a particular jump, and widening it is always at least as good as any narrower choice.

Gas Station: restart after a failure

Stations on a loop give gas and need fuel to reach the next one. Keep a tank starting at some station. If the tank goes negative on the way to station j, then no station between the start and j can be a better start either: each of them would arrive at j with at most as much fuel as the failed start did, since the failed start had a non-negative tank on arriving at each of them. So restart at j + 1. If the total gas is at least the total cost, the last restart point works; otherwise nothing does. That one pass replaces trying every start, which is quadratic.

Each bar is the tank after that station when the journey began at the last restart. Amber bars are the failures that move the candidate start to the next station. Here the surplus is 0, so a start exists, and it is station 2.

Hand of Straights: start from the smallest

Split a hand of cards into groups of consecutive values of a fixed size. The smallest remaining card cannot join a group as anything but its first card, since every group it could be in needs a smaller card that is already gone. So it must start a group, which makes the choice forced, and the only question is whether the next values exist. Count the cards, walk the values in ascending order and, for each unused copy, consume the run of next values. If any is missing, the answer is no. The forced-choice argument is the simplest kind of exchange proof: there is nothing to exchange.

When greedy is wrong

With coins 1, 3 and 4 and a target of 6, taking the biggest coin first gives 4+1+1 (three coins), but 3+3 uses two. Selecting the shortest interval first, instead of the earliest-ending one, can also block two longer, compatible intervals. These are the cases where the local choice destroys something later; the DP pages handle them by trying every option.

Worked example

Jump Game. With jumps 2, 3, 1, 1, 4, 2, 1, 1 the farthest reach after each index is 2, 4, 4, 4, 8, 8, 8, 8, so the end (index 7) is reachable. With 3, 2, 1, 0, 4, 1 the reach after index 3 is 3, the scan arrives at index 4 beyond it, and the end is not reachable.

Jump Game II. On the first row the index ranges first reached with 0, 1, 2 and 3 jumps are 0..0, 1..2, 3..4, 5..7, so the fewest jumps is 3.

Gas Station. Gas 3, 1, 2, 5, 4, 1, cost 4, 2, 2, 3, 3, 2. The running tank is -1, -1, 0, 2, 3, 2 with restarts after each negative value. The total surplus is 0, which is not negative, so the journey is possible, and the starting station is 2.

Hand of Straights. The hand 1, 2, 3, 3, 4, 4, 5, 5, 6 with groups of 3 splits into 1, 2, 3; 3, 4, 5; 4, 5, 6, found by always opening at the smallest remaining card.

Implementation

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


def min_jumps(nums):
    jumps = end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == end:
            jumps += 1
            end = farthest
    return jumps


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

Variations and edge cases

from collections import Counter


def is_n_straight_hand(hand, size):
    if len(hand) % size:
        return False
    counts = Counter(hand)
    for card in sorted(counts):
        need = counts[card]
        if need:
            for value in range(card, card + size):
                if counts[value] < need:
                    return False
                counts[value] -= need
    return True


def max_non_overlapping(intervals):
    intervals.sort(key=lambda pair: pair[1])
    kept, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            kept += 1
            last_end = end
    return kept

• Unreachable end in Jump Game II. The loop above assumes the end is reachable. If it might not be, check farthest <= i and return early.
• Single element. One index needs zero jumps and is trivially reachable; the loops handle this because the range is empty.
• Counting whole runs. In the straights version, subtracting need from every value of the run handles duplicates in one step; subtracting one at a time works too but repeats work.
• Sorting keys and ties. Sorting by end time needs a decision for equal ends; either order is fine for counting, but check this when you also output the chosen items.
• Strict versus non-strict. Whether an interval starting exactly where another ends overlaps changes >= to >. Read the statement.
• Gas total check. Without the total test, the restart point can look valid when the remaining stations were never checked against the earlier surplus.

Complexity and tradeoffs

• Time: usually O(n) for a single pass, or O(n log n) when a sort comes first, as in interval and scheduling problems.
• Space: O(1) for the scans above, O(n) for the counters.
• Baseline. Trying every start or every sequence of jumps is quadratic to exponential, so greedy turns minutes into milliseconds on large inputs.
• Versus DP. If a counterexample exists, use DP. Jump Game can be written as DP over "can I reach index i", which is O(n²) and always right; the greedy version is the optimisation, justified by the reach being an unbroken run.
• When it fails. If a local choice can block a better global combination (weighted intervals, coin systems like 1, 3, 4), greedy gives a wrong answer silently. Test on small cases against brute force.

Problems

This page has many problems because greedy is a way of arguing rather than one trick. Start with Jump Game and Gas Station, where the proof fits in a paragraph, then try the scheduling and counting problems and ask for each: what is the exchange or stays-ahead argument?

Easy

• 860. Lemonade Change NeetCode 250
  Give change using a ten before fives whenever you can, because fives are more flexible for later customers.

Medium

• 45. Jump Game II NeetCode 150 NeetCode 250
  Treat the indices reachable with each number of jumps as a BFS level, and each level's farthest reach becomes the next boundary.
• 55. Jump Game Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Track the farthest index reachable so far; you get stuck only if you arrive at an index beyond that reach.
• 122. Best Time to Buy and Sell Stock II NeetCode 250
  With unlimited transactions, collecting every day-over-day increase is exactly the maximum profit.
• 134. Gas Station Grind 169 NeetCode 150 NeetCode 250
  If the total gas covers the total cost an answer exists, and it is the station just after the point where the running tank last went negative.
• 179. Largest Number Grind 169
  Order the numbers by which concatenation is larger, a then b against b then a, and handle an all-zero result.
• 435. Non-overlapping Intervals Blind 75 Grind 169 NeetCode 150 NeetCode 250
  Sort by end time and keep each interval that starts at or after the last kept end; the answer is how many intervals were dropped.
• 621. Task Scheduler Grind 169 NeetCode 150 NeetCode 250
  The most frequent task fixes the frame length, (maximum count - 1) times (n + 1) plus ties, unless the tasks alone take longer.
• 649. Dota2 Senate NeetCode 250
  Queue each party's senators by index; the earlier senator bans the other and goes back in the queue with index plus n.
• 678. Valid Parenthesis String NeetCode 150 NeetCode 250
  Track the lowest and highest number of open brackets possible, with a star widening the range; fail if the high count drops below zero, and accept only if the low count can end at zero.
• 763. Partition Labels NeetCode 150 NeetCode 250
  Record each letter's last index, extend the current part to the farthest last index seen, and cut when the scan reaches it.
• 767. Reorganize String NeetCode 250
  Always place the most frequent remaining letter that differs from the last one placed, or fill even indices first by frequency.
• 846. Hand of Straights NeetCode 150 NeetCode 250
  Always start a group at the smallest remaining card and consume the next consecutive values, failing if any is missing.
• 1405. Longest Happy String NeetCode 250
  Use the most plentiful letter unless it would make three in a row, in which case use the next most plentiful once.
• 1899. Merge Triplets to Form Target Triplet NeetCode 150 NeetCode 250
  Discard every triplet that exceeds the target in any position; the target is reachable exactly when the rest can match each position.

Hard

• 135. Candy NeetCode 250
  One left-to-right pass satisfies left neighbours and one right-to-left pass satisfies right neighbours, so take the larger requirement at each child.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

• 121. Best Time to Buy and Sell Stock Easy
• 11. Container With Most Water Medium
• 853. Car Fleet Medium
• 881. Boats to Save People Medium
• 1011. Capacity To Ship Packages Within D Days Medium
• 410. Split Array Largest Sum Hard
• 502. IPO Hard

Connections

The sort-then-sweep greedy is the idea behind interval problems, the heap-based greedy shows up in scheduling with priorities, and the "restart after a failure" idea resembles the running-sum reset that gives Kadane's algorithm. Dijkstra's algorithm is a greedy algorithm too, with the stays-ahead proof that finalised distances are exact.

Check yourself

References

• Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms, chapter 15, greedy algorithms and the greedy-choice property.
• Kleinberg and Tardos, Algorithm Design, chapter 4, which introduces the exchange argument and the stays-ahead argument by name.
• Skiena, S., The Algorithm Design Manual, the catalog entry on scheduling and chapter 10 on dynamic programming versus greedy.
• Sedgewick and Wayne, Algorithms, sections 4.3 (minimum spanning trees) and 4.4 (shortest paths), where Prim, Kruskal and Dijkstra are greedy algorithms with their correctness proofs.
• Edmonds, J., "Matroids and the greedy algorithm", Mathematical Programming 1, 1971, which characterises exactly when greedy is optimal.
• The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.