Greedy Algorithms: When Committing Without Looking Back Is Correct

Greedy algorithms have a reputation as the "unprovable" category. You look at a problem, have an intuition, and code it up — but the proof that local choices produce a global optimum feels hand-wavy. That's frustrating when you're sitting in an interview wondering if your approach is actually correct or just lucky.

Here's the thing: once you've seen a few greedy problems, you start to recognize the structural property that makes greedy work. It's not magic. It's called the greedy choice property — at each step, making the locally optimal choice doesn't close off globally optimal solutions. And once you see it in action across a few different problem shapes, it becomes something you can argue for, not just hope about.

Three problems here. Jump Game (can you reach the end?), Gas Station (circular resource allocation), and Partition Labels (segment maximally independent groups). Each one expresses the greedy intuition differently.

What Makes a Problem "Greedy-Solvable"

A problem is greedy-solvable when you can prove that a locally optimal choice at each step never eliminates the globally optimal solution. The classic counterexample is coin change with arbitrary denominations — greedy fails because picking the largest coin first can block you from reaching the exact total. But with standard denominations (25, 10, 5, 1), greedy is optimal.

For interview purposes, the signal is usually: "Can I maintain a single running variable that captures all the information I need?" If yes, you probably have a greedy problem. If you need to look ahead or compare options at each step, it might be DP.

Problem 1: Jump Game (LeetCode 55)

The problem: Given an integer array nums where nums[i] is the maximum jump length from index i, return true if you can reach the last index starting from index 0.

Input: [2, 3, 1, 1, 4] → true
Input: [3, 2, 1, 0, 4] → false

The Greedy Insight

You don't care how you reached a position — you care about the farthest you can reach from any reachable position. Maintain a single variable maxReach: the farthest index you can land on. For each index i you haven't passed yet, update maxReach = max(maxReach, i + nums[i]). If i ever exceeds maxReach, you're stuck.

For [3, 2, 1, 0, 4]:

Approach 1: Brute Force (Backtracking)

// O(2^n) time, O(n) space — explores all possible jumps
const canJumpBrute = (nums) => {
  const dfs = (i) => {
    if (i >= nums.length - 1) return true;
    for (let jump = nums[i]; jump >= 1; jump--) {
      if (dfs(i + jump)) return true;
    }
    return false;
  };
  return dfs(0);
};

Exponential. Explores redundant paths.

Approach 2: DP — O(n²)

// O(n²) time, O(n) space
const canJumpDP = (nums) => {
  const n = nums.length;
  const dp = new Array(n).fill(false);
  dp[0] = true;
 
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && j + nums[j] >= i) {
        dp[i] = true;
        break;
      }
    }
  }
 
  return dp[n - 1];
};

Correct, but unnecessarily quadratic.

Approach 3: Greedy — O(n) Time, O(1) Space

// O(n) time, O(1) space
const canJump = (nums) => {
  let maxReach = 0;
 
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false; // Can't reach this position
    maxReach = Math.max(maxReach, i + nums[i]);
  }
 
  return true;
};

The greedy property here: maxReach represents the frontier of all reachable positions. We never need to remember which specific path got us here — only how far forward we can reach.

Problem 2: Gas Station (LeetCode 134)

The problem: There are n gas stations on a circular route. Station i has gas[i] liters and costs cost[i] to reach the next station. Find the starting station index from which you can complete the full circuit. Return -1 if impossible. Guaranteed at most one valid answer.

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3

Two Key Observations

Observation 1: If the total gas across all stations is less than the total cost, no solution exists. You need sum(gas) >= sum(cost) to go around the full circuit.

Observation 2: If a valid starting point exists, you can find it greedily. Start at station 0 and maintain a running tank. Whenever the tank goes negative, the current starting point (and every station up to this one) can't work — reset the tank and set the new candidate starting point to i + 1.

Why does this work? If you can't complete the trip starting from station s and you run out of gas at station f, then no station between s and f is a valid start either. Starting mid-journey means you'd arrive at f with even less gas (you skipped the early gas stations). So the next candidate must be after f.

The single greedy pass over net = gas[i] - cost[i] = [-2, -2, -2, 3, 3]:

Approach 1: Brute Force

// O(n²) time, O(1) space — try each starting station
const canCompleteCircuitBrute = (gas, cost) => {
  const n = gas.length;
 
  for (let start = 0; start < n; start++) {
    let tank = 0;
    let completed = true;
 
    for (let i = 0; i < n; i++) {
      const station = (start + i) % n;
      tank += gas[station] - cost[station];
      if (tank < 0) {
        completed = false;
        break;
      }
    }
 
    if (completed) return start;
  }
 
  return -1;
};

Approach 2: Greedy — O(n) Time, O(1) Space

// O(n) time, O(1) space
const canCompleteCircuit = (gas, cost) => {
  let totalTank = 0;
  let currentTank = 0;
  let startStation = 0;
 
  for (let i = 0; i < gas.length; i++) {
    const net = gas[i] - cost[i];
    totalTank += net;
    currentTank += net;
 
    if (currentTank < 0) {
      // Can't start from startStation — try starting from i+1
      startStation = i + 1;
      currentTank = 0;
    }
  }
 
  // If total gas < total cost, no solution exists
  return totalTank >= 0 ? startStation : -1;
};

The elegant part: you make one pass. totalTank tells you if any solution exists at all; currentTank + the reset logic tells you where that solution is.

Problem 3: Partition Labels (LeetCode 763)

The problem: Given a string s, partition it into as many parts as possible such that each letter appears in at most one part. Return the lengths of each part.

Input: s = "ababcbacadefegdehijhklij"
Output: [9, 7, 8]

The Greedy Strategy

For each character, you need to know the last position it appears. Once you have that, the algorithm is:

1. Scan left to right, tracking the farthest "last position" of any character seen so far in the current partition.
2. When your current index reaches that farthest position, you've found a valid partition boundary — cut here.

Why is this greedy correct? You're forced to include every occurrence of every character you've started collecting. The partition boundary can't be any earlier than the last occurrence of any character in the current segment. Making the cut as early as legally possible maximizes the number of partitions.

Approach 1: Brute Force

// O(n²) time, O(1) space — check each possible partition boundary
const partitionLabelsBrute = (s) => {
  const result = [];
  let start = 0;
 
  while (start < s.length) {
    let end = start;
    let i = start;
 
    while (i <= end) {
      // Extend end to include all occurrences of s[i]
      for (let j = s.length - 1; j > end; j--) {
        if (s[j] === s[i]) {
          end = j;
          break;
        }
      }
      i++;
    }
 
    result.push(end - start + 1);
    start = end + 1;
  }
 
  return result;
};

Approach 2: Greedy with Last-Position Map

// O(n) time, O(1) space — O(1) because only 26 lowercase letters
const partitionLabels = (s) => {
  // Step 1: Record the last occurrence of each character
  const last = {};
  for (let i = 0; i < s.length; i++) {
    last[s[i]] = i;
  }
 
  // Step 2: Scan and cut at partition boundaries
  const result = [];
  let partitionStart = 0;
  let farthest = 0;
 
  for (let i = 0; i < s.length; i++) {
    farthest = Math.max(farthest, last[s[i]]);
 
    if (i === farthest) {
      result.push(farthest - partitionStart + 1);
      partitionStart = i + 1;
    }
  }
 
  return result;
};

Walk through "ababcbacadefegdehijhklij":

• At i=0 (a): last a is at 8, farthest=8
• At i=1 (b): last b is at 5, farthest=8
• At i=5 (b): last b is at 5, farthest=8
• At i=8 (a): i === farthest, cut. Partition length = 9.
• Continue with d, e, f, g... cut at i=14. Length = 7.
• Continue with h, i, j, k, l... cut at i=23. Length = 8.

Clean, one preprocessing pass, one scan.

Interview Tips

On Jump Game: The follow-up is almost always Jump Game II (LeetCode 45) — minimum number of jumps to reach the end. The same maxReach idea extends naturally: you maintain a currentEnd (end of current jump's reach) and a nextEnd (farthest reach from current positions). When i === currentEnd, increment the jump counter and advance currentEnd = nextEnd. Practice that version; it's frequently asked.

On Gas Station: If the interviewer asks why you're allowed to reset startStation without trying intermediate stations first, walk through the invariant: every station before the reset failed (either directly, or transitively because starting there would give you less gas when you hit the wall). This is the crux of the proof — be ready to explain it in 30 seconds.

On Partition Labels: The problem asks for lengths, but it's easy to also return the actual substrings. Common follow-up: "What if a character can appear in at most two parts?" Then you'd track second-to-last positions instead. The algorithm structure stays the same; only the preprocessing changes.

General greedy advice: When you claim a greedy approach in an interview, be ready to argue (briefly) why the greedy choice doesn't block globally optimal solutions. You don't need a formal proof, but "I make the locally best choice and it can't hurt the global answer because..." is the right framing. Interviewers at strong companies will push on this.

The through-line: all three problems reduce to "maintain one piece of state, update it as you scan, act when a condition is met." Once you see that structure, greedy problems stop feeling like guesswork.