Suggest an edit

Improve this article

Refine the answer for “What does a locally optimal choice mean in a greedy algorithm?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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:

1. Greedy-choice property: there exists an optimal solution that starts with some greedy step.
2. 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

1. Formulate the local criterion (what exactly counts as "best right now").
2. Show the greedy-choice property: an optimum exists that starts with this step.
3. Prove optimal substructure (usually an exchange argument or induction).
4. 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.

```js
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.

```js
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
}

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.

Markdown · drag & drop images · ⌘B / ⌘I shortcuts776 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.