Autocoder

Greedy algorithm interview questions with worked solutions

Last updated 2026-11-19

A greedy algorithm makes the locally best choice at each step and never reconsiders it. It is fast and short when it works, and wrong when it does not, so the interview skill is not writing the loop but justifying the choice: why does picking this option now never hurt the final answer?

The ten problems below come with the argument that makes each greedy step safe, ordered from direct to subtle. For selection problems on ranges, see interval questions; when a greedy choice fails because of weights or overlapping sub-problems, move to dynamic programming. Pair this page with the DSA coding round guide.

Problems10, easy to hard
LanguagesPython and Java
Proof toolsExchange argument, stays ahead

How to justify a greedy choice

The standard argument is an exchange argument: take any optimal solution that does not use your greedy choice, and show you can swap in the greedy choice without making it worse. The second is a stays-ahead argument: show that after each step the greedy solution is at least as good as any other on the quantity you care about.

In an interview, test your idea on a small counterexample before coding. Coin change with coins 1, 3, 4 and amount 6 is the classic case where greedy picks 4 + 1 + 1 but 3 + 3 is better.

Typical signals

Words such as "minimum number of", "maximum number of", "earliest", "fewest" with a simple local rule are common. A greedy solution usually has an O(n log n) sort or an O(n) scan. If you cannot explain why the rule is safe, that is a reason to suspect it.

Greedy algorithm interview questions with worked solutions: questions with worked answers

  1. 1

    Assign cookies: maximise the number of children who receive a cookie at least as large as their greed.

    easy

    Sort both lists. Walk through the cookies from smallest to largest and give each cookie to the least greedy unsatisfied child if it is big enough. Using the smallest sufficient cookie for the least demanding child wastes nothing. The count of satisfied children is the answer. Time O(n log n + m log m), space O(1).. Edge cases: no cookies or no children (0), every cookie too small, more cookies than children.

    python
    def find_content_children(g, s):
        g.sort()
        s.sort()
        i = 0
        for cookie in s:
            if i < len(g) and g[i] <= cookie:
                i += 1
        return i
    java
    import java.util.*;
    
    class Solution {
        static int findContentChildren(int[] g, int[] s) {
            Arrays.sort(g);
            Arrays.sort(s);
            int i = 0;
            for (int cookie : s)
                if (i < g.length && g[i] <= cookie) i++;
            return i;
        }
    }
  2. 2

    Lemonade change: each customer pays 5, 10 or 20 for a 5-dollar drink; can you always give change?

    easy

    Track the count of 5 and 10 notes. A 10 needs one 5. A 20 needs 15 in change: prefer one 10 and one 5, because 5s are more flexible and can substitute for a 10 later, otherwise use three 5s. Preferring the 10 is the greedy step. Time O(n), space O(1).. Edge cases: first customer pays 10 or 20 (false), a 20 when only 5s remain, long runs of 5s.

    python
    def lemonade_change(bills):
        five = ten = 0
        for b in bills:
            if b == 5:
                five += 1
            elif b == 10:
                if not five:
                    return False
                five -= 1
                ten += 1
            else:
                if ten and five:
                    ten -= 1
                    five -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True
    java
    import java.util.*;
    
    class Solution {
        static boolean lemonadeChange(int[] bills) {
            int five = 0, ten = 0;
            for (int b : bills) {
                if (b == 5) five++;
                else if (b == 10) {
                    if (five == 0) return false;
                    five--;
                    ten++;
                } else {
                    if (ten > 0 && five > 0) { ten--; five--; }
                    else if (five >= 3) five -= 3;
                    else return false;
                }
            }
            return true;
        }
    }
  3. 3

    Best time to buy and sell stock with unlimited transactions.

    easy

    Any rise between consecutive days can be captured by buying the day before and selling the day after, and the sum of all rises equals the best total. So add every positive day-to-day difference. No need to find the actual buy and sell days. Time O(n), space O(1).. Edge cases: prices only falling (0), one day, flat prices.

    python
    def max_profit(prices):
        return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, len(prices)))
    java
    import java.util.*;
    
    class Solution {
        static int maxProfit(int[] p) {
            int profit = 0;
            for (int i = 1; i < p.length; i++)
                if (p[i] > p[i - 1]) profit += p[i] - p[i - 1];
            return profit;
        }
    }
  4. 4

    Jump game: can you reach the last index if each element is the maximum jump length from that position?

    medium

    Scan once, tracking the farthest index reachable so far. If the current index is beyond that, you are stuck and the answer is false. Otherwise update farthest with i + a[i]. You do not need to choose a specific jump, only to know the reachable frontier. Time O(n), space O(1).. Edge cases: a zero in the middle that can be jumped over versus one that cannot, single element (true), all zeroes except the first.

    python
    def can_jump(a):
        far = 0
        for i, x in enumerate(a):
            if i > far:
                return False
            far = max(far, i + x)
        return True
    java
    import java.util.*;
    
    class Solution {
        static boolean canJump(int[] a) {
            int far = 0;
            for (int i = 0; i < a.length; i++) {
                if (i > far) return false;
                far = Math.max(far, i + a[i]);
            }
            return true;
        }
    }
  5. 5

    Jump game II: the minimum number of jumps to reach the last index (reachable guaranteed).

    medium

    Think in layers like BFS. Track the end of the current jump range and the farthest reachable index. When you reach the end of the current range, you must jump again: increment the counter and extend the range to the farthest point. Stop before the last index. Time O(n), space O(1).. Edge cases: single element (0 jumps), every jump of length one, a big first jump.

    python
    def jump(a):
        jumps = cur_end = far = 0
        for i in range(len(a) - 1):
            far = max(far, i + a[i])
            if i == cur_end:
                jumps += 1
                cur_end = far
        return jumps
    java
    import java.util.*;
    
    class Solution {
        static int jump(int[] a) {
            int jumps = 0, curEnd = 0, far = 0;
            for (int i = 0; i < a.length - 1; i++) {
                far = Math.max(far, i + a[i]);
                if (i == curEnd) {
                    jumps++;
                    curEnd = far;
                }
            }
            return jumps;
        }
    }
  6. 6

    Gas station: find the starting station to complete a circular route, or -1.

    medium

    If total gas is less than total cost, no start works. Otherwise a solution exists and is unique. Scan with a running tank; whenever it goes negative, none of the stations from the previous start up to here can be the start (each would have reached this point with at least as little fuel), so reset the start to the next station. Time O(n), space O(1).. Edge cases: total gas below total cost (-1), a single station, a start at the last index.

    python
    def can_complete_circuit(gas, cost):
        total = tank = start = 0
        for i in range(len(gas)):
            d = gas[i] - cost[i]
            total += d
            tank += d
            if tank < 0:
                start = i + 1
                tank = 0
        return start if total >= 0 else -1
    java
    import java.util.*;
    
    class Solution {
        static int canCompleteCircuit(int[] gas, int[] cost) {
            int total = 0, tank = 0, start = 0;
            for (int i = 0; i < gas.length; i++) {
                int d = gas[i] - cost[i];
                total += d;
                tank += d;
                if (tank < 0) {
                    start = i + 1;
                    tank = 0;
                }
            }
            return total >= 0 ? start : -1;
        }
    }
  7. 7

    Task scheduler: the least time to run tasks when identical tasks need n idle slots between them.

    medium

    The most frequent task decides the frame. If it appears maxf times and k tasks tie for that frequency, the minimum length is (maxf - 1) * (n + 1) + k: maxf - 1 full blocks of n + 1 slots, plus a final row of the k tied tasks. Other tasks fill the gaps. If there are more tasks than that, no idling is needed and the answer is the task count. Time O(n) to count, space O(26).. Edge cases: n = 0 (answer is the task count), a single task type, many types with few repeats.

    python
    from collections import Counter
    
    def least_interval(tasks, n):
        cnt = Counter(tasks)
        maxf = max(cnt.values())
        k = sum(1 for v in cnt.values() if v == maxf)
        return max(len(tasks), (maxf - 1) * (n + 1) + k)
    java
    import java.util.*;
    
    class Solution {
        static int leastInterval(char[] tasks, int n) {
            int[] cnt = new int[26];
            for (char t : tasks) cnt[t - 'A']++;
            int maxf = 0;
            for (int c : cnt) maxf = Math.max(maxf, c);
            int k = 0;
            for (int c : cnt) if (c == maxf) k++;
            return Math.max(tasks.length, (maxf - 1) * (n + 1) + k);
        }
    }
  8. 8

    Queue reconstruction by height: rebuild a queue from people given as [height, number of taller-or-equal people in front].

    medium

    Sort by height descending, and for equal heights by the front-count ascending. Then insert each person at index equal to their count. Taller people are placed first, so inserting a shorter person later never changes the count of taller people in front of anyone already placed. Time O(n^2) because of list insertions, space O(n).. Edge cases: equal heights (tie-break matters), count 0 for everyone, a single person.

    python
    def reconstruct_queue(people):
        people.sort(key=lambda p: (-p[0], p[1]))
        res = []
        for p in people:
            res.insert(p[1], p)
        return res
    java
    import java.util.*;
    
    class Solution {
        static int[][] reconstructQueue(int[][] people) {
            Arrays.sort(people, (a, b) -> a[0] != b[0] ? Integer.compare(b[0], a[0]) : Integer.compare(a[1], b[1]));
            List<int[]> res = new ArrayList<>();
            for (int[] p : people) res.add(p[1], p);
            return res.toArray(new int[0][]);
        }
    }
  9. 9

    Candy: distribute the fewest candies so each child gets at least one and a higher-rated child gets more than a neighbour.

    hard

    Do two passes. Left to right, give a child one more than the left neighbour if their rating is higher. Right to left, do the same against the right neighbour, keeping the maximum of the two requirements. Each pass enforces one side of the rule without breaking the other. Time O(n), space O(n).. Edge cases: equal ratings (no extra candy needed), strictly increasing or decreasing ratings, a single child.

    python
    def candy(r):
        n = len(r)
        c = [1] * n
        for i in range(1, n):
            if r[i] > r[i - 1]:
                c[i] = c[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if r[i] > r[i + 1]:
                c[i] = max(c[i], c[i + 1] + 1)
        return sum(c)
    java
    import java.util.*;
    
    class Solution {
        static int candy(int[] r) {
            int n = r.length;
            int[] c = new int[n];
            Arrays.fill(c, 1);
            for (int i = 1; i < n; i++)
                if (r[i] > r[i - 1]) c[i] = c[i - 1] + 1;
            for (int i = n - 2; i >= 0; i--)
                if (r[i] > r[i + 1]) c[i] = Math.max(c[i], c[i + 1] + 1);
            int sum = 0;
            for (int x : c) sum += x;
            return sum;
        }
    }
  10. 10

    Minimum number of refuelling stops to reach a target, given stations with positions and fuel.

    hard

    Drive as far as possible without stopping, remembering the fuel amount of every station you pass in a max-heap. When you run out before the next point, retroactively refuel at the passed station with the most fuel and count a stop. If the heap is empty while fuel is negative, the target is unreachable. A final virtual station at the target flushes the last leg. Time O(n log n), space O(n).. Edge cases: target reachable with the starting fuel (0 stops), unreachable (-1), a station exactly at the point fuel runs out.

    python
    import heapq
    
    def min_refuel_stops(target, fuel, stations):
        heap, stops, prev = [], 0, 0
        for pos, f in stations + [[target, 0]]:
            fuel -= pos - prev
            while heap and fuel < 0:
                fuel += -heapq.heappop(heap)
                stops += 1
            if fuel < 0:
                return -1
            heapq.heappush(heap, -f)
            prev = pos
        return stops
    java
    import java.util.*;
    
    class Solution {
        static int minRefuelStops(int target, int fuel, int[][] stations) {
            PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
            int stops = 0, prev = 0;
            for (int i = 0; i <= stations.length; i++) {
                int pos = i < stations.length ? stations[i][0] : target;
                int f = i < stations.length ? stations[i][1] : 0;
                fuel -= pos - prev;
                while (!heap.isEmpty() && fuel < 0) {
                    fuel += heap.poll();
                    stops++;
                }
                if (fuel < 0) return -1;
                heap.add(f);
                prev = pos;
            }
            return stops;
        }
    }

Frequently asked questions

How do I know a greedy solution is correct?

Prove it with an exchange argument (swap the greedy choice into any optimal solution without loss) or a stays-ahead argument. Also test it on small cases against brute force.

What is a classic case where greedy fails?

Coin change with coins 1, 3, 4: for 6, greedy picks 4, 1, 1 (three coins) but 3 + 3 uses two. Such cases need dynamic programming.

Is sorting always part of a greedy solution?

Often, because sorting exposes the order in which local choices are safe. But scans such as jump game and gas station are greedy without sorting.

How is greedy different from dynamic programming?

Greedy commits to one choice per step and never revisits it. DP tries all choices and combines sub-results. Greedy is faster but applies to fewer problems.

Which interval problems are greedy?

Non-overlapping intervals and balloon arrows are classic sort-by-end greedy problems. See interval questions.

Related guides

More in DSA Interview Questions

See all in this section