What does a locally optimal choice mean in a greedy algorithm?

AlgorithmsJunior~2 min read

Short answer

A locally optimal choice in a greedy algorithm is an action that, at each step, selects the best option by some current criterion (maximum gain, minimum cost, etc.) without evaluating all future consequences. The algorithm repeats such choices, hoping to obtain a globally optimal solution.

Detailed answer

What "locally optimal choice" means

This is a strategy: among all options available at the current step, the algorithm picks the one that looks best by a local criterion (for example, "earliest end date," "highest value density," "smallest edge weight"). The algorithm does not backtrack or reconsider decisions - it builds the answer step by step.

Local criterion: the "better/worse" metric at the current step.
Greedy step: pick the element that maximizes/minimizes this criterion.
No backtracking: an accepted choice stays in the final solution.

When greediness gives a globally optimal answer

For locally optimal steps to add up to a globally optimal solution, a problem usually needs two properties:

Greedy-choice property: there exists an optimal solution that starts with some greedy step.
Optimal substructure: after the greedy step, the remainder of the problem is again optimal for the subproblem.

Correctness is often proved with an exchange argument: showing that any optimal answer can be "rebuilt" by replacing its first step with the greedy one, without worsening quality.

Where this works

Selecting non-overlapping intervals (maximum number of events): pick the activity with the minimum end time.
Minimum spanning tree (Kruskal/Prim): always take the smallest edge that does not form a cycle.
Optimal prefix coding (Huffman): always merge the two lightest nodes.
Shortest paths without negative edges (Dijkstra): pick the unvisited vertex with the minimum current distance.

Where greediness breaks

Coin change for arbitrary denominations: with coins [1, 3, 4] and sum 6, the greedy choice gives 4+1+1 (3 coins), the optimum is 3+3 (2 coins).
0/1 knapsack: choosing by maximum "value/weight" is not always optimal.
Weighted scheduling (weighted interval scheduling): dynamic programming is needed, greediness alone is not enough.

Interview reasoning template

Formulate the local criterion (what exactly counts as "best right now").
Show the greedy-choice property: an optimum exists that starts with this step.
Prove optimal substructure (usually an exchange argument or induction).
Give a counterexample for alternative criteria (why yours is the correct one).

Illustration: selecting non-overlapping activities (greediness works)

Criterion: always take the activity that finishes earliest among those compatible with what is already chosen.

function selectActivities(intervals) {
  // intervals: [{ start, end }]
  intervals.sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;
  for (const it of intervals) {
    if (it.start >= lastEnd) {
      result.push(it);
      lastEnd = it.end;
    }
  }
  return result;
}

// Example
const activities = [
  { start: 1, end: 4 },
  { start: 3, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 3, end: 9 },
  { start: 5, end: 9 },
  { start: 6, end: 10 },
  { start: 8, end: 11 },
  { start: 8, end: 12 },
  { start: 2, end: 14 },
  { start: 12, end: 16 }
];
console.log(selectActivities(activities));

Counterexample: coin change (greediness breaks)

For coins [1, 3, 4] and sum 6, greediness (taking the largest coin <= the remainder) gives a suboptimal answer.

function coinChangeGreedy(amount, coins) {
  coins = [...coins].sort((a, b) => b - a);
  const used = [];
  for (const c of coins) {
    while (amount >= c) {
      amount -= c;
      used.push(c);
    }
  }
  return amount === 0 ? used : null; // null if change is impossible
}

function coinChangeDP(amount, coins) {
  const dp = Array(amount + 1).fill(Infinity);
  const prev = Array(amount + 1).fill(-1);
  dp[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (a >= c && dp[a - c] + 1 < dp[a]) {
        dp[a] = dp[a - c] + 1;
        prev[a] = c;
      }
    }
  }
  if (!isFinite(dp[amount])) return null;
  const res = [];
  for (let a = amount; a > 0; a -= prev[a]) res.push(prev[a]);
  return res;
}

const coins = [1, 3, 4];
const amount = 6;
console.log('Greedy:', coinChangeGreedy(amount, coins)); // [4, 1, 1]
console.log('DP    :', coinChangeDP(amount, coins));     // [3, 3] (optimum)

Summary

A locally optimal choice is "the best step right now" by a given criterion. Greedy algorithms are fast and simple, but produce a correct globally optimal result only for problems with a suitable structure (the greedy-choice property and optimal substructure). Other problems need dynamic programming, exhaustive search, or another approach.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.