10.2 Greedy Algorithms

1. What Is a Greedy Algorithm?

A Greedy Algorithm solves an optimization problem step-by-step by always picking the choice that looks best right now (the locally optimal choice) and never undoing or reconsidering past choices.

2. Why Do We Need Greedy & When Does It Work vs. Fail?

Why Greedy Is Amazing When It Works

Backtracking explores an exponential tree (O(2^N)), and Dynamic Programming builds a table of subproblems (O(N^2)). When a problem has the Greedy Choice Property (meaning taking the best immediate step never locks you out of the best overall outcome), Greedy solves it in one O(N) pass with O(1) memory!

How to Tell Greedy vs. Dynamic Programming Apart

• Where Greedy Works (Jump Game): You stand at index 0 and each nums[i] tells you the maximum jump length from i. Why explore every jump combination? If you can reach index farthest, you can also reach every single index before farthest! So tracking a single variable farthest = max(farthest, i + nums[i]) is 100% sufficient.
• Where Greedy Fails (Coin Change with [1, 3, 4], target 6): Greedy grabs the biggest coin (4), forcing 4 + 1 + 1 (3 coins), whereas 3 + 3 uses only 2 coins! Whenever a greedy choice today can hurt you tomorrow, use Dynamic Programming instead.

Quick Decision Table: Should I Use Greedy or Dynamic Programming?

3. Basic Operations & Walkthroughs (All 4 Languages)

# 1. Jump Game: Track the furthest index reachable so far -> O(N) time, O(1) space
def can_jump(nums: list[int]) -> bool:
  farthest = 0
  for i, jump in enumerate(nums):
      if i > farthest:
          return False  # We landed on an unreachable gap!
      farthest = max(farthest, i + jump)
  return True

# 2. Gas Station: Reset starting station whenever tank drops below 0 -> O(N)
def can_complete_circuit(gas: list[int], cost: list[int]) -> int:
  if sum(gas) < sum(cost):
      return -1  # Total fuel < total cost -> impossible!
  tank = start = 0
  for i in range(len(gas)):
      tank += gas[i] - cost[i]
      if tank < 0:
          start = i + 1
          tank = 0
  return start

4. Core Interview Patterns & Common Traps

jumps = 0
cur_end = farthest = 0
for i in range(len(nums) - 1):
  farthest = max(farthest, i + nums[i])
  if i == cur_end:        # Finished scanning current jump's reach!
      jumps += 1
      cur_end = farthest  # Commit to the furthest reach for next jump
return jumps

5. Practice On Your Own (Curated Submodule Problems)