Greedy Algorithms Explained

What is a Greedy Algorithm?

A greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate benefit. The key insight is that by making the locally optimal choice at each step, we hope to arrive at a globally optimal solution.

Think of it like climbing a hill in fog: you can only see a few feet ahead, so you always step in the direction that goes upward. Greedy algorithms work the same way - they make the best decision with the information available right now, without looking ahead or reconsidering past choices.

When Does Greedy Work?

Greedy algorithms don't always produce optimal solutions. They work when the problem has two key properties:

1. Greedy Choice Property

A global optimum can be reached by making locally optimal choices. In other words, we never need to reconsider our choices - what seems best now will be part of the final answer.

2. Optimal Substructure

An optimal solution to the problem contains optimal solutions to its subproblems. After making a greedy choice, we're left with a smaller subproblem that has the same structure as the original.

// Classic greedy example: Coin Change (with specific denominations)
// Given coins [25, 10, 5, 1], make change for 41 cents

function makeChangeGreedy(amount: number, coins: number[]): number[] {
  const result: number[] = []
  // Sort coins in descending order
  coins.sort((a, b) => b - a)

  for (const coin of coins) {
    while (amount >= coin) {
      result.push(coin)
      amount -= coin
    }
  }

  return result
}

// makeChangeGreedy(41, [25, 10, 5, 1])
// Returns: [25, 10, 5, 1] → 4 coins
// This is optimal for US currency!

When Greedy Fails: Counterexamples

Understanding when greedy doesn't work is just as important as knowing when it does. Here are common pitfalls:

Coin Change with Arbitrary Denominations

The greedy approach fails for many coin systems. Consider coins [1, 3, 4] and amount 6:

• Greedy: 4 + 1 + 1 = 3 coins
• Optimal: 3 + 3 = 2 coins

The greedy choice (picking the largest coin) leads to a suboptimal solution. This is why LeetCode's Coin Change problem requires dynamic programming.

0/1 Knapsack

Greedy by value-to-weight ratio doesn't work when you can't take fractional items. However, the Fractional Knapsack problem can be solved greedily.

Key Insight

When you suspect greedy might work, try to find a counterexample. If you can't, it's a good sign greedy is correct. In interviews, you might say: "I believe greedy works here because [reason]. Let me verify with an example..."

Classic Greedy Problems

Problem 1: Jump Game

LeetCode 55: Given an array where each element represents your maximum jump length, determine if you can reach the last index.

function canJump(nums: number[]): boolean {
  let maxReach = 0

  for (let i = 0; i < nums.length; i++) {
    // If we can't reach current position, we're stuck
    if (i > maxReach) {
      return false
    }

    // Greedily update the farthest we can reach
    maxReach = Math.max(maxReach, i + nums[i])

    // Early exit if we can already reach the end
    if (maxReach >= nums.length - 1) {
      return true
    }
  }

  return true
}

// Example: canJump([2,3,1,1,4]) → true
// Start at index 0, jump to 1, jump to 4 (end)

// Example: canJump([3,2,1,0,4]) → false
// We get stuck at index 3 (value 0)

Why greedy works: At each position, we only care about the farthest point reachable. We don't need to track all possible paths - just whether the end is reachable.

Problem 2: Gas Station

LeetCode 134: There are n gas stations in a circle. You have a car with unlimited tank capacity. Return the starting station index if you can complete the circuit, otherwise return -1.

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalTank = 0
  let currentTank = 0
  let startStation = 0

  for (let i = 0; i < gas.length; i++) {
    const netGain = gas[i] - cost[i]
    totalTank += netGain
    currentTank += netGain

    // If we can't reach station i+1, restart from i+1
    if (currentTank < 0) {
      startStation = i + 1
      currentTank = 0
    }
  }

  // If total gas >= total cost, a solution exists
  // and startStation is the answer
  return totalTank >= 0 ? startStation : -1
}

// Example: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
// Returns: 3 (start at station 3)

// Key insight: If we fail at station i starting from j,
// we also fail starting from any station between j and i.
// So we can skip directly to i+1.

Why greedy works: If total gas >= total cost, a solution exists. When we run out of gas at station i, none of the stations before i can be the starting point (they would also run out), so we skip to i+1.

Problem 3: Meeting Rooms II

LeetCode 253: Given meeting intervals, find the minimum number of conference rooms required.

function minMeetingRooms(intervals: number[][]): number {
  if (intervals.length === 0) return 0

  // Separate start and end times, then sort
  const starts = intervals.map(i => i[0]).sort((a, b) => a - b)
  const ends = intervals.map(i => i[1]).sort((a, b) => a - b)

  let rooms = 0
  let endPtr = 0

  for (let i = 0; i < starts.length; i++) {
    // If the earliest ending meeting ends before this one starts,
    // we can reuse that room
    if (starts[i] >= ends[endPtr]) {
      endPtr++
    } else {
      // Otherwise, we need a new room
      rooms++
    }
  }

  return rooms
}

// Example: intervals = [[0,30],[5,10],[15,20]]
// Returns: 2
// Meeting [5,10] overlaps with [0,30], so we need 2 rooms

// Alternative: Use a min-heap for end times
// Heap approach is more intuitive but same O(n log n) complexity

Why greedy works: We process meetings by start time and greedily assign each meeting to the room that becomes free earliest. If no room is free, we need a new room.

Problem 4: Task Scheduler

LeetCode 621: Given tasks with cooldown period n, find the minimum time to complete all tasks.

function leastInterval(tasks: string[], n: number): number {
  // Count frequency of each task
  const freq = new Map<string, number>()
  let maxFreq = 0

  for (const task of tasks) {
    const count = (freq.get(task) || 0) + 1
    freq.set(task, count)
    maxFreq = Math.max(maxFreq, count)
  }

  // Count how many tasks have the maximum frequency
  let maxCount = 0
  for (const count of freq.values()) {
    if (count === maxFreq) {
      maxCount++
    }
  }

  // Formula: (maxFreq - 1) * (n + 1) + maxCount
  // This represents the minimum slots needed
  const minSlots = (maxFreq - 1) * (n + 1) + maxCount

  // Answer is max of minSlots and total tasks
  // (we might have enough tasks to fill all idle slots)
  return Math.max(minSlots, tasks.length)
}

// Example: tasks = ['A','A','A','B','B','B'], n = 2
// Returns: 8
// One valid sequence: A B idle A B idle A B

// Visualization:
// A _ _ A _ _ A    (place most frequent first)
// A B _ A B _ A B  (fill gaps with other tasks)

// Why greedy: Always schedule the most frequent task first
// to minimize idle time.

Why greedy works: By scheduling the most frequent task first, we create the skeleton of our schedule. Other tasks fill the gaps, minimizing idle time.

Problem 5: Partition Labels

LeetCode 763: Partition a string so that each letter appears in at most one partition. Return the sizes of all partitions.

function partitionLabels(s: string): number[] {
  // Find the last occurrence of each character
  const lastIndex = new Map<string, number>()
  for (let i = 0; i < s.length; i++) {
    lastIndex.set(s[i], i)
  }

  const result: number[] = []
  let partitionStart = 0
  let partitionEnd = 0

  for (let i = 0; i < s.length; i++) {
    // Extend partition to include last occurrence of current char
    partitionEnd = Math.max(partitionEnd, lastIndex.get(s[i])!)

    // If we've reached the end of current partition
    if (i === partitionEnd) {
      result.push(partitionEnd - partitionStart + 1)
      partitionStart = i + 1
    }
  }

  return result
}

// Example: s = "ababcbacadefegdehijhklij"
// Returns: [9, 7, 8]
// Partitions: "ababcbaca" | "defegde" | "hijhklij"

// Why greedy: We must include all occurrences of each char
// in the same partition. Extend the partition end greedily
// as we encounter chars with later last occurrences.

Why greedy works: Once we include a character in a partition, we must extend to include all its occurrences. We greedily extend the current partition and only close it when we've seen all necessary characters.

Greedy vs Dynamic Programming

Both approaches have optimal substructure, but they differ in a key way:

• Greedy: Makes one choice and never looks back. O(n) or O(n log n) time, O(1) space typically.
• DP: Considers all choices and picks the best. Often O(n^2) or more, uses O(n) or O(n^2) space.

When greedy works, it's usually faster. But proving greedy correctness can be tricky. In interviews, if you're unsure, DP is the safer choice - it's correct by construction.

Pro Tips for Interviews

• Sort first: Many greedy problems become easier after sorting (by start time, end time, deadline, profit, etc.)
• Prove correctness: Explain why the greedy choice is safe. "If we don't take this option now, we can't do better later because..."
• Test with counterexamples: Before committing to greedy, try to break it with a tricky input
• Use heaps when needed: Min-heaps help when you need the "smallest/earliest" element repeatedly
• Draw timelines: For interval problems, visualize the timeline to see the greedy choice

Practice Problems

Ready to test your understanding? Try these LeetCode problems:

• Easy: Best Time to Buy and Sell Stock II, Assign Cookies
• Medium: Jump Game, Gas Station, Task Scheduler, Partition Labels
• Hard: Jump Game II, Candy, IPO, Meeting Rooms III

Continue Learning

• Dynamic Programming Guide - When greedy fails, DP often works
• Two Pointers Pattern - Another efficient approach for array problems
• Sliding Window Technique - Often used alongside greedy for subarray problems
• Start Practicing - Apply greedy algorithms to real interview problems