Top 10 Greedy Algorithm Problems to Master for Coding Interviews

Greedy algorithm problems are the most dangerous pattern in an interview. Not because they're hard to code. Because they look like they should work, then they don't, and you have no idea why.

The failure mode is always the same. You make a locally optimal choice, assume it extends globally, write the code, submit, and then discover there was an edge case shaped exactly like your blind spot. Then you spend ten minutes debugging logic that was actually never correct. The code wasn't the problem. The assumption was.

The fix: understand the greedy choice property. For a greedy algorithm to work, your local choice has to be provably safe. The exchange argument is how you prove it. Swap your greedy choice into any optimal solution and show the result is no worse.

This list is ordered by what each problem teaches, not just difficulty. Work through them in sequence and by the end you will have ten exchange arguments internalized. That's the real pattern recognition.

Problem 1: Assign Cookies (LC 455, Easy)

What it teaches: Basic greedy matching. Satisfy the smallest greedily.

You have children with greed factors and cookies of different sizes. Assign each child at most one cookie such that the cookie's size meets their greed factor. Maximize satisfied children.

Sort both arrays. Use two pointers. For each child in order of increasing greed, assign the smallest cookie that can satisfy them.

def findContentChildren(g: list[int], s: list[int]) -> int:
    g.sort()
    s.sort()
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1
    return child

Why greedy works: If you use a large cookie on an easy-to-satisfy child, you waste it. Swapping to give the smallest sufficient cookie to each child in order produces a result that's at least as good. This is the exchange argument in its cleanest form. One sentence, obvious, provably correct.

Problem 2: Best Time to Buy and Sell Stock II (LC 122, Medium)

What it teaches: Problem transformation. Collect every profitable day.

You can complete unlimited buy-sell transactions. Maximize total profit.

The key insight is a transformation, not a procedure. Profit over any multi-day hold equals the sum of daily differences during that hold. So collecting every positive daily difference is equivalent to the optimal strategy.

def maxProfit(prices: list[int]) -> int:
    return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))

The exchange argument: any multi-day hold with a negative day inside it can be improved by excluding that day. So the optimal hold never includes a negative-diff day, which means collecting every positive diff is equivalent to any optimal strategy.

Greedy sometimes requires reframing the input before the choice becomes obvious. The brute force approach of simulating trades is fine. The one-liner is what you pull out after you explain the insight.

Problem 3: Jump Game (LC 55, Medium)

What it teaches: Track a running maximum. One variable is enough.

Can you reach the last index? Each element is your max jump length from that position.

Maintain max_reach. At each index, if you're beyond max_reach you're stuck. Otherwise update it.

def canJump(nums: list[int]) -> bool:
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
    return True

If you can reach index i, you can reach any index up to i + nums[i]. The greedy choice is always to track the farthest reachable point. No benefit to backtracking. No benefit to storing visited states. One variable.

Problem 4: Non-overlapping Intervals (LC 435, Medium)

What it teaches: Activity selection. Sort by end time, not start time.

Find the minimum number of intervals to remove to make the rest non-overlapping.

This is the classic activity selection problem. Equivalently: maximize the intervals you keep. Sort by end time. Keep an interval if its start is at or after the end of the last kept interval.

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    intervals.sort(key=lambda x: x[1])
    count = 0
    end = float('-inf')
    for start, stop in intervals:
        if start >= end:
            end = stop
        else:
            count += 1
    return count

Exchange argument: suppose an optimal solution picks interval I over the greedy choice G at some step, where I ends later than G. Swapping G in gives a solution that ends earlier, leaving more room for future intervals. The swap never loses anything.

Sort by start time instead and the whole thing collapses immediately. A lot of people learn this the wrong way and it takes one wrong-answer submission to convince them.

The merge intervals pattern is related but distinct: there you combine overlapping intervals, here you select non-overlapping ones.

Problem 5: Minimum Number of Arrows to Burst Balloons (LC 452, Medium)

What it teaches: Greedy interval coverage.

Balloons span horizontal ranges. An arrow shot at x bursts every balloon whose range includes x. Find the minimum number of arrows.

Same algorithm as problem 4 in different clothing: sort by end, shoot each arrow at the end of the current group, count how many groups you need.

def findMinArrowShots(points: list[list[int]]) -> int:
    points.sort(key=lambda x: x[1])
    arrows = 1
    arrow_pos = points[0][1]
    for start, end in points[1:]:
        if start > arrow_pos:
            arrows += 1
            arrow_pos = end
    return arrows

Once you internalize activity selection, interval variants become structurally recognizable. The signal is sort by end, greedy scan. This is the second time you've written essentially the same code. Notice that.

Wojak 4-panel: engineer skips 5-round interview process by getting an offer after one interview; hiring manager cries "you were supposed to jump through hoops"

The hiring loop when you solve every greedy problem and explain the exchange argument unprompted.

Problem 6: Jump Game II (LC 45, Medium)

What it teaches: BFS thinking inside greedy. Track current boundary and next boundary.

Minimum jumps to reach the last index.

Think in levels, like BFS. At each jump count, track the farthest you can reach from any position in the current level. When you exhaust the current level, increment jumps and advance the boundary.

def jump(nums: list[int]) -> int:
    jumps = current_end = farthest = 0
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
    return jumps

This is Jump Game's cousin with a cost dimension added. Instead of asking "can I reach", ask "what's the minimum cost to reach." That changes which invariant you maintain. The BFS framing makes it obvious why greedy works: you're processing all positions reachable in k jumps before advancing to k+1.

Problem 7: Gas Station (LC 134, Medium)

What it teaches: Circular feasibility. Reset start when cumulative total goes negative.

N gas stations in a circle. Each gives gas[i] fuel and costs cost[i] to travel to the next. Find the starting station, or return -1.

Two insights, both worth knowing:

If total gas is at least total cost, a valid solution exists and is unique.
Start from 0, track running tank. If tank goes negative, start over from the next station.

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

Why resetting works: If you can't reach station j from station i, you also can't reach j from any station between i and j. The cumulative tank was already insufficient before j arrived, meaning every intermediate start would hit the same deficit or worse. You skip the entire failed range in one step.

Most people's first instinct is to try every starting station. That's O(n²). The reset insight collapses it to O(n). The exchange argument here is a bit sneaky: you have to think about what "tank went negative at j" implies for every station between start and j.

Problem 8: Partition Labels (LC 763, Medium)

What it teaches: Two-pass structure. Precompute future information, then greedy scan.

Partition a string so each character appears in at most one part. Return the part sizes.

Pass 1: record the last index of each character. Pass 2: greedily extend the current partition's boundary as you scan. When the current index equals the boundary, close the partition.

def partitionLabels(s: str) -> list[int]:
    last = {c: i for i, c in enumerate(s)}
    result = []
    start = end = 0
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            result.append(end - start + 1)
            start = i + 1
    return result

When your greedy choice requires future information, precompute it first. The "last occurrence" precompute is a recurring structure. You'll see it in Candy, in interval problems, and in string pattern matching. Recognize it as a template.

Problem 9: Task Scheduler (LC 621, Medium)

What it teaches: Frequency math. The bottleneck resource drives the answer.

CPU tasks with cooldown n: the same task can't repeat within n intervals. Minimize total intervals including idle time.

The most frequent task controls the structure. If that task appears max_freq times, it creates (max_freq - 1) gaps of size n. All other tasks fill those gaps. If there aren't enough tasks, idle time fills the rest.

from collections import Counter

def leastInterval(tasks: list[str], n: int) -> int:
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for f in freq.values() if f == max_freq)
    return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

The formula: (max_freq - 1) * (n + 1) + max_count. If you have enough tasks to fill all idle slots, the answer is just len(tasks). This kind of greedy needs a mathematical argument, not just a procedure. A heap-based simulation also works and generalizes better, but the formula is the cleaner answer if you can derive it under pressure.

Problem 10: Candy (LC 135, Hard)

What it teaches: Bidirectional two-pass. One pass isn't enough when constraints point in both directions.

Each child gets at least one candy. A child with a higher rating than a neighbor must get more candies than that neighbor. Minimize total candies.

One left-to-right pass satisfies the left-neighbor constraint. A right-to-left pass satisfies the right-neighbor constraint. At each index, take the maximum of both passes.

def candy(ratings: list[int]) -> int:
    n = len(ratings)
    left = [1] * n
    for i in range(1, n):
        if ratings[i] > ratings[i - 1]:
            left[i] = left[i - 1] + 1
    right = [1] * n
    for i in range(n - 2, -1, -1):
        if ratings[i] > ratings[i + 1]:
            right[i] = right[i + 1] + 1
    return sum(max(l, r) for l, r in zip(left, right))

Recognizing that two independent constraints can be satisfied independently is the insight. Most people waste time looking for a single-pass solution. There isn't one. The two-pass structure from Partition Labels reappears here in harder form.

Candy is an Easy problem in disguise if you see the structure. It's an impossibility if you don't.

The Templates These 10 Problems Cover

Template	Problems
Sort + scan (matching)	Assign Cookies
Problem transformation	Stock II
Running max	Jump Game, Jump Game II
Activity selection (sort by end)	Non-overlapping Intervals, Arrows
Reset-start (circular feasibility)	Gas Station
Two-pass (precompute then scan)	Partition Labels, Candy
Frequency math	Task Scheduler

If you're stuck on a new greedy problem, start by asking which template it resembles. Then ask whether you can construct the exchange argument. If you can't, the problem might not be greedy at all. That's when DP becomes the right tool.

The Hidden Test in Every Greedy Problem

Getting the right answer on examples is table stakes. The interviewer wants to hear "the reason this works is..." followed by a sketch of why your local choice is safe globally.

Practice narrating that argument for each problem above. For the harder ones like Gas Station and Candy, be ready to explain why a simpler approach fails before presenting your solution. That dead-end acknowledgment is what moves you from a 3 to a 4 on problem-solving.

If you want to practice narrating greedy reasoning under real interview pressure, SpaceComplexity runs voice-based mock interviews where the AI probes your justification in real time, the same way a human interviewer would.

Six Rules That Transfer

Sort by end time for activity selection problems, never start time
The exchange argument is what separates "I think this is greedy" from "this is provably greedy"
Two-pass structure when a greedy choice requires future information
Reset-start in circular feasibility problems when running total goes negative
Frequency math problems have elegant formulas once you identify the bottleneck resource
If you can build a counterexample in two minutes, pivot to DP