Greedy Algorithms

What is a greedy algorithm

A greedy algorithm makes the locally optimal choice at every step and never reconsiders it. No backtracking, no exploring alternatives. The bet is that a sequence of locally optimal decisions produces a globally optimal solution.

Contrast with dynamic programming:

Greedy is faster and simpler — but only correct for problems with two structural properties:

1. Greedy-choice property: a globally optimal solution can be assembled from locally optimal choices.
2. Optimal substructure: the optimal solution to the problem contains optimal solutions to its subproblems.

DP requires only optimal substructure. Greedy requires both. This is why greedy fails for arbitrary coin change but DP handles it.

Proving greedy correctness: the exchange argument

The standard proof technique for greedy algorithms is the exchange argument:

Assume an optimal solution OPT exists that differs from the greedy solution G. Find the first position where they diverge. Show that you can swap OPT’s choice at that position with G’s choice without making the solution worse. Repeat until OPT equals G, proving G is also optimal.

Demonstration — Activity Selection: given activities with start and end times, select the maximum number of non-overlapping activities.

Greedy choice: always pick the activity with the earliest end time.

Exchange argument: let OPT be optimal. If OPT chooses activity x first and greedy chooses y where end(y) <= end(x), replace x with y in OPT. Since y ends no later than x, it conflicts with no more future activities — so OPT remains feasible and just as large. Repeat for every divergence. Conclusion: greedy is optimal.

This exact structure — “swap the greedy choice in without harm” — is the proof you articulate at a FAANG interview when asked to justify a greedy approach.

Jump Game (LC 55)

Problem: Given nums[i] = maximum jump length from index i, can you reach the last index?

Greedy: track the furthest index reachable from all positions seen so far. If at any point the current index exceeds that furthest reach, you are stuck.

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

  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false       // can't reach index i
    maxReach = Math.max(maxReach, i + nums[i])
  }

  return true
}
// Time: O(n)  Space: O(1)

maxReach is updated greedily at every step. No DP table needed — the single number captures all the state required.

Jump Game II (LC 45)

Problem: Find the minimum number of jumps to reach the last index. Assume you can always reach the end.

Greedy — BFS-style: think in “levels” like BFS. Each level is the range of indices reachable in exactly jumps moves. At each step, greedily extend as far as possible within the current level. When you exhaust the current level, increment jumps and start the next.

function jump(nums: number[]): number {
  let jumps = 0
  let currentEnd = 0    // end of the current "jump level"
  let farthest = 0      // furthest index reachable so far

  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i])

    if (i === currentEnd) {
      // Must jump — we've reached the end of this level
      jumps++
      currentEnd = farthest
    }
  }

  return jumps
}
// Time: O(n)  Space: O(1)

Intuition: within a level, scan all reachable positions and record the furthest they can reach. When the level is exhausted, one jump gets you to any position in the next level. Greedy — always maximise the reach of each jump.

Gas Station (LC 134)

Problem: n gas stations arranged in a circle. gas[i] = gas gained at station i, cost[i] = gas to travel to the next station. Find the starting station index that allows completing the full circuit, or return -1.

Two key observations:

1. If sum(gas) < sum(cost), no solution exists — not enough total fuel.
2. If a solution exists, start from the station after the last point of deficit.

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalSurplus = 0
  let currentSurplus = 0
  let startIndex = 0

  for (let i = 0; i < gas.length; i++) {
    const diff = gas[i] - cost[i]
    totalSurplus += diff
    currentSurplus += diff

    if (currentSurplus < 0) {
      // Can't start at or before i — reset and try starting from i+1
      startIndex = i + 1
      currentSurplus = 0
    }
  }

  return totalSurplus >= 0 ? startIndex : -1
}
// Time: O(n)  Space: O(1)

Why the start after last failure is correct: if we fail at station i starting from j, then starting from any station between j and i would also fail (they would inherit the already-negative surplus). So we skip all of them and try i+1. Combined with the total surplus check, exactly one valid starting point exists when a solution exists.

Task Scheduler (LC 621)

Problem: Given tasks (letters) with a cooldown n (same task must be separated by at least n other tasks or idles), find the minimum time to finish all tasks.

Greedy formula: arrange the most frequent tasks in a grid with n+1 columns. Remaining tasks fill gaps; excess tasks extend beyond the grid.

function leastInterval(tasks: string[], n: number): number {
  const freq = new Array(26).fill(0)
  for (const t of tasks) freq[t.charCodeAt(0) - 65]++

  const maxFreq = Math.max(...freq)
  // How many tasks share the maximum frequency?
  const countMaxFreq = freq.filter(f => f === maxFreq).length

  // Formula: arrange maxFreq-1 full frames of size (n+1), plus the last row
  const minTime = (maxFreq - 1) * (n + 1) + countMaxFreq

  // Can never take less time than the total number of tasks
  return Math.max(minTime, tasks.length)
}
// Time: O(n)  Space: O(1)

Proof of the formula: picture the most frequent task A appearing maxFreq times. Place one A at the start of each frame. There are maxFreq - 1 gaps between the last A and each prior A, each of size n. Fill them with other tasks or idles. The last frame has only the tasks tied for maximum frequency. When total tasks exceeds the grid (many tasks to fill the idles), tasks.length dominates.

Candy (LC 135)

Problem: n children in a line, each with a rating. Give each child at least 1 candy. Children with higher ratings than their immediate neighbours must receive more candies. Minimise total candies.

Two-pass greedy: satisfy left-neighbour constraint first, then right-neighbour constraint.

function candy(ratings: number[]): number {
  const n = ratings.length
  const candies = new Array(n).fill(1)

  // Left to right: if rating[i] > rating[i-1], give i one more than i-1
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) {
      candies[i] = candies[i - 1] + 1
    }
  }

  // Right to left: if rating[i] > rating[i+1], ensure i has more than i+1
  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((sum, c) => sum + c, 0)
}
// Time: O(n)  Space: O(n)

Why two passes: after the left-to-right pass, right-neighbour constraints may be violated. The right-to-left pass fixes them while taking the max to preserve left-neighbour gains already made.

Assign Cookies (LC 455)

Problem: Each child has a greed factor g[i]. Each cookie has size s[j]. Assign at most one cookie per child; a cookie satisfies a child if s[j] >= g[i]. Maximise the number of content children.

Greedy: sort both arrays. Try to satisfy the least greedy child first with the smallest sufficient cookie.

function findContentChildren(g: number[], s: number[]): number {
  g.sort((a, b) => a - b)
  s.sort((a, b) => a - b)

  let child = 0, cookie = 0

  while (child < g.length && cookie < s.length) {
    if (s[cookie] >= g[child]) child++   // cookie satisfies this child
    cookie++                              // move to next cookie regardless
  }

  return child
}
// Time: O(n log n + m log m)  Space: O(1)
// n = children, m = cookies

Exchange argument: using a larger cookie on an easy child wastes capacity — the same child could be satisfied by a smaller cookie, freeing the larger one for a greedier child.

Partition Labels (LC 763)

Problem: Partition a string so that each letter appears in at most one part. Return the sizes of the parts.

Greedy: record the last occurrence of each character. Scan left to right, expanding the current partition’s end to the last occurrence of each character seen. When the current index reaches the partition end, close it.

function partitionLabels(s: string): number[] {
  // Record 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 sizes: number[] = []
  let partStart = 0
  let partEnd = 0

  for (let i = 0; i < s.length; i++) {
    partEnd = Math.max(partEnd, lastIndex.get(s[i])!)

    if (i === partEnd) {
      sizes.push(partEnd - partStart + 1)
      partStart = i + 1
    }
  }

  return sizes
}
// Time: O(n)  Space: O(1)  — at most 26 characters in the map

Intuition: once we know the last occurrence of every character in the current window, we know the earliest point at which we can safely close the partition. We greedily close it as soon as possible.

When greedy fails: coin change

Classic counterexample. Consider denominations [1, 3, 4] and target 6.

• Greedy (largest coin first): 4 + 1 + 1 = 3 coins
• Optimal: 3 + 3 = 2 coins

Greedy fails because choosing 4 locally looks great but globally forecloses the better 3+3 option. The greedy-choice property does not hold — a locally optimal choice (use the largest denomination) does not guarantee a globally optimal result.

US coins [1, 5, 10, 25] work greedily because each denomination is a multiple of smaller ones (approximately), preserving the greedy-choice property. Arbitrary denominations break this structure.

Rule: when faced with a minimisation or maximisation problem involving choices with complex interactions, try greedy first — but if you can construct a counterexample, switch to DP.

Greedy vs DP decision guide

Can I find a counterexample to the greedy choice?
├─ YES → use DP
└─ NO  → can I prove the exchange argument?
         ├─ YES → greedy is safe
         └─ UNSURE → try greedy, verify on edge cases
                     (and be ready to pivot to DP in the interview)

Try greedy first when:

• The problem involves picking or scheduling items in order (activity selection, task scheduling)
• Optimal local choice is obvious — smallest/largest/earliest
• O(n log n) time is acceptable

Fall back to DP when:

• Multiple overlapping subproblems (choices affect each other)
• Greedy fails on a constructed counterexample
• Problem asks for counts of ways, not just one optimal solution

Complexity reference