Greedy Algorithms: Practice Problems with Solutions

Coding Patterns - Guide to 30 Core Algorithm Patterns

Greedy Algorithms: Complete Guide with Code Examples

Welcome to the practice problems for greedy algorithms. If you need a refresher on the theory, the concept guide covers the greedy choice property and when the pattern applies. For the code, the code templates have the patterns in all 6 languages. Each problem below includes a hint, a visual walkthrough, and the full solution.

Recommended Study Order

The problems are ordered by difficulty, but the progression matters as much as the individual solutions.

Assign Cookies teaches the sort-then-scan shape with two sorted arrays and two pointers. Master this before anything with a cooldown or a formula.
Best Time to Buy and Sell Stock II drops the sorting entirely. The greedy rule is a single comparison per step.
Jump Game introduces a running state that must never go stale. It is the furthest-reach template from the template page.
Gas Station keeps a running balance and adds a restart rule. Understanding why the restart skips every index before it is the key.
Task Scheduler moves from scans to counting. The greedy rule produces a formula instead of a simulation.
Candy is the hardest. Two passes run in opposite directions, and the final answer must satisfy both constraints at once.

The order above is designed to build intuition progressively. The app schedules your reviews so you do not forget the Easy patterns while grinding Hard ones. Set up your review schedule .

Easy Problems

1. Assign Cookies

LeetCode 455 | Difficulty: Easy

Brief: Given child greed factors and cookie sizes, maximize the number of satisfied children.

Why this pattern: This is greedy matching. Give the smallest cookie that satisfies the current child. A larger cookie helps no one else more, so wasting it on an easy child is never optimal.

Key Insight: Sort both arrays first. Then the two-pointer scan works because the greedy choice is always the cheapest unused cookie that clears the child’s threshold.

Visual:

    graph LR
    A["g = [1,2,3], s = [1,1]"] --> B["cookie 1 >= greed 1: satisfied"]
    B --> C["cookie 1 < greed 2: skip cookie"]
    C --> D["no cookies left"]
    D --> E["Result: 1 child satisfied"]

Code:

var findContentChildren = function(g, s) {
    g.sort((a, b) => a - b);
    s.sort((a, b) => a - b);

    let child = 0;
    let cookie = 0;

    while (child < g.length && cookie < s.length) {
        // Give the smallest cookie that clears the greed
        // factor. A larger cookie would help no one else.
        if (s[cookie] >= g[child]) child++;
        cookie++;
    }

    return child;
};

class Solution:
    def findContentChildren(self, g: List[int], s: List[int]) -> int:
        g.sort()
        s.sort()

        child = 0
        cookie = 0

        while child < len(g) and cookie < len(s):
            # The smallest cookie that satisfies this child
            # preserves larger cookies for harder children.
            if s[cookie] >= g[child]:
                child += 1
            cookie += 1

        return child

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);

        int child = 0;
        int cookie = 0;

        while (child < g.length && cookie < s.length) {
            // Smallest cookie that clears this child's greed
            // factor, so larger cookies stay available.
            if (s[cookie] >= g[child]) child++;
            cookie++;
        }

        return child;
    }
}

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(), g.end());
        sort(s.begin(), s.end());

        int child = 0;
        int cookie = 0;

        while (child < g.size() && cookie < s.size()) {
            // Give the cheapest cookie that works. Wasting
            // a big cookie on an easy child is never optimal.
            if (s[cookie] >= g[child]) child++;
            cookie++;
        }

        return child;
    }
};

func findContentChildren(g []int, s []int) int {
    sort.Ints(g)
    sort.Ints(s)

    child := 0
    cookie := 0

    for child < len(g) && cookie < len(s) {
        // Smallest cookie that satisfies this child, so
        // larger cookies remain for harder children.
        if s[cookie] >= g[child] {
            child++
        }
        cookie++
    }

    return child
}

def find_content_children(g, s)
  g.sort!
  s.sort!

  child = 0
  cookie = 0

  while child < g.length && cookie < s.length
    # Give the smallest cookie that works. Bigger cookies
    # stay available for children with higher greed.
    child += 1 if s[cookie] >= g[child]
    cookie += 1
  end

  child
end

Both pointers advance in the same direction, and each step consumes exactly one cookie. When a cookie fails a child, that cookie can never satisfy any later child either, because the children are sorted, so it is safe to discard it. This is why the greedy matching never needs to backtrack.

Medium Problems

2. Best Time to Buy and Sell Stock II

LeetCode 122 | Difficulty: Medium

Brief: Maximize profit from buying and selling a stock, with unlimited transactions and no overlapping positions.

Why this pattern: Every price rise is a profit opportunity, and capturing every rise is never worse than skipping one. No lookahead is needed because the decision at each step depends only on the current and previous prices.

Key Insight: Sum every positive difference between consecutive prices. Each positive difference is a buy and sell pair. The greedy rule is a single comparison per step and runs in

O(N)

Visual:

    graph LR
    A["7 1 5 3 6 4"] --> B["1 to 5: +4"]
    B --> C["3 to 6: +3"]
    C --> D["total profit 7"]

Code:

var maxProfit = function(prices) {
    let profit = 0;

    for (let i = 1; i < prices.length; i++) {
        // Every rise is a profit opportunity. Buying at
        // the low and selling at the high of each rise
        // captures all of them.
        if (prices[i] > prices[i - 1]) {
            profit += prices[i] - prices[i - 1];
        }
    }

    return profit;
};

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0

        for i in range(1, len(prices)):
            # Each positive difference is a buy-sell pair.
            # Skipping a rise can never increase profit.
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]

        return profit

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            // Capture every rise. Each positive difference
            // is an independent profit opportunity.
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }

        return profit;
    }
}

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0;

        for (size_t i = 1; i < prices.size(); i++) {
            // Sum every price rise. A rise is profit no
            // matter how many transactions it takes.
            if (prices[i] > prices[i - 1]) {
                profit += prices[i] - prices[i - 1];
            }
        }

        return profit;
    }
};

func maxProfit(prices []int) int {
    profit := 0

    for i := 1; i < len(prices); i++ {
        // Add each rise to the profit. Buying at the
        // valley and selling at the peak of every rise
        // captures the full upside.
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }

    return profit
}

def max_profit(prices)
  profit = 0

  (1...prices.length).each do |i|
    # Every rise is a trade. No single trade can beat
    # taking all of them.
    if prices[i] > prices[i - 1]
      profit += prices[i] - prices[i - 1]
    end
  end

  profit
end

The solution never simulates a holding period. Buying on day i and selling on day j earns the same as buying and selling on every intermediate rise, because the price differences telescope. A flat or falling price contributes zero, which is exactly what the condition filters out. A single-element array returns 0 because the loop body never runs.

3. Jump Game

LeetCode 55 | Difficulty: Medium

Brief: Given an array of maximum jump lengths, determine whether the last index is reachable from the first.

Why this pattern: The furthest-reach scan is the greedy loop in its purest form. The state is a single number, the furthest index reachable so far, and it only grows.

Key Insight: If an index lies beyond the current reach, a gap exists and the end is unreachable. No later jump can help, because every later jump starts from a position you can never stand on.

Visual:

    graph TD
    A["nums = [2,3,1,1,4]"] --> B["i=0: reach = 2"]
    B --> C["i=1: reach = max(2, 4) = 4"]
    C --> D["i=2: reach stays 4"]
    D --> E["i=4: reach >= last index"]
    E --> F["Return true"]

Code:

var canJump = function(nums) {
    let maxReach = 0;

    for (let i = 0; i < nums.length; i++) {
        // An index beyond our reach is a gap that no
        // later jump can bridge.
        if (i > maxReach) return false;

        // Keep the larger reach. Widening it can only
        // add options, never remove them.
        maxReach = Math.max(maxReach, i + nums[i]);
    }

    return true;
};

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0

        for i in range(len(nums)):
            # Past the reach, a gap exists and the end
            # of the array is unreachable.
            if i > max_reach:
                return False

            max_reach = max(max_reach, i + nums[i])

        return True

class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;

        for (int i = 0; i < nums.length; i++) {
            // A gap means the last index is unreachable.
            if (i > maxReach) return false;

            // The reach only grows. Extending it is the
            // greedy choice and it never hurts.
            maxReach = Math.max(maxReach, i + nums[i]);
        }

        return true;
    }
}

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;

        for (size_t i = 0; i < nums.size(); i++) {
            // Beyond the reach lies a gap, and the final
            // index is unreachable from the start.
            if ((int)i > maxReach) return false;

            maxReach = max(maxReach, (int)i + nums[i]);
        }

        return true;
    }
};

func canJump(nums []int) bool {
    maxReach := 0

    for i := 0; i < len(nums); i++ {
        // An unreachable index means a gap. No future
        // jump starts before the gap, so it cannot close.
        if i > maxReach {
            return false
        }

        if i+nums[i] > maxReach {
            maxReach = i + nums[i]
        }
    }

    return true
}

def can_jump(nums)
  max_reach = 0

  nums.each_with_index do |jump, i|
    # An index beyond the reach is a gap. The last index
    # is unreachable once a gap appears.
    return false if i > max_reach

    max_reach = [max_reach, i + jump].max
  end

  true
end

The single-element case returns true because the last index is index 0, which is reachable from itself. The case [0, 2] returns false because index 1 lies beyond the reach of 0. The reach update is a max, not a sum, which is the whole trick. Intermediate jumps that fall short of the current reach are simply dominated and skipped.

4. Gas Station

LeetCode 134 | Difficulty: Medium

Brief: Find the starting station that lets a car complete a circular route, given gas available and gas cost per station.

Why this pattern: A running balance decides the start. The greedy restart rule skips whole prefixes at once instead of trying each station as a candidate.

Key Insight: If the balance drops below zero at station k, then no station from the current start up to k can be a valid start either. The car that reaches station k is the one with the most fuel left, so a weaker start only fails earlier. This is why the restart jumps to k + 1 instead of trying the next candidate one by one.

Visual:

    graph LR
    A["net = [-2,-2,-2,3,3]"] --> B["balance drops below 0 twice"]
    B --> C["restart at index 3"]
    C --> D["balance stays positive from 3 on"]
    D --> E["total >= 0: return 3"]

Code:

var canCompleteCircuit = function(gas, cost) {
    let total = 0;
    let balance = 0;
    let start = 0;

    for (let i = 0; i < gas.length; i++) {
        const net = gas[i] - cost[i];
        total += net;
        balance += net;

        // If the balance drops below zero, every station
        // between start and i is disqualified as a start.
        if (balance < 0) {
            start = i + 1;
            balance = 0;
        }
    }

    return total >= 0 ? start : -1;
};

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        total = 0
        balance = 0
        start = 0

        for i in range(len(gas)):
            net = gas[i] - cost[i]
            total += net
            balance += net

            # A negative balance rules out every station
            # from start through i as a valid start.
            if balance < 0:
                start = i + 1
                balance = 0

        return start if total >= 0 else -1

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int total = 0;
        int balance = 0;
        int start = 0;

        for (int i = 0; i < gas.length; i++) {
            int net = gas[i] - cost[i];
            total += net;
            balance += net;

            // Below zero, no station in the current prefix
            // can be a valid start, so jump past the failure.
            if (balance < 0) {
                start = i + 1;
                balance = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
}

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int total = 0;
        int balance = 0;
        int start = 0;

        for (int i = 0; i < (int)gas.size(); i++) {
            int net = gas[i] - cost[i];
            total += net;
            balance += net;

            // A negative balance disqualifies the whole
            // prefix, so the next candidate starts at i + 1.
            if (balance < 0) {
                start = i + 1;
                balance = 0;
            }
        }

        return total >= 0 ? start : -1;
    }
};

func canCompleteCircuit(gas []int, cost []int) int {
    total := 0
    balance := 0
    start := 0

    for i := 0; i < len(gas); i++ {
        net := gas[i] - cost[i]
        total += net
        balance += net

        // When the balance goes negative, no station from
        // the current start through i can work as a start.
        if balance < 0 {
            start = i + 1
            balance = 0
        }
    }

    if total >= 0 {
        return start
    }
    return -1
}

def can_complete_circuit(gas, cost)
  total = 0
  balance = 0
  start = 0

  gas.each_index do |i|
    net = gas[i] - cost[i]
    total += net
    balance += net

    # A negative balance rules out every station in the
    # prefix as a start. Jump past the failure point.
    if balance < 0
      start = i + 1
      balance = 0
    end
  end

  total >= 0 ? start : -1
end

Two conditions must both hold. The total net gas must be non-negative, otherwise the circuit is impossible regardless of the start. And the start candidate is the index right after the last time the running balance went negative. If the balance never drops below zero, index 0 is the answer. The greedy restart is what keeps this at

O(N)

time and

O(1)

space instead of a quadratic check of every start.

5. Task Scheduler

LeetCode 621 | Difficulty: Medium

Brief: Given a task list and a cooldown n, return the minimum total time to finish all tasks, where the same task must be separated by n other units.

Why this pattern: The most frequent task dictates the pace. The greedy rule produces a count of frames instead of a simulation of the schedule.

Key Insight: The most frequent task appears maxFreq times, so it needs maxFreq - 1 full frames of n + 1 slots plus one tail frame. Tasks tied for the most frequent each occupy one slot in the tail frame. The answer is the larger of the task count and this frame total, because when the cooldown is small, the tasks themselves fill the frames completely.

Visual:

    graph TD
    A["A A A B B B, n = 2"] --> B["maxFreq = 3"]
    B --> C["frames = (3-1) * 3 = 6"]
    C --> D["two tasks tie for max: +2"]
    D --> E["max(6, 8) = 8"]

Code:

var leastInterval = function(tasks, n) {
    const freq = new Array(26).fill(0);

    for (const task of tasks) {
        freq[task.charCodeAt(0) - 65]++;
    }

    const maxFreq = Math.max(...freq);
    // Tasks tied for the most frequent each take
    // one slot in the final frame.
    const maxCount = freq.filter(f => f === maxFreq).length;

    // maxFreq - 1 full frames of n + 1 slots, plus
    // the tail frame holding the tied tasks.
    return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
};

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        freq = [0] * 26

        for task in tasks:
            freq[ord(task) - ord('A')] += 1

        max_freq = max(freq)
        # Tasks tied for the most frequent each occupy
        # one slot in the final frame.
        max_count = freq.count(max_freq)

        # max_freq - 1 full frames of n + 1 slots, plus
        # the tail frame that holds the tied tasks.
        return max(len(tasks), (max_freq - 1) * (n + 1) + max_count)

class Solution {
    public int leastInterval(char[] tasks, int n) {
        int[] freq = new int[26];

        for (char task : tasks) {
            freq[task - 'A']++;
        }

        int maxFreq = 0;
        for (int f : freq) maxFreq = Math.max(maxFreq, f);

        // Tasks tied for the most frequent each need
        // one slot in the final frame.
        int maxCount = 0;
        for (int f : freq) if (f == maxFreq) maxCount++;

        return Math.max(tasks.length, (maxFreq - 1) * (n + 1) + maxCount);
    }
}

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n) {
        vector<int> freq(26, 0);

        for (char task : tasks) {
            freq[task - 'A']++;
        }

        int maxFreq = *max_element(freq.begin(), freq.end());
        int maxCount = count(freq.begin(), freq.end(), maxFreq);

        // maxFreq - 1 full frames of n + 1 slots, plus
        // the tail frame that holds the tied tasks.
        return max((int)tasks.size(), (maxFreq - 1) * (n + 1) + maxCount);
    }
};

func leastInterval(tasks []byte, n int) int {
    freq := make([]int, 26)

    for _, task := range tasks {
        freq[task-'A']++
    }

    maxFreq := 0
    for _, f := range freq {
        if f > maxFreq {
            maxFreq = f
        }
    }

    // Tasks tied for the most frequent each occupy
    // one slot in the final frame.
    maxCount := 0
    for _, f := range freq {
        if f == maxFreq {
            maxCount++
        }
    }

    frames := (maxFreq - 1) * (n + 1) + maxCount
    if len(tasks) > frames {
        return len(tasks)
    }
    return frames
}

def least_interval(tasks, n)
  freq = Array.new(26, 0)

  tasks.each do |task|
    freq[task.ord - 'A'.ord] += 1
  end

  max_freq = freq.max
  # Tasks tied for the most frequent each take
  # one slot in the final frame.
  max_count = freq.count(max_freq)

  # max_freq - 1 full frames of n + 1 slots, plus
  # the tail frame that holds the tied tasks.
  [tasks.length, (max_freq - 1) * (n + 1) + max_count].max
end

The frequency array has a fixed size of 26, so the time is

O(N)

for the counting pass and the space is

O(1)

. The tie count is the detail people miss. With tasks A A A B B B and n = 2, a formula that ignores ties returns 7, but the schedule needs 8, because both A and B need a slot in the tail frame. When the cooldown is small, like n = 1 with many distinct tasks, the frame total falls below the task count and the task count wins.

Hard Problems

6. Candy

LeetCode 135 | Difficulty: Hard

Brief: Distribute candy so every child with a higher rating than a neighbor gets more candy than that neighbor, using the minimum total.

Why this pattern: Two-pass comparison. One pass enforces the left constraint, the second pass enforces the right constraint. The greedy rule is local: match the neighbor, nothing more.

Key Insight: Start every child with 1. The left pass raises a child when the left neighbor has a lower rating. The right pass does the same from the other side, and the max of the two values keeps the left constraint intact.

Visual:

    graph LR
    A["ratings = [1,0,2]"] --> B["left pass: [1,1,2]"]
    B --> C["right pass: [2,1,2]"]
    C --> D["total = 5"]

Code:

var candy = function(ratings) {
    const n = ratings.length;
    const candies = new Array(n).fill(1);

    // Left pass: a child rated higher than the left
    // neighbor gets more candy than that neighbor.
    for (let i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) {
            candies[i] = candies[i - 1] + 1;
        }
    }

    // Right pass: same rule from the right. The max
    // keeps the left-pass values intact.
    for (let i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    return candies.reduce((a, b) => a + b, 0);
};

class Solution:
    def candy(self, ratings: List[int]) -> int:
        n = len(ratings)
        candies = [1] * n

        # Left pass: a higher-rated child needs more candy
        # than the child on the left when that child is
        # rated lower.
        for i in range(1, n):
            if ratings[i] > ratings[i - 1]:
                candies[i] = candies[i - 1] + 1

        # Right pass: same rule from the right. The max
        # keeps the left-pass constraint satisfied.
        for i in range(n - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candies[i] = max(candies[i], candies[i + 1] + 1)

        return sum(candies)

class Solution {
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candies = new int[n];
        Arrays.fill(candies, 1);

        // Left pass: raise a child rated higher than the
        // child on the left.
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Right pass: same rule from the right. The max
        // keeps the left-pass values intact.
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
        }

        int total = 0;
        for (int c : candies) total += c;

        return total;
    }
}

class Solution {
public:
    int candy(vector<int>& ratings) {
        int n = ratings.size();
        vector<int> candies(n, 1);

        // Left pass: a child rated higher than the left
        // neighbor gets more candy than that neighbor.
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }

        // Right pass: same rule from the right. The max
        // keeps the left-pass constraint satisfied.
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = max(candies[i], candies[i + 1] + 1);
            }
        }

        int total = 0;
        for (int c : candies) total += c;

        return total;
    }
};

func candy(ratings []int) int {
    n := len(ratings)
    candies := make([]int, n)

    for i := range candies {
        candies[i] = 1
    }

    // Left pass: a child rated higher than the left
    // neighbor needs more candy than that neighbor.
    for i := 1; i < n; i++ {
        if ratings[i] > ratings[i-1] {
            candies[i] = candies[i-1] + 1
        }
    }

    // Right pass: same rule from the right. The max
    // keeps the left-pass constraint intact.
    for i := n - 2; i >= 0; i-- {
        if ratings[i] > ratings[i+1] && candies[i+1]+1 > candies[i] {
            candies[i] = candies[i+1] + 1
        }
    }

    total := 0
    for _, c := range candies {
        total += c
    }

    return total
}

def candy(ratings)
  n = ratings.length
  candies = Array.new(n, 1)

  # Left pass: a higher-rated child needs more candy
  # than the child on the left.
  (1...n).each do |i|
    candies[i] = candies[i - 1] + 1 if ratings[i] > ratings[i - 1]
  end

  # Right pass: same rule from the right. The max keeps
  # the left-pass constraint satisfied.
  (n - 2).downto(0).each do |i|
    if ratings[i] > ratings[i + 1]
      candies[i] = [candies[i], candies[i + 1] + 1].max
    end
  end

  candies.sum
end

The two passes each run in

O(N)

time, and the candy array costs

O(N)

space. The max in the right pass is the detail that makes this correct. A child can be raised by the left pass and then need to be raised again by the right pass, and the max preserves whichever constraint is tighter. Flat runs of equal ratings stay at 1, because neither pass fires on an equal pair. The single-child case returns 1.

Hard problems are where patterns separate candidates who pass from candidates who get offers. Track your misses and review them on a spaced schedule so you do not repeat them in the real interview.

These six problems cover the full range of greedy shapes. Assign Cookies is the sort-then-scan. Best Time to Buy and Sell Stock II and Jump Game are pure scans with one state variable. Gas Station adds the restart rule. Task Scheduler turns the greedy rule into a formula. Candy layers two directional passes on top of each other. By the end, you should be able to name the greedy choice for a new problem, test it against a counterexample, and reach for the right template.

Done with these problems? The app has more, plus a spaced repetition system that brings problems back right before you would forget them. Continue your prep .