What does a globally optimal solution mean in a greedy algorithm?

AlgorithmsJunior~2 min read

Short answer

A globally optimal solution is a solution that minimizes or maximizes the objective function among all feasible solutions to the problem. In the context of greedy algorithms, this means that a sequence of locally best choices by a given criterion leads to the best possible final solution. This holds only for problems that have optimal substructure and the greedy-choice property (usually proved with an "exchange argument").

Detailed explanation

Definitions

Locally optimal choice: an action that looks best "here and now" by some greedy criterion, without looking far ahead.
Globally optimal solution: a solution than which none is better among all feasible solutions (by the objective function). For minimization problems, it has the lowest cost; for maximization problems, the highest gain.
Greedy algorithm: builds a solution step by step, each time making a locally optimal choice, hoping to obtain the global optimum.

When a greedy algorithm guarantees the global optimum

Optimal substructure: the problem's optimal solution contains optimal solutions of its subproblems.
Greedy-choice property: there exists an optimal solution that starts with the locally best step by the chosen criterion.

Correctness is most often proved with an "exchange argument": showing that any optimal answer can be transformed by "exchanges" into one where the first step coincides with the greedy one, without worsening quality. Repeating the steps yields the entire greedy answer, equal to the global optimum.

Typical problems where greedy gives the global optimum

Selecting the maximum number of non-overlapping intervals (activities) - sort by end time.
Minimum spanning tree (Kruskal/Prim) - the "cut property" guarantees global minimality.
Optimal prefix coding (Huffman) - the smallest frequencies are merged first.
Coin change in "canonical" denomination systems (for example, 1, 5, 10, 25).

Example (greedy is globally optimal): selecting non-overlapping intervals

Greedy choice: always take the interval with the smallest end time that does not overlap with those already chosen.

function selectActivities(intervals) {
  // intervals: [{ start: number, end: number }]
  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 intervals = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 4, end: 7 },
  { start: 1, end: 2 }
];
console.log(selectActivities(intervals));
// Greedy gives the global maximum number of selected intervals

Counterexample (greedy does not give the global optimum): coin change

Denominations 1, 3, 4; sum 6. Greedy by largest coins picks 4 + 1 + 1 (3 coins), but the globally optimal is 3 + 3 (2 coins).

function greedyCoins(coins, amount) {
  coins = [...coins].sort((a, b) => b - a);
  const taken = [];
  for (const c of coins) {
    while (amount >= c) {
      amount -= c;
      taken.push(c);
    }
  }
  return { coins: taken, count: taken.length, remainder: amount };
}

console.log(greedyCoins([1, 3, 4], 6));
// { coins: [4, 1, 1], count: 3, remainder: 0 }  <-- not the global optimum

How to still get the global optimum when greedy breaks (DP)

Dynamic programming guarantees the global optimum by enumerating subproblems and remembering the best results.

function minCoinsDP(coins, amount) {
  const INF = amount + 1;
  const dp = new Array(amount + 1).fill(INF);
  const prev = new 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 (dp[amount] === INF) return { count: -1, coins: [] };
  const out = [];
  let a = amount;
  while (a > 0) {
    out.push(prev[a]);
    a -= prev[a];
  }
  return { count: out.length, coins: out };
}

console.log(minCoinsDP([1, 3, 4], 6));
// { count: 2, coins: [3, 3] }  <-- globally optimal

Practical interview tips

First, formulate the optimality criterion and the feasible set of solutions.
Check the optimal substructure and try to formulate the greedy-choice criterion.
Try the "exchange argument": can any optimal structure be transformed so its first step matches your greedy one?
If you quickly find a counterexample, greedy probably does not guarantee the global optimum; consider DP/search.

Summary

A globally optimal solution is the best among all feasible ones. Greedy algorithms reach it only on problems with optimal substructure and the greedy-choice property, which is usually proved with an exchange argument. Otherwise, dynamic programming or other methods are used.

Short Answer

Interview ready

Premium

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