Greedy Algorithms — When a Local Choice Is Provably Optimal

Q: Why does Gas Station work in one pass?

If the tank goes negative somewhere between start and i, then no station in that range can be a valid start either — any later start begins with strictly less accumulated fuel. So the search can jump straight to i + 1 instead of retrying each station, turning O(n²) into O(n). The separate sum(gas) >= sum(cost) check decides whether any answer exists.

Greedy is the pattern with the smallest code and the highest risk. Take the locally best option at each step and never revisit it — which is either optimal or badly wrong, with nothing in between. The interview skill is not writing greedy code; it is justifying that greedy applies.

When greedy works

Two conditions must hold:

Greedy choice property — a locally optimal choice is part of some globally optimal

solution.

Optimal substructure — after making that choice, the rest is the same problem on a

smaller input.

The standard proof is the exchange argument: take any optimal solution that differs from the greedy one, swap in the greedy choice, and show the result is no worse. You do not need a formal write-up in an interview — but you do need the sentence. "Sorting by end time is safe because finishing earliest leaves the most room for everything after it" is what turns a guess into an answer.

When you cannot make that argument, the choice interacts with future ones and it is DP. Coin Change is the standard counterexample: greedily taking the largest coin fails on coins [1, 3, 4] for amount 6 — greedy gives 4 + 1 + 1, optimal is 3 + 3.

Sort, then sweep

Most greedy problems begin with a sort that makes the safe choice obvious.

def find_content_children(g, s):        # Assign Cookies
    g.sort()                            # child greed
    s.sort()                            # cookie sizes
    child = cookie = 0
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1                  # satisfied: move to the next child
        cookie += 1
    return child

int findContentChildren(int[] g, int[] s) {
    Arrays.sort(g);   // child greed
    Arrays.sort(s);   // cookie sizes
    int child = 0, cookie = 0;

    while (child < g.length && cookie < s.length) {
        if (s[cookie] >= g[child]) child++;   // satisfied: next child
        cookie++;
    }
    return child;
}

int findContentChildren(vector<int>& g, vector<int>& s) {
    sort(g.begin(), g.end());   // child greed
    sort(s.begin(), s.end());   // cookie sizes
    int child = 0, cookie = 0;

    while (child < (int)g.size() && cookie < (int)s.size()) {
        if (s[cookie] >= g[child]) child++;   // satisfied: next child
        cookie++;
    }
    return child;
}

static int cmp(const void* a, const void* b) {
    return (*(int*)a) - (*(int*)b);
}

int findContentChildren(int* g, int gn, int* s, int sn) {
    qsort(g, gn, sizeof(int), cmp);
    qsort(s, sn, sizeof(int), cmp);
    int child = 0, cookie = 0;

    while (child < gn && cookie < sn) {
        if (s[cookie] >= g[child]) child++;   /* satisfied: next child */
        cookie++;
    }
    return child;
}

function findContentChildren(g, s) {
  g.sort((a, b) => a - b);   // child greed
  s.sort((a, b) => a - b);   // cookie sizes
  let child = 0, cookie = 0;

  while (child < g.length && cookie < s.length) {
    if (s[cookie] >= g[child]) child++;   // satisfied: next child
    cookie++;
  }
  return child;
}

Giving the smallest sufficient cookie to the least greedy child is safe by exchange: any optimal assignment can be rewritten to make that pairing without satisfying fewer children.

The interval problems — Minimum Number of Arrows, Non-overlapping Intervals — are the same shape sorted by end time.

Track a running best

The other family needs no sort, just one scan with a well-chosen invariant.

def can_jump(nums):                     # Jump Game
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:
            return False                # stranded
        reach = max(reach, i + jump)
    return True

boolean canJump(int[] nums) {
    int reach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > reach) return false;              // stranded
        reach = Math.max(reach, i + nums[i]);
    }
    return true;
}

bool canJump(const vector<int>& nums) {
    int reach = 0;
    for (int i = 0; i < (int)nums.size(); i++) {
        if (i > reach) return false;              // stranded
        reach = max(reach, i + nums[i]);
    }
    return true;
}

bool canJump(int* nums, int n) {
    int reach = 0;
    for (int i = 0; i < n; i++) {
        if (i > reach) return false;              /* stranded */
        if (i + nums[i] > reach) reach = i + nums[i];
    }
    return true;
}

function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;                // stranded
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

def can_complete_circuit(gas, cost):    # Gas Station
    if sum(gas) < sum(cost):
        return -1                       # no solution exists at all
    start = tank = 0
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:                    # cannot reach i + 1 from start
            start = i + 1               # so no station in start..i can work either
            tank = 0
    return start

int canCompleteCircuit(int[] gas, int[] cost) {
    int total = 0;
    for (int i = 0; i < gas.length; i++) total += gas[i] - cost[i];
    if (total < 0) return -1;      // global feasibility is a SEPARATE check

    int start = 0, tank = 0;
    for (int i = 0; i < gas.length; i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {            // cannot reach i + 1 from start, and no
            start = i + 1;         // station in start..i can work either
            tank = 0;
        }
    }
    return start;
}

int canCompleteCircuit(const vector<int>& gas, const vector<int>& cost) {
    int total = 0;
    for (size_t i = 0; i < gas.size(); i++) total += gas[i] - cost[i];
    if (total < 0) return -1;      // global feasibility is a SEPARATE check

    int start = 0, tank = 0;
    for (size_t i = 0; i < gas.size(); i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {            // no station in start..i can work either
            start = (int)i + 1;
            tank = 0;
        }
    }
    return start;
}

int canCompleteCircuit(int* gas, int* cost, int n) {
    int total = 0;
    for (int i = 0; i < n; i++) total += gas[i] - cost[i];
    if (total < 0) return -1;      /* global feasibility, checked separately */

    int start = 0, tank = 0;
    for (int i = 0; i < n; i++) {
        tank += gas[i] - cost[i];
        if (tank < 0) {            /* no station in start..i can work either */
            start = i + 1;
            tank = 0;
        }
    }
    return start;
}

function canCompleteCircuit(gas, cost) {
  const total = gas.reduce((sum, g, i) => sum + g - cost[i], 0);
  if (total < 0) return -1;      // global feasibility is a SEPARATE check

  let start = 0, tank = 0;
  for (let i = 0; i < gas.length; i++) {
    tank += gas[i] - cost[i];
    if (tank < 0) {              // no station in start..i can work either
      start = i + 1;
      tank = 0;
    }
  }
  return start;
}

Gas Station's insight is worth stating explicitly: if you run dry between start and i, then no station in that range can be a valid start either — each one begins with less fuel than you had. That collapses an O(n²) search to O(n).

Partition Labels

Greedy with a precomputed lookahead. Each letter must appear in exactly one part, so the current part cannot end before the last occurrence of every letter it contains.

def partition_labels(s):
    last = {ch: i for i, ch in enumerate(s)}
    out, start, end = [], 0, 0
    for i, ch in enumerate(s):
        end = max(end, last[ch])
        if i == end:                    # nothing inside reaches further
            out.append(i - start + 1)
            start = i + 1
    return out

List<Integer> partitionLabels(String s) {
    int[] last = new int[26];
    for (int i = 0; i < s.length(); i++) last[s.charAt(i) - 'a'] = i;

    List<Integer> out = new ArrayList<>();
    int start = 0, end = 0;
    for (int i = 0; i < s.length(); i++) {
        end = Math.max(end, last[s.charAt(i) - 'a']);
        if (i == end) {          // nothing inside this part reaches further
            out.add(i - start + 1);
            start = i + 1;
        }
    }
    return out;
}

vector<int> partitionLabels(const string& s) {
    int last[26] = {0};
    for (int i = 0; i < (int)s.size(); i++) last[s[i] - 'a'] = i;

    vector<int> out;
    int start = 0, end = 0;
    for (int i = 0; i < (int)s.size(); i++) {
        end = max(end, last[s[i] - 'a']);
        if (i == end) {          // nothing inside this part reaches further
            out.push_back(i - start + 1);
            start = i + 1;
        }
    }
    return out;
}

/* Caller owns the returned array; *count receives its length. */
int* partitionLabels(char* s, int* count) {
    int last[26] = {0};
    int n = strlen(s);
    for (int i = 0; i < n; i++) last[s[i] - 'a'] = i;

    int* out = malloc(n * sizeof(int));
    *count = 0;
    int start = 0, end = 0;
    for (int i = 0; i < n; i++) {
        if (last[s[i] - 'a'] > end) end = last[s[i] - 'a'];
        if (i == end) {          /* nothing inside reaches further */
            out[(*count)++] = i - start + 1;
            start = i + 1;
        }
    }
    return out;
}

function partitionLabels(s) {
  const last = new Map();
  for (let i = 0; i < s.length; i++) last.set(s[i], i);

  const out = [];
  let start = 0, end = 0;
  for (let i = 0; i < s.length; i++) {
    end = Math.max(end, last.get(s[i]));
    if (i === end) {           // nothing inside this part reaches further
      out.push(i - start + 1);
      start = i + 1;
    }
  }
  return out;
}

Two-pass greedy: Candy

The one that teaches the most. Each child needs more candy than a lower-rated neighbour on

both sides, and a single pass cannot satisfy both directions at once. So do two, and take

the maximum:

def candy(ratings):
    n = len(ratings)
    candies = [1] * n
    for i in range(1, n):               # left to right: fix the left neighbour
        if ratings[i] > ratings[i - 1]:
            candies[i] = candies[i - 1] + 1
    for i in range(n - 2, -1, -1):      # right to left: fix the right one
        if ratings[i] > ratings[i + 1]:
            candies[i] = max(candies[i], candies[i + 1] + 1)
    return sum(candies)

int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);

    // A constraint pulling in two directions needs one pass per direction,
    // then a max — a single pass cannot satisfy both.
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }

    int total = 0;
    for (int c : candies) total += c;
    return total;
}

int candy(const vector<int>& ratings) {
    int n = ratings.size();
    vector<int> candies(n, 1);

    // One pass per direction, then a max.
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = max(candies[i], candies[i + 1] + 1);
        }
    }
    return accumulate(candies.begin(), candies.end(), 0);
}

int candy(int* ratings, int n) {
    int* candies = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) candies[i] = 1;

    for (int i = 1; i < n; i++) {              /* fix the left neighbour */
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
    }
    for (int i = n - 2; i >= 0; i--) {         /* fix the right neighbour */
        if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {
            candies[i] = candies[i + 1] + 1;
        }
    }

    int total = 0;
    for (int i = 0; i < n; i++) total += candies[i];
    free(candies);
    return total;
}

function candy(ratings) {
  const n = ratings.length;
  const candies = new Array(n).fill(1);

  // A constraint pulling in two directions needs one pass per direction.
  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);
}

Whenever a constraint pulls in two directions, one pass per direction and a max at the end is the reflex to have.

Complexity

O(n log n) when a sort leads, O(n) when it does not — which is precisely why greedy is worth proving rather than abandoning for a safe O(n²) or a DP table.

Mistakes that cost the round

Applying greedy without an argument. If you cannot say why the local choice is safe,

it probably is not.

Sorting by the wrong key. End time versus start time changes the answer entirely.
Missing the global feasibility check. Gas Station needs sum(gas) >= sum(cost)

separately; the scan finds where to start, not whether a start exists.

One pass on a two-sided constraint, as in Candy.
Confusing "works on the examples" with "is correct". Greedy failures are usually

invisible on small inputs.

What to drill

Assign Cookies — sort and sweep.
Partition Labels — precomputed lookahead.
Jump Game — a running reach.
Gas Station — the restart argument.
Hand of Straights — greedy with a counter.
Valid Parenthesis String — track a range of possible open counts.
Candy — two passes.

All on the 22 DSA Patterns sheet.

Frequently asked

How do I know if a problem can be solved greedily?

It needs two properties: a locally optimal choice must be part of some globally optimal solution, and the remainder after that choice must be the same problem on a smaller input. The practical test is whether you can give an exchange argument — take any optimal solution, swap in the greedy choice, and show it is no worse. If you cannot, use DP.

What is the difference between greedy and dynamic programming?

Greedy commits to one choice at each step and never reconsiders; DP explores every choice and keeps the best. Greedy is faster — usually O(n log n) against DP's polynomial table — but only correct when the greedy choice property holds. Coin Change with coins [1,3,4] is the standard example where greedy fails and DP does not.

Why does Gas Station work in one pass?

If the tank goes negative somewhere between start and i, then no station in that range can be a valid start either — any later start begins with strictly less accumulated fuel. So the search can jump straight to i + 1 instead of retrying each station, turning O(n²) into O(n). The separate sum(gas) >= sum(cost) check decides whether any answer exists.

Greedy