What is "optimal substructure" in a greedy algorithm?

AlgorithmsJunior~4 min read

Short answer

Optimal substructure is a property of a problem in which an optimal solution can be assembled from optimal solutions of its subproblems. For a greedy algorithm this is not enough: besides optimal substructure, the "greedy-choice property" is also needed - the ability to make a locally optimal step that provably leads to the global optimum.

Detailed explanation

Definition

Optimal substructure is a property of optimization problems: if the original problem is split into subproblems, any part of the optimal solution that pertains to a subproblem is itself an optimal solution to that subproblem. Hence, combining the optimal solutions of the subproblems forms an optimal solution to the original problem.

Connection to greedy algorithms

Greedy algorithms make the locally best choice at each step and never return to it. For this approach to work, the following are required:

Optimal substructure: after the greedy step, the remaining part of the problem must be of the same nature, and the optimal solution of the original problem must include the optimal solution of the remaining subproblem.
Greedy-choice property: there exists an optimal solution in which the first step coincides with what the greedy heuristic does.
Both dynamic programming (DP) and greedy algorithms require optimal substructure.
Greedy additionally needs the greedy-choice property; if it is absent, DP or exhaustive search is applied.
In DP we enumerate a set of sub-solutions with memoization; in greedy we make one "irrevocable" choice and solve a smaller subproblem.

How to recognize optimal substructure

Describe the subproblem that remains after making one choice (for example, after choosing an interval, a vertex, an edge, etc.).
Assume the existence of an optimal solution O of the original problem.
Show that the part of O corresponding to the subproblem must be optimal for that subproblem; otherwise it could be replaced with a better solution, improving O (a contradiction).
Check the greedy-choice property: prove that there exists an optimal solution starting with the greedy step; after that, continue recursively by optimal substructure.

Classic examples

Interval selection (activity selection) by earliest finish: after choosing the interval that ends earliest of all, the same problem remains on the remaining compatible intervals; its optimal solution complements the overall optimum.
Dijkstra's algorithm: after fixing the vertex with the minimum current distance, the subproblem is to find shortest paths in the graph with the already-fixed set; optimal paths continue optimally.
Huffman codes: merging the two smallest frequencies creates a smaller subproblem; the optimal tree structure is preserved.
Fractional knapsack: after choosing the item with the maximum value per unit weight, the same type of problem remains on the remaining capacity; the optimal fractions add up to the overall optimum.

Counterexample: 0/1 knapsack

The 0/1 knapsack has optimal substructure (DP works), but a greedy choice by value/weight can lead to a non-optimum. So optimal substructure alone is not enough for a greedy algorithm - the "safety" of the greedy step must also be checked.

Mini-example: interval selection

Problem: select the maximum number of non-overlapping intervals. Greedy step: always take the interval that ends earliest of all. Optimal substructure: after choosing such an interval, a subproblem remains on the intervals starting no earlier than its end; the subproblem's optimal solution together with the chosen interval forms the optimum for the whole problem.

Proof sketch: let O be an optimal set. If the first interval in O ends later than our greedy one, replace it with the greedy one - the set's size does not decrease, and no overlaps arise. Then the remaining part is optimal for the subproblem (otherwise O could be improved), which is exactly optimal substructure.

// Selecting the maximum number of non-overlapping intervals (greedy algorithm)
// intervals: [{ start: number, end: number }]
function selectMaxNonOverlappingIntervals(intervals) {
  const sorted = [...intervals].sort((a, b) => a.end - b.end);
  const result = [];
  let lastEnd = -Infinity;

  for (const it of sorted) {
    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(selectMaxNonOverlappingIntervals(intervals));
// Result: an optimal-size set of intervals (for example, [{ start: 1, end: 2 }, { start: 2, end: 5 }])

Interview checklist

Give the definition: an optimal solution is composed of optimal solutions of subproblems.
Distinguish "optimal substructure" from the "greedy-choice property."
Give an example where both properties hold (intervals, Dijkstra, Huffman, fractional knapsack).
Give a counterexample (0/1 knapsack): substructure exists, greedy choice does not work.
Briefly describe the proof by replacing a suboptimal fragment with an optimal one (proof by contradiction).
State the consequence: if the greedy choice is safe, use a greedy algorithm; otherwise, use DP.

Summary

Optimal substructure is a necessary condition for greedy algorithms (and for DP): the optimum is built from the optima of subproblems. But for a greedy method to be correct, this alone is not enough: it must also be proved that the first locally best step belongs to some globally optimal solution.

Short Answer

Interview ready

Premium

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