Greedy Algorithms Explained

A greedy algorithm makes the best decision at each step based only on the information available now, never revisiting earlier choices. It produces optimal solutions for a specific class of problems, and recognizing that class is the real interview skill. Jump games, gas stations, and interval scheduling are the FAANG favorites.

Greedy Choice Property and Exchange Argument

A greedy algorithm is correct when two properties hold:

• Greedy choice property: the locally optimal pick is part of some global optimum.
• Optimal substructure: the rest of the problem after that pick is still solvable greedily.

Interviews rarely ask for a full proof, but an exchange argument is the standard one: assume an optimal solution differs from the greedy one, swap the greedy pick in, and show the result is no worse. Saying this aloud is a strong signal.

Jump Game (Can You Reach the End?)

Track the furthest index reachable so far. At each step, if the current index exceeds maxReach, you are stuck.

function canJump(nums: number[]): boolean {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;       // unreachable
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}
// Time: O(n), Space: O(1)

Jump Game II (Minimum Steps)

The greedy insight: within the current "window" you can jump from, you never revisit positions already covered. Count how many ever-expanding windows you must cross.

function jump(nums: number[]): number {
  let jumps = 0, currentEnd = 0, farthest = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    farthest = Math.max(farthest, i + nums[i]);
    if (i === currentEnd) {               // edge of current window
      jumps++;
      currentEnd = farthest;
    }
  }
  return jumps;
}

Gas Station

If total gas is less than total cost, no solution exists. Otherwise, starting from the first point where the running surplus goes negative gives a guaranteed valid station. This restarts-and-carry trick is the entire problem.

function canCompleteCircuit(gas: number[], cost: number[]): number {
  let total = 0, tank = 0, start = 0;
  for (let i = 0; i < gas.length; i++) {
    total += gas[i] - cost[i];
    tank += gas[i] - cost[i];
    if (tank < 0) { tank = 0; start = i + 1; }
  }
  return total < 0 ? -1 : start;
}

Non-overlapping Intervals

The greedy rule: sort by end time, and always keep the interval that finishes earliest, because it frees the most space for the rest. This is the activity-selection proof in disguise.

function eraseOverlapIntervals(intervals: number[][]): number {
  intervals.sort((a, b) => a[1] - b[1]);
  let end = -Infinity, kept = 0;
  for (const [s, e] of intervals) {
    if (s >= end) { kept++; end = e; }
  }
  return intervals.length - kept;
}

Candy (Even Distribution)

Two passes capture both constraints with O(1) memory beyond the result: left-to-right ensures each child with a higher rating than the previous neighbor gets more candy, then right-to-left propagates the reverse. This is a pure greedy with no backtracking.

function candy(ratings: number[]): number {
  const n = ratings.length;
  const candies = new Array(n).fill(1);
  for (let i = 1; i < n; i++) {
    if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 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((a, b) => a + b, 0);
}

When Greedy Fails (and When It Works)

• Fails on coin change with arbitrary denominations : greedy count of the largest coin is wrong; use DP.
• Fails on 0/1 knapsack : taking the best value-to-weight item greedily can miss the optimal combination; that is DP.
• Works on interval scheduling, jump games, gas stations, and minimal spanning trees : these satisfy the greedy choice property.
• Works on Huffman coding : merging the two least-frequent symbols is provably optimal.

Quick heuristic: if choosing the locally best option never leaves you worse off relative to any competitor, greedy wins. If a bad early choice can ruin later ones, reach for DP, backtracking, or BFS.

Common Mistakes

• Applying greedy without checking the greedy choice property; counterexamples hide in small inputs like coin change.
• Not attempting an exchange-argument justification when the interviewer probes correctness.
• Sorting by the wrong key : interval problems sort by end, others by start.
• Re-rendering every step in Jump Game II instead of using the window trick, driving complexity to O(n²).
• Forgetting edge cases like zero-length jumps or never-reachable totals : confirm against a small failing input.

Frequently Asked Questions

Related Tutorials

• Dynamic Programming : when greedy's local rule stops being safe.
• Intervals : the scheduling problems greedy dominates.
• Two Pointers : greedy sweeps pair naturally with sorted pointers.
• Greedy practice problems : company-tagged questions.