What is a greedy algorithm?

AlgorithmsJunior~3 min read

Short answer

A greedy algorithm is an approach that makes the locally best (most advantageous) choice at each step, without reconsidering decisions already made, hoping that the sequence of such choices leads to a globally optimal solution.

Detailed breakdown

Definition and intuition

Greedy algorithms build a solution step by step, each time choosing the option that looks best "here and now" by some criterion (a greedy heuristic). Key feature: decisions are irrevocable - once an element is chosen, it is never reconsidered.

Key idea

Local optimum: pick the best next step by the metric.
Irrevocability: decisions are locked in and never rolled back.
Proof: usually via an exchange argument or induction.

When greediness gives the optimum

There is optimal substructure: the problem's optimum is built from the optima of subproblems.
The greedy-choice property holds: there exists an optimal solution that starts with a greedy step.
Classic examples:
- Selecting non-overlapping intervals (activity selection) - sort by earliest end time.
- Minimum spanning tree: Kruskal/Prim.
- Shortest paths: Dijkstra with non-negative weights.
- Huffman coding.
- Coin change with canonical denomination systems (e.g., 1, 2, 5, 10, ...).

When greediness does not work

0/1 knapsack: a greedy choice by value/weight does not guarantee the optimum.
Coin change for arbitrary denominations, e.g. [1, 3, 4] and sum 6: greedy gives 4+1+1 (3 coins), the optimum is 3+3 (2 coins).
Shortest paths with negative edges - Bellman-Ford is needed.
Weighted interval scheduling - dynamic programming is required.

Template for designing a greedy solution

Formulate the greedy-choice metric (what "most advantageous" means).
Sort the data or prepare a structure for quickly picking the best candidate.
Iterate, each time making the greedy choice and locking it in.
Prove correctness: an exchange argument or induction plus the optimal-substructure property.
Estimate complexity: usually O(n log n) due to sorting or priority-queue work.

Example 1: Selecting non-overlapping intervals

Problem: choose the maximum number of non-overlapping intervals. Greedy heuristic: always take the interval with the earliest end time.

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

// Example
const intervals = [
  { start: 1, end: 3 },
  { start: 2, end: 5 },
  { start: 0, end: 6 },
  { start: 5, end: 7 },
  { start: 8, end: 9 },
  { start: 5, end: 9 }
];
console.log(selectActivities(intervals));
// Complexity: O(n log n) due to sorting; proof via an exchange argument.

Example 2: Coin change (canonical system)

Greedy heuristic: always take the largest possible denomination. Correct for canonical systems (e.g., 1, 2, 5, 10).

def greedy_change(amount, coins):
    coins = sorted(coins, reverse=True)
    result = []
    for c in coins:
        cnt = amount // c
        if cnt > 0:
            result.append((c, cnt))
            amount -= cnt * c
    return result

# Example
print(greedy_change(28, [1, 2, 5, 10]))
# Output: [(10, 2), (5, 1), (2, 1), (1, 1)]
# Note: for arbitrary denominations the greedy approach can be suboptimal.

Correctness proof (sketch): exchange argument

Idea: compare the greedy solution G with an optimal one O. We show that O can be transformed step by step into a solution that starts with the greedy choice, without worsening its quality. Repeating the transformation yields a solution equal to G, hence G is optimal. For example, in the interval problem, any optimal set can be rearranged so that its first interval ends no later than the greedy one, without reducing the set's size.

Strengths and weaknesses

Pros: simple to implement, fast (often O(n log n)), low memory usage.
Cons: does not always guarantee the optimum; a proof or counterexample matters.

Quick interview cheat sheet

State the greedy criterion and explain why it is reasonable.
Name the cases where it applies (intervals, MST, Dijkstra >= 0, Huffman).
Give a counterexample where greediness breaks (0/1 knapsack, coins [1,3,4]).
Briefly describe the proof via the exchange argument.

Short Answer

Interview ready

Premium

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