Greedy Pattern: Template + 346 LeetCode Problems

What the greedy pattern is

A greedy algorithm commits to the best-looking option at each step and never reconsiders, which makes it the fastest thing that can possibly work and also the easiest thing to get silently wrong. The hard part is never the code — it is three lines — but the justification, and the tool for that is the exchange argument: assume an optimal solution differs from the greedy one, look at the first place they diverge, and show that swapping in the greedy choice leaves the solution no worse. If that swap holds, greedy is correct; if it does not, the problem is dynamic programming wearing a disguise. Choosing what to be greedy about is usually a sorting decision, and the sort key is where the insight lives: interval scheduling works when you sort by earliest finishing time, because finishing early leaves the maximum room for everything after, and it quietly fails if you sort by start time or by duration instead.

When to use it

• —A local choice can be shown, by an exchange argument, never to rule out an optimal completion.
• —Sorting the input by one well-chosen key makes the right choice obvious at every step.
• —The problem is interval scheduling, jump reachability, or an assignment with a clear ordering.
• —A dynamic programming solution exists but its state collapses to a single running best.

The greedy template in Python

The shape, not a solution to any one problem. Adapt the condition and the summary being maintained; the skeleton stays the same across the 346 problems listed below.

def max_non_overlapping(intervals):
    intervals.sort(key=lambda pair: pair[1])   # earliest finishing time first
    last_end = float("-inf")
    kept = 0

    for start, finish in intervals:
        if start >= last_end:      # taking it never blocks a better option later
            kept += 1
            last_end = finish

    return kept

Complexity characteristics

Time

O(n log n), dominated by the sort

Auxiliary space

O(1) to O(n)

The greedy pass itself is a single linear scan; the sort that makes the greedy choice correct is what sets the complexity. When no sort is needed — a running maximum, a reachability check — the whole solution is O(n). The space is the sort's, which in Python means O(n) for Timsort's temporary buffer rather than the O(1) an in-place quicksort would suggest.

All 346 greedy LeetCode problems

Every problem in the library the greedy pattern applies to, grouped by LeetCode's own difficulty rating. 308 of the 346 carry a complete Python solution with a worked example and complexity analysis; the rest are listed for completeness, with the LeetCode Premium ones marked.

Related patterns

Problems sit in more than one pattern more often than not, and the overlap is where the interesting follow-up questions live.

Greedy pattern FAQ

More ways in: all 22 patterns, the curated study lists, or the full problem list.