ReslandDSA Study Center

Greedy Algorithms

Commit to the choice that looks best at each step and never revisit it. Fast and simple, but only correct when you can prove that choice is safe.

IntermediateRead first: Arrays & Hash Maps

How It Works

A greedy algorithm builds its answer one step at a time. At each step it commits to whatever looks best right now and never goes back. When that's correct, it's usually the simplest solution there is. Most greedy solutions take one of two shapes: sort the input so the best candidate comes first and take what fits, or make one pass while tracking a single running value, such as the farthest index you can reach.

Jump Game, Step by Step

Step 1 of 13

nums

  • Reachable so far
  • Index being visited
  • Visited
  • Out of reach

Can you get from index 0 to the last index of [2, 3, 1, 1, 4]? Start with farthest = 0: so far you can only stand where you start.

All 13 steps as text
  1. Can you get from index 0 to the last index of [2, 3, 1, 1, 4]? Start with farthest = 0: so far you can only stand where you start.
  2. Index 0 is within reach (0 <= 0). A jump from it lands anywhere up to 0 + 2 = 2, past 0, so farthest = 2.
  3. Index 1 is within reach (1 <= 2). A jump from it lands anywhere up to 1 + 3 = 4, past 2, so farthest = 4. That covers the last index.
  4. Index 2 is within reach (2 <= 4), but 2 + 1 = 3 doesn't beat farthest = 4, so it stays.
  5. Index 3 is within reach (3 <= 4), but 3 + 1 = 4 doesn't beat farthest = 4, so it stays.
  6. Index 4 is within reach (4 <= 4). A jump from it lands anywhere up to 4 + 4 = 8, past 4, so farthest = 8.
  7. The loop visited every index without passing farthest, so the last index is reachable. canJump returns true.
  8. Now try [3, 2, 1, 0, 4]. Start over with farthest = 0.
  9. Index 0 is within reach (0 <= 0). A jump from it lands anywhere up to 0 + 3 = 3, past 0, so farthest = 3.
  10. Index 1 is within reach (1 <= 3), but 1 + 2 = 3 doesn't beat farthest = 3, so it stays.
  11. Index 2 is within reach (2 <= 3), but 2 + 1 = 3 doesn't beat farthest = 3, so it stays.
  12. Index 3 is within reach (3 <= 3), but nums[3] = 0, so you can't jump on from it. farthest stays 3.
  13. Index 4 is past farthest = 3. No index before it can jump that far, so canJump returns false.

Greedy is safe when the problem has the greedy-choice property: some optimal answer starts with the greedy choice, and what's left afterwards is a smaller copy of the same problem. You show it with an exchange argument. Take any optimal answer that disagrees with greedy's first choice, swap greedy's choice in, and check that the result is still valid and no worse. If that swap always works, greedy never loses.

For example, to fit the most non-overlapping meetings into one room, keep taking the meeting that ends first among those that don't clash with the ones you've already taken. Whatever meeting an optimal schedule starts with, you can swap in the earliest-ending one instead. It ends no later, so it can't run into any meeting the schedule had after it. The Intervals topic uses the same rule.

Greedy fails when the best move now leaves you worse off later. Coin change is the classic trap. With coins [1, 3, 4] and amount 6, taking the largest coin that fits gives 4 + 1 + 1, three coins, while 3 + 3 needs only two. With US coins (1, 5, 10 and 25 cents) the same rule happens to work, which is exactly why it's tempting.

coins = [1, 3, 4], amount = 6

greedy   4 + 1 + 1   3 coins
optimal  3 + 3       2 coins
Taking the 4 first leaves 2, which only two 1s can pay.

When a counterexample like that exists, you have to compare the choices instead of trusting one, which is what Dynamic Programming: 1D does for coin change. Before you trust a greedy rule, spend a minute hunting for a small input that breaks it. If you can't find one, try to write the exchange argument.

When to Reach for It

  • The question asks for a minimum or maximum, like the fewest jumps or the most meetings, and one move looks clearly best at each step.
  • Sorting by a single key, such as end time, deadline or size, makes every decision easy.
  • The input is large (100,000 items or more), so an O(n²) dynamic program won't fit, but a single pass would.
  • You only need one running value, like the farthest point reached or a running balance, rather than every possible state.

Complexity

OperationTimeSpace
One pass with a running value (Jump Game, Gas Station)O(n)O(1)
Sort, then one pass (most non-overlapping meetings)O(n log n)O(1) to O(n), depending on the sort
Repeatedly take the best item from a heapO(n log n)O(n)

The Template

Jump Game

Given nums, where nums[i] is the longest jump you can make from index i, can you get from index 0 to the last index? You don't need to decide which jump to take. Track farthest, the farthest index any jump so far can reach. Every index up to farthest is reachable too, because a jump from i can land anywhere from i + 1 to i + nums[i], not just at the end.

So walk left to right and extend farthest with i + nums[i]. If you ever stand on an index past farthest, nothing before it can reach it, and the answer is false. If the loop finishes, every index was reachable.

Time O(n)Space O(1)

def can_jump(nums: list[int]) -> bool:
    """Whether you can reach the last index from index 0, where nums[i] is the
    longest jump you can make from index i."""
    farthest = 0  # Every index up to here is reachable.
    for i, jump in enumerate(nums):
        if i > farthest:
            return False  # Nothing before i can reach it.
        farthest = max(farthest, i + jump)
    return True


if __name__ == "__main__":
    print(can_jump([2, 3, 1, 1, 4]))  # True
    print(can_jump([3, 2, 1, 0, 4]))  # False
    print(can_jump([0]))  # True
// Whether you can reach the last index from index 0, where nums[i] is the
// longest jump you can make from index i.
export function canJump(nums: number[]): boolean {
  let farthest = 0; // Every index up to here is reachable.
  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false; // Nothing before i can reach it.
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}

console.log(canJump([2, 3, 1, 1, 4])); // true
console.log(canJump([3, 2, 1, 0, 4])); // false
console.log(canJump([0])); // true
package main

import "fmt"

// canJump reports whether you can reach the last index from index 0, where
// nums[i] is the longest jump you can make from index i.
func canJump(nums []int) bool {
	farthest := 0 // Every index up to here is reachable.
	for i, jump := range nums {
		if i > farthest {
			return false // Nothing before i can reach it.
		}
		farthest = max(farthest, i+jump)
	}
	return true
}

func main() {
	fmt.Println(canJump([]int{2, 3, 1, 1, 4})) // true
	fmt.Println(canJump([]int{3, 2, 1, 0, 4})) // false
	fmt.Println(canJump([]int{0}))             // true
}
using System;

public class Solution
{
    // Whether you can reach the last index from index 0, where nums[i] is the
    // longest jump you can make from index i.
    public static bool CanJump(int[] nums)
    {
        int farthest = 0; // Every index up to here is reachable.
        for (int i = 0; i < nums.Length; i++)
        {
            if (i > farthest) return false; // Nothing before i can reach it.
            farthest = Math.Max(farthest, i + nums[i]);
        }
        return true;
    }

    public static void Main()
    {
        Console.WriteLine(CanJump(new[] { 2, 3, 1, 1, 4 })); // True
        Console.WriteLine(CanJump(new[] { 3, 2, 1, 0, 4 })); // False
        Console.WriteLine(CanJump(new[] { 0 })); // True
    }
}
public class Solution {
    // Whether you can reach the last index from index 0, where nums[i] is the
    // longest jump you can make from index i.
    static boolean canJump(int[] nums) {
        int farthest = 0; // Every index up to here is reachable.
        for (int i = 0; i < nums.length; i++) {
            if (i > farthest) return false; // Nothing before i can reach it.
            farthest = Math.max(farthest, i + nums[i]);
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canJump(new int[] {2, 3, 1, 1, 4})); // true
        System.out.println(canJump(new int[] {3, 2, 1, 0, 4})); // false
        System.out.println(canJump(new int[] {0})); // true
    }
}

Worked Problems

Each solution stays folded until you open it, so you can try the problem first. Every one is a complete program in Python, TypeScript, Go, C# and Java, run and checked against its expected output.

Jump Game II

MEDIUMLeetCode 45

Problem

Same setup as Jump Game: nums[i] is the longest jump you can make from index i, and you start at index 0. This time the last index is always reachable. Return the fewest jumps it takes to get there.

Example: [2, 3, 1, 1, 4] returns 2. Jump 1 step to index 1, then 3 steps to the last index.

Show Solution

Approach

Think of it as a breadth-first search over ranges of indices. With 0 jumps you can only stand at index 0. With 1 jump you can reach any index up to nums[0]. With each further jump, you can reach anything up to the farthest point the previous range can jump to. Count ranges until one covers the last index.

index    0  1  2  3  4
nums     2  3  1  1  4

0 jumps  0
1 jump      1  2
2 jumps           3  4
Each row holds the indices you first reach with that many jumps.

In the code, currentEnd is the end of the current range and farthest is the end of the next one, built up as you scan. When i reaches currentEnd, you've seen everything this many jumps can reach, so you take another jump and the next range begins. The loop stops before the last index, because standing on it means you've arrived. If it ran one step further, it would count an extra jump whenever a range ends exactly on the last index.

Time O(n)Space O(1)

def min_jumps(nums: list[int]) -> int:
    """Fewest jumps from index 0 to the last index, where nums[i] is the longest
    jump you can make from index i. Assumes the last index is reachable."""
    jumps = 0
    current_end = 0  # Farthest index reachable with `jumps` jumps.
    farthest = 0  # Farthest index reachable with one more.
    # Stop before the last index: once you stand on it, you're done jumping.
    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            # You've seen every index this many jumps can reach. Take another.
            jumps += 1
            current_end = farthest
    return jumps


if __name__ == "__main__":
    print(min_jumps([2, 3, 1, 1, 4]))  # 2
    print(min_jumps([1, 1, 1, 1]))  # 3
    print(min_jumps([0]))  # 0
// Fewest jumps from index 0 to the last index, where nums[i] is the longest
// jump you can make from index i. Assumes the last index is reachable.
export function minJumps(nums: number[]): number {
  let jumps = 0;
  let currentEnd = 0; // Farthest index reachable with `jumps` jumps.
  let farthest = 0; // Farthest index reachable with one more.
  // Stop before the last index: once you stand on it, you're done jumping.
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {
      // You've seen every index this many jumps can reach. Take another.
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

console.log(minJumps([2, 3, 1, 1, 4])); // 2
console.log(minJumps([1, 1, 1, 1])); // 3
console.log(minJumps([0])); // 0
package main

import "fmt"

// minJumps returns the fewest jumps from index 0 to the last index, where
// nums[i] is the longest jump you can make from index i. It assumes the last
// index is reachable.
func minJumps(nums []int) int {
	jumps := 0
	currentEnd := 0 // Farthest index reachable with `jumps` jumps.
	farthest := 0   // Farthest index reachable with one more.
	// Stop before the last index: once you stand on it, you're done jumping.
	for i := 0; i < len(nums)-1; i++ {
		farthest = max(farthest, i+nums[i])
		if i == currentEnd {
			// You've seen every index this many jumps can reach. Take another.
			jumps++
			currentEnd = farthest
		}
	}
	return jumps
}

func main() {
	fmt.Println(minJumps([]int{2, 3, 1, 1, 4})) // 2
	fmt.Println(minJumps([]int{1, 1, 1, 1}))    // 3
	fmt.Println(minJumps([]int{0}))             // 0
}
using System;

public class Solution
{
    // Fewest jumps from index 0 to the last index, where nums[i] is the longest
    // jump you can make from index i. Assumes the last index is reachable.
    public static int MinJumps(int[] nums)
    {
        int jumps = 0;
        int currentEnd = 0; // Farthest index reachable with `jumps` jumps.
        int farthest = 0; // Farthest index reachable with one more.
        // Stop before the last index: once you stand on it, you're done jumping.
        for (int i = 0; i < nums.Length - 1; i++)
        {
            farthest = Math.Max(farthest, i + nums[i]);
            if (i == currentEnd)
            {
                // You've seen every index this many jumps can reach. Take another.
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }

    public static void Main()
    {
        Console.WriteLine(MinJumps(new[] { 2, 3, 1, 1, 4 })); // 2
        Console.WriteLine(MinJumps(new[] { 1, 1, 1, 1 })); // 3
        Console.WriteLine(MinJumps(new[] { 0 })); // 0
    }
}
public class Solution {
    // Fewest jumps from index 0 to the last index, where nums[i] is the longest
    // jump you can make from index i. Assumes the last index is reachable.
    static int minJumps(int[] nums) {
        int jumps = 0;
        int currentEnd = 0; // Farthest index reachable with `jumps` jumps.
        int farthest = 0; // Farthest index reachable with one more.
        // Stop before the last index: once you stand on it, you're done jumping.
        for (int i = 0; i < nums.length - 1; i++) {
            farthest = Math.max(farthest, i + nums[i]);
            if (i == currentEnd) {
                // You've seen every index this many jumps can reach. Take another.
                jumps++;
                currentEnd = farthest;
            }
        }
        return jumps;
    }

    public static void main(String[] args) {
        System.out.println(minJumps(new int[] {2, 3, 1, 1, 4})); // 2
        System.out.println(minJumps(new int[] {1, 1, 1, 1})); // 3
        System.out.println(minJumps(new int[] {0})); // 0
    }
}

Gas Station

MEDIUMLeetCode 134

Problem

Gas stations sit on a circular road. Station i has gas[i] fuel to pick up, and driving from station i to the next one burns cost[i]. Your tank starts empty and has no limit. Return the station to start from so you can drive all the way around once, or -1 if no start works. When an answer exists, it's unique.

Example: gas = [1, 2, 3, 4, 5] and cost = [3, 4, 5, 1, 2] returns 3. Starting at station 3, you pick up 4 and burn 1, leaving 3, and the tank never goes negative on the way around.

Show Solution

Approach

Trying every start and simulating the loop is O(n²). Two observations bring it down to one pass:

  1. If the total gas is less than the total cost, no start can work, because the loop as a whole burns more than it gets. Otherwise some start does work, and the next point finds it.
  2. Drive from start and keep a running tank. If it drops below zero on the way to station i + 1, then start fails, and so does every station between start and i. You reached each of them with zero or more fuel, so starting there with an empty tank can only leave you worse off. Skip them all and try i + 1.
station      0   1   2   3   4
gas - cost  -2  -2  -2  +3  +3
tank        -2  -2  -2   3   6
start        1   2   3   3   3
The tank goes negative at stations 0, 1 and 2, so the start moves past each one and the tank resets. The total is 0, so station 3 works.

Why does the last candidate work? The stretch from it to the end of the array never ran dry, and every stretch before it ended in a deficit. A total of zero or more means the fuel you carry past the end is enough to cover those deficits as you wrap around.

Time O(n)Space O(1)

def starting_station(gas: list[int], cost: list[int]) -> int:
    """The station to start from to drive once around the loop, or -1 if none
    works. gas[i] is the fuel at station i, and cost[i] is the fuel it takes to
    drive from station i to the next one."""
    total = 0  # Net fuel over the whole loop.
    tank = 0  # Fuel left since leaving start.
    start = 0
    for i in range(len(gas)):
        total += gas[i] - cost[i]
        tank += gas[i] - cost[i]
        if tank < 0:
            # Stuck before station i + 1. Every station from start to i fails too,
            # since you reached each one with zero or more fuel. Try i + 1 next.
            start = i + 1
            tank = 0
    return start if total >= 0 else -1  # A non-negative total means start works.


if __name__ == "__main__":
    print(starting_station([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]))  # 3
    print(starting_station([2, 3, 4], [3, 4, 3]))  # -1
    print(starting_station([3, 1, 1], [1, 2, 2]))  # 0
// The station to start from to drive once around the loop, or -1 if none
// works. gas[i] is the fuel at station i, and cost[i] is the fuel it takes to
// drive from station i to the next one.
export function startingStation(gas: number[], cost: number[]): number {
  let total = 0; // Net fuel over the whole loop.
  let tank = 0; // Fuel left since leaving start.
  let start = 0;
  for (let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i];
    tank += gas[i] - cost[i];
    if (tank < 0) {
      // Stuck before station i + 1. Every station from start to i fails too,
      // since you reached each one with zero or more fuel. Try i + 1 next.
      start = i + 1;
      tank = 0;
    }
  }
  return total >= 0 ? start : -1; // A non-negative total means start works.
}

console.log(startingStation([1, 2, 3, 4, 5], [3, 4, 5, 1, 2])); // 3
console.log(startingStation([2, 3, 4], [3, 4, 3])); // -1
console.log(startingStation([3, 1, 1], [1, 2, 2])); // 0
package main

import "fmt"

// startingStation returns the station to start from to drive once around the
// loop, or -1 if none works. gas[i] is the fuel at station i, and cost[i] is
// the fuel it takes to drive from station i to the next one.
func startingStation(gas, cost []int) int {
	total := 0 // Net fuel over the whole loop.
	tank := 0  // Fuel left since leaving start.
	start := 0
	for i := range gas {
		total += gas[i] - cost[i]
		tank += gas[i] - cost[i]
		if tank < 0 {
			// Stuck before station i + 1. Every station from start to i fails too,
			// since you reached each one with zero or more fuel. Try i + 1 next.
			start = i + 1
			tank = 0
		}
	}
	if total < 0 {
		return -1
	}
	return start // A non-negative total means start works.
}

func main() {
	fmt.Println(startingStation([]int{1, 2, 3, 4, 5}, []int{3, 4, 5, 1, 2})) // 3
	fmt.Println(startingStation([]int{2, 3, 4}, []int{3, 4, 3}))             // -1
	fmt.Println(startingStation([]int{3, 1, 1}, []int{1, 2, 2}))             // 0
}
using System;

public class Solution
{
    // The station to start from to drive once around the loop, or -1 if none
    // works. gas[i] is the fuel at station i, and cost[i] is the fuel it takes to
    // drive from station i to the next one.
    public static int StartingStation(int[] gas, int[] cost)
    {
        int total = 0; // Net fuel over the whole loop.
        int tank = 0; // Fuel left since leaving start.
        int start = 0;
        for (int i = 0; i < gas.Length; i++)
        {
            total += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0)
            {
                // Stuck before station i + 1. Every station from start to i fails too,
                // since you reached each one with zero or more fuel. Try i + 1 next.
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1; // A non-negative total means start works.
    }

    public static void Main()
    {
        Console.WriteLine(StartingStation(new[] { 1, 2, 3, 4, 5 }, new[] { 3, 4, 5, 1, 2 })); // 3
        Console.WriteLine(StartingStation(new[] { 2, 3, 4 }, new[] { 3, 4, 3 })); // -1
        Console.WriteLine(StartingStation(new[] { 3, 1, 1 }, new[] { 1, 2, 2 })); // 0
    }
}
public class Solution {
    // The station to start from to drive once around the loop, or -1 if none
    // works. gas[i] is the fuel at station i, and cost[i] is the fuel it takes to
    // drive from station i to the next one.
    static int startingStation(int[] gas, int[] cost) {
        int total = 0; // Net fuel over the whole loop.
        int tank = 0; // Fuel left since leaving start.
        int start = 0;
        for (int i = 0; i < gas.length; i++) {
            total += gas[i] - cost[i];
            tank += gas[i] - cost[i];
            if (tank < 0) {
                // Stuck before station i + 1. Every station from start to i fails too,
                // since you reached each one with zero or more fuel. Try i + 1 next.
                start = i + 1;
                tank = 0;
            }
        }
        return total >= 0 ? start : -1; // A non-negative total means start works.
    }

    public static void main(String[] args) {
        System.out.println(startingStation(new int[] {1, 2, 3, 4, 5}, new int[] {3, 4, 5, 1, 2})); // 3
        System.out.println(startingStation(new int[] {2, 3, 4}, new int[] {3, 4, 3})); // -1
        System.out.println(startingStation(new int[] {3, 1, 1}, new int[] {1, 2, 2})); // 0
    }
}

Common Pitfalls

  • Trusting a greedy rule because it passed the examples. Try small inputs where the best move now blocks a better one later, as coins [1, 3, 4] with amount 6 do.
  • Sorting by the wrong key. To keep the most non-overlapping intervals, sort by end time. Sorting by start or by length can lock in a bad pick early.
  • Assuming greedy means taking the biggest value. The safe choice is whatever an exchange argument supports, like the earliest end time, and often it isn't the largest anything.
  • In Jump Game II, looping all the way to the last index. If a range ends exactly there, you count a jump you never take.
  • In Gas Station, retrying from start + 1 after running dry instead of jumping to i + 1. It still finds the answer, but it rechecks stations already ruled out and becomes O(n²).

Practice

More problems to try on your own.