Greedy algorithms · Commitwise

A greedy algorithm makes the choice that looks best right now, and never looks back. When it works, it’s the simplest solution there is: often a sort and one loop, O(n log n), a few lines of code. When it doesn’t, it returns a confident, plausible, wrong answer. The skill this lesson teaches is telling the two apart, and convincing an interviewer you can.

New to some of these? Open what you need, or skip ahead.

Basics:What are arrays and indexes?

An array is a row of values stored one after another: [5, 8, 2, 9]. Each position has an index, starting at 0: here 5 is at index 0 and 9 at index 3. The last index is always count - 1 (Swift) or size - 1 / length - 1 (Kotlin, Java, TypeScript).

Reading nums[2] is instant, whatever the array’s size. Reading an index that doesn’t exist (like nums[4] here) crashes with an “index out of range” error (in TypeScript it quietly gives undefined, a bug of its own), which is why loops usually go from 0 up to, but not including, the length.

Basics:What does O(n) mean?

Big-O describes how the amount of work grows with the size of the input n:

O(1): the same work whatever the size (reading array[5]).
O(log n): grows very slowly (about 20 steps for a million items).
O(n): grows in step with the input (one pass over the array).
O(n²): comparing every item with every other item, which gets slow fast.

You’ll see it next to every solution, for time and for extra space (memory). The Big-O tutorial explains it properly.

Basics:How does sorting work in each language?

Every language has a built-in sort that takes O(n log n):

Swift: nums.sort() sorts in place; nums.sorted() returns a sorted copy; sorted(by: >) sorts descending.
Kotlin: nums.sort() in place; nums.sorted() returns a copy; sortedBy { it.end } sorts by a property.
Java: Arrays.sort(nums) for arrays, list.sort(Comparator.comparingInt(Meeting::end)) for lists.
TypeScript: nums.sort((a, b) => a - b). Without the comparator, numbers are sorted as text, so 10 comes before 9.

Part Not started

The best choice right now

Paying 0.80 EUR in coins, you probably take the biggest coin that fits (50 cents), then the next biggest (20, then 10), without thinking about it. Each step makes the best choice at that moment, and with euro coins, you end up with the fewest coins. That’s a greedy algorithm: always take what looks best now, and never undo it.

It’s fast because there’s nothing to try and nothing to undo. The catch is that “best right now” isn’t always “best overall”, and the second half of this lesson is about telling which is which.

Greedy makes an irrevocable locally optimal choice at each step and reduces the problem to a smaller one of the same kind. It’s correct when the problem has the greedy-choice property (some optimal solution starts with the greedy choice) and optimal substructure (what remains after that choice is solved optimally by the same rule). In interviews, the code is usually trivial; the evaluation is whether you can state the invariant and defend it, or produce a counterexample when it fails.

Jump Game

Jump Game. nums[i] is the maximum jump length from index i. Starting at index 0, can you reach the last index? [2, 3, 1, 1, 4] → true. [3, 2, 1, 0, 4] → false (every path lands on the 0).

Trying every path is backtracking, exponential. But you don’t need the path, only how far you could possibly get. Walk left to right and keep the furthest index reachable so far:

Track the furthest reach

func canJump(_ nums: [Int]) -> Bool {
    var furthest = 0                              // furthest index reachable so far
    for i in 0..<nums.count {
        if i > furthest { return false }          // this index can't be reached
        furthest = max(furthest, i + nums[i])
    }
    return true
}

fun canJump(nums: IntArray): Boolean {
    var furthest = 0                              // furthest index reachable so far
    for (i in nums.indices) {
        if (i > furthest) return false            // this index can't be reached
        furthest = maxOf(furthest, i + nums[i])
    }
    return true
}

boolean canJump(int[] nums) {
    int furthest = 0;                             // furthest index reachable so far
    for (int i = 0; i < nums.length; i++) {
        if (i > furthest) return false;           // this index can't be reached
        furthest = Math.max(furthest, i + nums[i]);
    }
    return true;
}

function canJump(nums: number[]): boolean {
  let furthest = 0;                               // furthest index reachable so far
  for (let i = 0; i < nums.length; i++) {
    if (i > furthest) return false;               // this index can't be reached
    furthest = Math.max(furthest, i + nums[i]);
  }
  return true;
}

One number, furthest, replaces all the paths. Every index up to furthest can be reached somehow, and from each of them you might jump further. If the loop ever arrives at an index beyond furthest, there’s a gap nobody can cross. O(n) time, O(1) space.

Invariant: after processing index i, furthest is the maximum index reachable using jumps from indices 0…i. Every index ≤ furthest is reachable (reachability is contiguous: you can always jump shorter), so the first i > furthest proves the end is unreachable. Note the greedy isn’t “take the longest jump”; it’s “track the best frontier”, which is the more common shape of greedy in interviews.

Practice: trace it, then break it

[2, 3, 1, 1, 4], furthest starts at 0.
i = 0: 0 ≤ 0, furthest = max(0, 0 + 2) = 2.
i = 1: 1 ≤ 2, furthest = max(2, 1 + 3) = 4. That’s already the last index.
i = 2, 3, 4: all ≤ 4. The loop ends: true.
[3, 2, 1, 0, 4]: furthest becomes 3, 3, 3, 3 at i = 0…3 (each jump lands on index 3, the 0). At i = 4, 4 > 3: false.

Here’s a version someone wrote from memory. It returns true for [3, 2, 1, 0, 4]:

Spot the bugJump Game, almost

Tap the line with the bug.

func canJump(_ nums: [Int]) -> Bool {
    var furthest = 0
    for i in 0..<nums.count {
        furthest = max(furthest, i + nums[i])
    }
    return furthest >= nums.count - 1
}

fun canJump(nums: IntArray): Boolean {
    var furthest = 0
    for (i in nums.indices) {
        furthest = maxOf(furthest, i + nums[i])
    }
    return furthest >= nums.size - 1
}

boolean canJump(int[] nums) {
    int furthest = 0;
    for (int i = 0; i < nums.length; i++) {
        furthest = Math.max(furthest, i + nums[i]);
    }
    return furthest >= nums.length - 1;
}

function canJump(nums: number[]): boolean {
  let furthest = 0;
  for (let i = 0; i < nums.length; i++) {
    furthest = Math.max(furthest, i + nums[i]);
  }
  return furthest >= nums.length - 1;
}

The loop uses nums[i] from every index, including ones that can’t be reached. At i = 4, the 4 is beyond furthest = 3, but the code still adds its jump: furthest becomes 8 and the function says true. Only reachable indices may extend the frontier, so check first:

if i > furthest { return false }
furthest = max(furthest, i + nums[i])

if (i > furthest) return false
furthest = maxOf(furthest, i + nums[i])

if (i > furthest) return false;
furthest = Math.max(furthest, i + nums[i]);

if (i > furthest) return false;
furthest = Math.max(furthest, i + nums[i]);

Exercisemedium

Jump Game II

Same input, and the last index is always reachable. Return the minimum number of jumps to reach it. [2, 3, 1, 1, 4] → 2 (0 → 1 → 4).

›

Think of it as BFS without a queue: all indices reachable with k jumps form a contiguous range. The next range ends at the furthest index reachable from anywhere in the current one.

SolutionTry it yourself firstTime O(n)Space O(1)

func jump(_ nums: [Int]) -> Int {
    var jumps = 0, currentEnd = 0, furthest = 0
    for i in 0..<(nums.count - 1) {               // never jump from the last index
        furthest = max(furthest, i + nums[i])
        if i == currentEnd {                      // the current range is used up
            jumps += 1
            currentEnd = furthest
        }
    }
    return jumps
}

fun jump(nums: IntArray): Int {
    var jumps = 0; var currentEnd = 0; var furthest = 0
    for (i in 0 until nums.size - 1) {            // never jump from the last index
        furthest = maxOf(furthest, i + nums[i])
        if (i == currentEnd) {                    // the current range is used up
            jumps++
            currentEnd = furthest
        }
    }
    return jumps
}

int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, furthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {   // never jump from the last index
        furthest = Math.max(furthest, i + nums[i]);
        if (i == currentEnd) {                    // the current range is used up
            jumps++;
            currentEnd = furthest;
        }
    }
    return jumps;
}

function jump(nums: number[]): number {
  let jumps = 0, currentEnd = 0, furthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {     // never jump from the last index
    furthest = Math.max(furthest, i + nums[i]);
    if (i === currentEnd) {                       // the current range is used up
      jumps++;
      currentEnd = furthest;
    }
  }
  return jumps;
}

Each range [previousEnd + 1, currentEnd] is one BFS level. The loop stops before the last index, otherwise reaching it exactly at a range boundary would count one jump too many. Saying “this is level-order BFS on an implicit graph, compressed to O(1) space” is the explanation interviewers want; the DP alternative is O(n²).

Greedy = irrevocable local choice + same-shaped remaining problem. Correct only with the greedy-choice property and optimal substructure; be ready to argue it.
Common shape: track one frontier value (furthest reach, minimum so far, running balance) in one pass.
Jump Game: if i > furthest return false; furthest = max(furthest, i + nums[i]). Jump Game II: BFS levels as ranges, count when i == currentEnd, loop to n − 2.

Check this part

What does a greedy algorithm do at each step?
That's what makes it fast, and also why it can be wrong.
In Jump Game, the loop reaches index i and i > furthest. What does that mean?
Every reachable index is at most furthest; a gap means nothing beyond it is reachable.
Which two properties make a greedy algorithm correct?
Some optimal solution starts with the greedy choice, and the rest is solved by the same rule.
Jump Game II in O(n): what is the hidden structure?
Indices reachable in k jumps form a range; the next range ends at the furthest reach from it.

Greedy keeps one simple piece of state and updates it with the best local choice at every step. Jump Game only needs the furthest reachable index. It works when no local choice can ruin the final answer.

Part Not started

Sort, then choose

A large family of greedy solutions has the same shape: sort by the right key, then walk once and take what fits. Picking the key is the whole problem.

Assign Cookies. Each child has a greed factor g[i]: they’re happy with a cookie of at least that size. Each cookie has a size s[j], and each child gets at most one cookie. Maximize the number of happy children. g = [1, 2, 3], s = [1, 1] → 1. g = [1, 2], s = [1, 2, 3] → 2.

Smallest cookie for the least greedy child

func findContentChildren(_ greed: [Int], _ cookies: [Int]) -> Int {
    let g = greed.sorted(), s = cookies.sorted()
    var child = 0
    for cookie in s where child < g.count && cookie >= g[child] {
        child += 1                                // this cookie makes this child happy
    }
    return child
}

fun findContentChildren(greed: IntArray, cookies: IntArray): Int {
    val g = greed.sorted()
    val s = cookies.sorted()
    var child = 0
    for (cookie in s) {
        if (child < g.size && cookie >= g[child]) child++   // this cookie makes this child happy
    }
    return child
}

int findContentChildren(int[] greed, int[] cookies) {
    int[] g = greed.clone(), s = cookies.clone();
    Arrays.sort(g);
    Arrays.sort(s);
    int child = 0;
    for (int cookie : s) {
        if (child < g.length && cookie >= g[child]) child++;   // this cookie makes this child happy
    }
    return child;
}

function findContentChildren(greed: number[], cookies: number[]): number {
  const g = [...greed].sort((a, b) => a - b);
  const s = [...cookies].sort((a, b) => a - b);
  let child = 0;
  for (const cookie of s) {
    if (child < g.length && cookie >= g[child]) child++;   // this cookie makes this child happy
  }
  return child;
}

Walk through the cookies from smallest to largest. If the current cookie is big enough for the least greedy child who isn’t happy yet, give it to them. If not, it’s too small for every remaining child (they’re all at least as greedy), so throw it away. Sorting is O(n log n); the loop is O(n).

Why it’s right: the exchange argument

How do you know giving the smallest fitting cookie is never a mistake? Imagine a perfect assignment made by someone else. If they gave the least greedy child a bigger cookie than we did, swap: give that child our smaller cookie (it still fits) and give the bigger one to whoever had ours. Nobody becomes unhappy. Repeating the swap turns their perfect answer into ours without losing a happy child, so ours is perfect too.

That’s the exchange argument, and it’s how every greedy solution is justified.

Exchange argument: take any optimal solution O that differs from the greedy solution G at the first decision. Show you can modify O to agree with G at that decision without making it worse; by induction, G is optimal. For Assign Cookies: if O assigns cookie c' to the least greedy child where G assigns the smallest sufficient cookie c ≤ c', swap c and c' in O; feasibility and count are preserved. The other common proof is greedy stays ahead: after each step, the greedy partial solution is at least as good as any other by some measure (for interval scheduling: greedy’s k-th chosen interval ends no later than anyone’s k-th).

Exercisemedium

Boats to Save People

people[i] is a person’s weight. Each boat carries at most two people, with a total weight of at most limit. Return the minimum number of boats. Every person weighs at most limit.

people = [1, 2],       limit = 3  → 1
people = [3, 2, 2, 1], limit = 3  → 3   ([1, 2], [2], [3])
people = [3, 5, 3, 4], limit = 5  → 4

›

The heaviest person needs a boat no matter what. Who is the best partner for them?

›

Sort, then use two pointers: the heaviest person always boards; the lightest joins them if they fit together. If the lightest doesn’t fit with the heaviest, they won’t fit with anyone heavier either.

SolutionTry it yourself firstTime O(n log n)Space O(1) besides sorting

func numRescueBoats(_ people: [Int], _ limit: Int) -> Int {
    let p = people.sorted()
    var light = 0, heavy = p.count - 1, boats = 0
    while light <= heavy {
        if p[light] + p[heavy] <= limit { light += 1 }   // the lightest shares the boat
        heavy -= 1                                       // the heaviest always leaves
        boats += 1
    }
    return boats
}

fun numRescueBoats(people: IntArray, limit: Int): Int {
    val p = people.sorted()
    var light = 0; var heavy = p.size - 1; var boats = 0
    while (light <= heavy) {
        if (p[light] + p[heavy] <= limit) light++         // the lightest shares the boat
        heavy--                                           // the heaviest always leaves
        boats++
    }
    return boats
}

int numRescueBoats(int[] people, int limit) {
    int[] p = people.clone();
    Arrays.sort(p);
    int light = 0, heavy = p.length - 1, boats = 0;
    while (light <= heavy) {
        if (p[light] + p[heavy] <= limit) light++;        // the lightest shares the boat
        heavy--;                                          // the heaviest always leaves
        boats++;
    }
    return boats;
}

function numRescueBoats(people: number[], limit: number): number {
  const p = [...people].sort((a, b) => a - b);
  let light = 0, heavy = p.length - 1, boats = 0;
  while (light <= heavy) {
    if (p[light] + p[heavy] <= limit) light++;          // the lightest shares the boat
    heavy--;                                            // the heaviest always leaves
    boats++;
  }
  return boats;
}

Exchange argument: in any optimal plan, if the heaviest person shares a boat with someone other than the lightest, swapping that partner with the lightest person still fits (the lightest weighs no more), and the count doesn’t change. So pairing heaviest with lightest is always safe. When light == heavy, one person is left and takes a boat alone.

The wrong key

The key you sort by is the whole algorithm. Here’s a plausible greedy for “attend as many meetings as possible in one room”:

Spot the bugMost meetings in one room

Tap the line with the bug.

func maxMeetings(_ meetings: [Meeting]) -> Int {
    let sorted = meetings.sorted { ($0.end - $0.start) < ($1.end - $1.start) }
    var chosen: [Meeting] = []
    for m in sorted where chosen.allSatisfy({ m.start >= $0.end || m.end <= $0.start }) {
        chosen.append(m)
    }
    return chosen.count
}

fun maxMeetings(meetings: List<Meeting>): Int {
    val sorted = meetings.sortedBy { it.end - it.start }
    val chosen = mutableListOf<Meeting>()
    for (m in sorted) {
        if (chosen.all { m.start >= it.end || m.end <= it.start }) chosen.add(m)
    }
    return chosen.size
}

int maxMeetings(List<Meeting> meetings) {
    List<Meeting> sorted = meetings.stream().sorted(Comparator.comparingInt(m -> m.end() - m.start())).toList();
    List<Meeting> chosen = new ArrayList<>();
    for (Meeting m : sorted) {
        if (chosen.stream().allMatch(c -> m.start() >= c.end() || m.end() <= c.start())) chosen.add(m);
    }
    return chosen.size();
}

function maxMeetings(meetings: Meeting[]): number {
  const sorted = [...meetings].sort((a, b) => (a.end - a.start) - (b.end - b.start));
  const chosen: Meeting[] = [];
  for (const m of sorted) {
    if (chosen.every((c) => m.start >= c.end || m.end <= c.start)) chosen.push(m);
  }
  return chosen.length;
}

“Shortest first” sounds sensible, but a short meeting can sit across two longer ones that would both fit. With [1, 5], [4, 7], [6, 10], it takes [4, 7] (length 3) first, which blocks both others: 1 instead of 2. It’s also O(n²) because of the overlap check against every chosen meeting.

The right key is the earliest end: finishing first leaves the most room for everything after. With that order, a meeting fits exactly when it starts at or after the last chosen end, so one variable replaces the list:

var count = 0, lastEnd = Int.min
for m in meetings.sorted(by: { $0.end < $1.end }) where m.start >= lastEnd {
    count += 1
    lastEnd = m.end
}

var count = 0; var lastEnd = Int.MIN_VALUE
for (m in meetings.sortedBy { it.end }) {
    if (m.start >= lastEnd) { count++; lastEnd = m.end }
}

int count = 0, lastEnd = Integer.MIN_VALUE;
for (Meeting m : meetings.stream().sorted(Comparator.comparingInt(Meeting::end)).toList()) {
    if (m.start() >= lastEnd) { count++; lastEnd = m.end(); }
}

let count = 0, lastEnd = -Infinity;
for (const m of [...meetings].sort((a, b) => a.end - b.end)) {
  if (m.start >= lastEnd) { count++; lastEnd = m.end; }
}

Proof by “greedy stays ahead”: the k-th meeting greedy picks ends no later than the k-th meeting of any valid schedule, so greedy can always fit at least as many. Sorting by earliest start and by fewest conflicts both have counterexamples too; try to build them. The Intervals lesson continues from here.

Sort by the right key, then one pass: Assign Cookies (both ascending, smallest sufficient cookie), Boats (heaviest + lightest), interval scheduling (earliest end).
Prove it: exchange argument (swap an optimal solution’s first differing choice for the greedy one without loss) or greedy stays ahead (greedy’s k-th choice is at least as good as anyone’s k-th).
Wrong keys look plausible: shortest meeting first, earliest start, fewest conflicts all fail interval scheduling.

Check this part

In Assign Cookies, the smallest remaining cookie is too small for the least greedy child. What do you do with it?
All remaining children are at least as greedy, so nobody can use it.
What does the exchange argument show?
Repeating the swap turns any perfect answer into the greedy one, so greedy is perfect too.
To attend the most meetings in one room, sort by…
Ending first leaves the most room; the other keys have counterexamples.
Which proof technique fits interval scheduling most naturally?
By induction on k, greedy always has room for at least as many intervals.

Many greedy solutions sort first and then choose in one pass: the smallest cookie that satisfies the least greedy child, the meeting that ends earliest. The exchange argument proves it: swapping any optimal choice for the greedy one never makes things worse.

Part Not started

When greedy fails

Greedy coin change works for euro coins. Change the coins, and the same code gives a wrong answer:

Biggest coin first

func greedyCoins(_ coins: [Int], _ amount: Int) -> Int {
    var remaining = amount, count = 0
    for coin in coins.sorted(by: >) {          // biggest first
        count += remaining / coin
        remaining %= coin
    }
    return remaining == 0 ? count : -1
}

fun greedyCoins(coins: IntArray, amount: Int): Int {
    var remaining = amount; var count = 0
    for (coin in coins.sortedDescending()) {   // biggest first
        count += remaining / coin
        remaining %= coin
    }
    return if (remaining == 0) count else -1
}

int greedyCoins(int[] coins, int amount) {
    int[] sorted = coins.clone();
    Arrays.sort(sorted);
    int remaining = amount, count = 0;
    for (int i = sorted.length - 1; i >= 0; i--) {   // biggest first
        count += remaining / sorted[i];
        remaining %= sorted[i];
    }
    return remaining == 0 ? count : -1;
}

function greedyCoins(coins: number[], amount: number): number {
  let remaining = amount, count = 0;
  for (const coin of [...coins].sort((a, b) => b - a)) {   // biggest first
    count += Math.floor(remaining / coin);
    remaining %= coin;
  }
  return remaining === 0 ? count : -1;
}

With coins [1, 3, 4] and amount 6, greedy takes a 4, then two 1s: 3 coins. But 3 + 3 is 2 coins. Taking the 4 looked best at that moment, and it made the better combination impossible. With coins [2, 5] and amount 6, greedy takes a 5, then can’t make the remaining 1, and returns -1, even though 2 + 2 + 2 works.

When a choice now can block a better result later, greedy isn’t safe. The fix is to consider every choice and reuse the answers to smaller amounts: that’s dynamic programming, where Coin Change is solved properly.

Coin systems where greedy is optimal are called canonical (euro, US dollar). [1, 3, 4] isn’t: the greedy-choice property fails. 0/1 knapsack fails the same way (best value-per-weight first can leave unusable capacity), while fractional knapsack, where you may take part of an item, is exactly the greedy by value density. In an interview, “is greedy safe here?” is answered by either a proof sketch (exchange / stays ahead) or a small counterexample, and producing the counterexample quickly is the stronger signal.

How to check a greedy idea

Say the rule in one sentence: “always take the meeting that ends first”.
Try to break it with two or three tiny inputs, especially ones where the greedy choice is only slightly better than the alternative.
Compare with brute force on small random inputs if you can run code. Any difference is a counterexample.
If it survives, explain why with the exchange argument. If it breaks, the problem probably needs dynamic programming.

Predict the output

greedyCoins([1, 5, 6, 9], 11): what does it return, and what is the real minimum?

Exerciseeasy

Lemonade Change

Lemonade costs 5 EUR. Customers queue up and each pays with a 5, 10 or 20 EUR bill, one at a time. You start with no money. Return true if you can give every customer the right change.

[5, 5, 5, 10, 20]  → true
[5, 5, 10, 10, 20] → false

›

Track how many 5s and 10s you hold (20s are never useful as change). A 10 needs one 5 back. A 20 needs 15 back: either 10 + 5, or 5 + 5 + 5.

›

When both options for a 20 are possible, which one should you choose? Which bill is more useful for future customers?

SolutionTry it yourself firstTime O(n)Space O(1)

Give a 10 + 5 for a 20 whenever you can, and only use three 5s otherwise. A 5 can make change for a 10 and a 20; a 10 only helps with a 20. Keeping the more flexible bill is the greedy choice, and it’s safe: any plan that pays 5 + 5 + 5 while holding a 10 can swap two of those 5s for the 10 and never be worse off.

func lemonadeChange(_ bills: [Int]) -> Bool {
    var fives = 0, tens = 0
    for bill in bills {
        switch bill {
        case 5: fives += 1
        case 10:
            guard fives > 0 else { return false }
            fives -= 1; tens += 1
        default:                                    // 20
            if tens > 0 && fives > 0 { tens -= 1; fives -= 1 }
            else if fives >= 3 { fives -= 3 }
            else { return false }
        }
    }
    return true
}

fun lemonadeChange(bills: IntArray): Boolean {
    var fives = 0; var tens = 0
    for (bill in bills) {
        when (bill) {
            5 -> fives++
            10 -> {
                if (fives == 0) return false
                fives--; tens++
            }
            else -> when {                          // 20
                tens > 0 && fives > 0 -> { tens--; fives-- }
                fives >= 3 -> { fives -= 3 }
                else -> return false
            }
        }
    }
    return true
}

boolean lemonadeChange(int[] bills) {
    int fives = 0, tens = 0;
    for (int bill : bills) {
        if (bill == 5) {
            fives++;
        } else if (bill == 10) {
            if (fives == 0) return false;
            fives--; tens++;
        } else if (tens > 0 && fives > 0) {         // 20
            tens--; fives--;
        } else if (fives >= 3) {
            fives -= 3;
        } else {
            return false;
        }
    }
    return true;
}

function lemonadeChange(bills: number[]): boolean {
  let fives = 0, tens = 0;
  for (const bill of bills) {
    if (bill === 5) {
      fives++;
    } else if (bill === 10) {
      if (fives === 0) return false;
      fives--; tens++;
    } else if (tens > 0 && fives > 0) {             // 20
      tens--; fives--;
    } else if (fives >= 3) {
      fives -= 3;
    } else {
      return false;
    }
  }
  return true;
}

Exercisemedium

Gas Station

There are n gas stations on a circular route. Station i has gas[i] fuel, and driving from station i to i + 1 costs cost[i]. With an empty tank, find the starting station from which you can drive all the way around once, or -1. If a solution exists, it’s unique.

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]  → 3
gas = [2, 3, 4],       cost = [3, 4, 3]        → -1

›

If the total gas is less than the total cost, no start works. Otherwise, some start does. Which?

›

Drive from a candidate start. If the tank goes negative on arriving at station j, no station between the start and j can be the answer either. Why? Restart at j + 1.

SolutionTry it yourself firstTime O(n)Space O(1)

func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
    var total = 0, tank = 0, start = 0
    for i in 0..<gas.count {
        let diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if tank < 0 {                       // can't reach i + 1 from start, or from anything in between
            start = i + 1
            tank = 0
        }
    }
    return total >= 0 ? start : -1
}

fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
    var total = 0; var tank = 0; var start = 0
    for (i in gas.indices) {
        val diff = gas[i] - cost[i]
        total += diff
        tank += diff
        if (tank < 0) {                     // can't reach i + 1 from start, or from anything in between
            start = i + 1
            tank = 0
        }
    }
    return if (total >= 0) start else -1
}

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0, tank = 0, start = 0;
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        total += diff;
        tank += diff;
        if (tank < 0) {                     // can't reach i + 1 from start, or from anything in between
            start = i + 1;
            tank = 0;
        }
    }
    return total >= 0 ? start : -1;
}

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i];
    total += diff;
    tank += diff;
    if (tank < 0) {                         // can't reach i + 1 from start, or from anything in between
      start = i + 1;
      tank = 0;
    }
  }
  return total >= 0 ? start : -1;
}

Why skipping is safe: every station k between start and i was reached with a tank of at least 0, so starting at k with an empty tank can only be worse at i. Why the last candidate works when total ≥ 0: the deficit accumulated before start is exactly covered by the surplus from start to the end. This “skip the whole failed prefix” argument is the same one behind Kadane’s maximum-subarray algorithm.

Deep diveWhen is greedy provably optimal?Interview favorite

There’s a general answer: greedy is optimal for every weight function exactly on matroids, set systems where independent sets are closed under subsets and satisfy the exchange property (from a smaller independent set you can always add an element of a larger one). Spanning forests of a graph form a matroid, which is why Kruskal’s algorithm (take the cheapest edge that doesn’t form a cycle) finds a minimum spanning tree. Interviewers won’t expect the theory, but “this looks like Kruskal / like a matroid, so greedy by weight is safe” is a strong answer when it applies.

Greedy fails when an early choice blocks a better combination: non-canonical coins ([1, 3, 4], 6 → greedy 3, optimal 2), 0/1 knapsack. Fractional knapsack is greedy by density.
Validate: state the rule, attack it with tiny counterexamples, diff against brute force; if it breaks, use DP.
Gas Station: if total ≥ 0, the start is just after the last point where the running tank went negative. Same “skip the failed prefix” idea as Kadane.
Matroids (MST via Kruskal) are where greedy is provably optimal for any weights.

Gas Station

func canCompleteCircuit(_ gas: [Int], _ cost: [Int]) -> Int {
    var total = 0, tank = 0, start = 0
    for i in gas.indices { let d = gas[i] - cost[i]; total += d; tank += d; if tank < 0 { start = i + 1; tank = 0 } }
    return total >= 0 ? start : -1
}

fun canCompleteCircuit(gas: IntArray, cost: IntArray): Int {
    var total = 0; var tank = 0; var start = 0
    for (i in gas.indices) { val d = gas[i] - cost[i]; total += d; tank += d; if (tank < 0) { start = i + 1; tank = 0 } }
    return if (total >= 0) start else -1
}

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;
}

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  gas.forEach((g, i) => { const d = g - cost[i]; total += d; tank += d; if (tank < 0) { start = i + 1; tank = 0; } });
  return total >= 0 ? start : -1;
}

Check this part

Coins [1, 3, 4], amount 6. How many coins does "biggest coin first" use?
4 + 1 + 1. The best answer is 3 + 3, two coins: greedy isn't safe here.
How do you check whether a greedy rule is correct?
One counterexample is enough to reject it; an exchange argument is what accepts it.
Which knapsack variant is solved by greedy?
Taking part of an item removes the blocking effect that breaks 0/1.
Gas Station: the running tank goes negative at station i. Where can the answer be?
Each skipped station was reached with a non-negative tank, so starting there empty is no better.

Greedy fails when an early choice can block a better combination later: coin systems like [1, 3, 4], 0/1 knapsack. Test a greedy idea against brute force on small inputs; if a counterexample appears, switch to dynamic programming.

Key takeaways

A greedy algorithm takes the best-looking choice at each step and never undoes it.
Many greedy solutions are “sort by the right key, then take what fits in one pass”.
The exchange argument explains why it works: swapping a perfect answer’s choice for the greedy one never hurts.
Greedy can be confidently wrong (coins [1, 3, 4]); try small counterexamples, and use dynamic programming when it fails.

Correctness needs the greedy-choice property and optimal substructure; prove it with an exchange argument or “greedy stays ahead”.
Frontier tracking (Jump Game, Gas Station, Kadane) is the common one-pass greedy shape.
The sort key is the algorithm: earliest end for interval scheduling; plausible alternatives fail.
Produce a counterexample fast when greedy doesn’t hold, and switch to DP.