Greedy Algorithms

Overview

Greedy algorithms solve optimization problems by making the locally optimal choice at each step with the hope of finding a global optimum. The key principle is: make the best decision you can right now, without worrying about future consequences.

Greedy algorithms don’t always produce optimal solutions, but when they do, they’re often the most efficient approach.

Core Principle

At each decision point, a greedy algorithm:

Makes the choice that looks best at the moment
Never reconsiders that choice
Hopes that these local choices lead to a global optimum

function greedyApproach(problem) {
  let solution = [];
  
  while (!problem.isSolved()) {
    // Make the best choice right now
    const bestChoice = findLocalOptimum(problem);
    solution.push(bestChoice);
    problem.update(bestChoice);
  }
  
  return solution;
}

Problem: Minimum Coin Change

Problem Description

Given a value v, if we want to make change for v using an infinite supply of coins with denominations [c1, c2, c3, ..., cn], what is the minimum number of coins needed? If it’s not possible to make change, return -1.Example:

Value: 186
Coins: [1, 5, 10, 25]
Output: 9 coins
Solution: 7×25 + 1×10 + 1×1 = 175 + 10 + 1 = 186

Greedy Strategy

The greedy approach for coin change:

Sort coins in descending order
Use as many of the largest coin as possible
Move to the next smaller coin
Repeat until we make exact change

This greedy approach only works for certain coin systems (like US coins). For arbitrary coin denominations, use dynamic programming instead.

Implementation

function minCoinChange(value: number, coins: number[]): {
  count: number;
  breakdown: Record<number, number>;
} {
  const result: Record<number, number> = {};
  let amount = value;
  let count = 0;
  
  // Start with largest coin
  for (let i = coins.length - 1; i >= 0; i--) {
    if (coins[i] <= amount) {
      // Use as many of this coin as possible
      const coinCount = Math.floor(amount / coins[i]);
      
      result[coins[i]] = result[coins[i]]
        ? result[coins[i]] + coinCount
        : coinCount;
      
      count += coinCount;
      amount = amount % coins[i];
    }
  }
  
  // Check if we made exact change
  if (amount !== 0) {
    return { count: -1, breakdown: {} };
  }
  
  return { count, breakdown: result };
}

// Usage
const value = 186;
const coins = [1, 5, 10, 25];
const result = minCoinChange(value, coins);

console.log(`Minimum coins: ${result.count}`);
// Output: Minimum coins: 9

console.log('Breakdown:', result.breakdown);
// Output: Breakdown: { '1': 1, '10': 1, '25': 7 }

Step-by-Step Walkthrough

For value = 186 and coins = [1, 5, 10, 25]:

Step 1: Use 25 cent coins
  186 ÷ 25 = 7 remainder 11
  Use 7 quarters, remaining: 11

Step 2: Use 10 cent coins
  11 ÷ 10 = 1 remainder 1
  Use 1 dime, remaining: 1

Step 3: Use 5 cent coins
  1 ÷ 5 = 0 remainder 1
  Use 0 nickels, remaining: 1

Step 4: Use 1 cent coins
  1 ÷ 1 = 1 remainder 0
  Use 1 penny, remaining: 0

Total: 7 + 1 + 0 + 1 = 9 coins

Complexity Analysis

Time Complexity: O(n)
- Where n is the number of coin denominations
- We iterate through each coin type once
Space Complexity: O(n)
- To store the breakdown of coins used

When Greedy Fails

Greedy doesn’t always give optimal results. Consider:

// Coins: [1, 3, 4]
// Value: 6

// Greedy approach:
// 4 + 1 + 1 = 6 (3 coins)

// Optimal solution:
// 3 + 3 = 6 (2 coins)

For arbitrary coin systems, use dynamic programming instead.

When to Use Greedy Algorithms

Use When

Problem has greedy choice property
Optimal substructure exists
Local optimum leads to global optimum
Proof of correctness is available
Need fast, simple solution

Avoid When

Local choices don’t guarantee global optimum
Need to explore all possibilities
Problem requires backtracking
Counterexamples to greedy exist
DP is more appropriate

Greedy Choice Property

A problem has the greedy choice property if:

Local Optimum

Making the locally optimal choice at each step

No Reconsideration

Never needing to reconsider previous choices

Global Optimum

These local choices lead to a globally optimal solution

Classic Greedy Algorithm Examples

Activity Selection

Problem: Select maximum number of non-overlapping activities.Greedy Strategy: Always pick the activity that finishes earliest.

function activitySelection(activities: Array<[number, number]>) {
  // Sort by finish time
  activities.sort((a, b) => a[1] - b[1]);
  
  const selected = [activities[0]];
  let lastFinish = activities[0][1];
  
  for (let i = 1; i < activities.length; i++) {
    if (activities[i][0] >= lastFinish) {
      selected.push(activities[i]);
      lastFinish = activities[i][1];
    }
  }
  
  return selected;
}

Huffman Coding

Problem: Create optimal prefix-free binary codes for data compression.Greedy Strategy: Always combine the two nodes with smallest frequencies.

class HuffmanNode {
  constructor(
    public freq: number,
    public char?: string,
    public left?: HuffmanNode,
    public right?: HuffmanNode
  ) {}
}

function huffmanCoding(frequencies: Map<string, number>) {
  const heap = new MinHeap<HuffmanNode>(
    (a, b) => a.freq - b.freq
  );
  
  // Add all characters to heap
  for (const [char, freq] of frequencies) {
    heap.insert(new HuffmanNode(freq, char));
  }
  
  // Build tree
  while (heap.size() > 1) {
    const left = heap.extractMin();
    const right = heap.extractMin();
    const parent = new HuffmanNode(
      left.freq + right.freq,
      undefined,
      left,
      right
    );
    heap.insert(parent);
  }
  
  return heap.extractMin();
}

Dijkstra's Shortest Path

Problem: Find shortest path from source to all vertices.Greedy Strategy: Always expand the vertex with smallest distance from source.

function dijkstra(graph: number[][], source: number) {
  const n = graph.length;
  const dist = new Array(n).fill(Infinity);
  const visited = new Array(n).fill(false);
  
  dist[source] = 0;
  
  for (let i = 0; i < n - 1; i++) {
    // Find vertex with minimum distance
    let u = -1;
    for (let v = 0; v < n; v++) {
      if (!visited[v] && (u === -1 || dist[v] < dist[u])) {
        u = v;
      }
    }
    
    visited[u] = true;
    
    // Update distances
    for (let v = 0; v < n; v++) {
      if (graph[u][v] && !visited[v]) {
        dist[v] = Math.min(
          dist[v],
          dist[u] + graph[u][v]
        );
      }
    }
  }
  
  return dist;
}

Fractional Knapsack

Problem: Maximize value in knapsack when items can be divided.Greedy Strategy: Sort by value-to-weight ratio, take highest ratio first.

interface Item {
  value: number;
  weight: number;
}

function fractionalKnapsack(
  items: Item[],
  capacity: number
): number {
  // Sort by value/weight ratio (descending)
  items.sort((a, b) => 
    (b.value / b.weight) - (a.value / a.weight)
  );
  
  let totalValue = 0;
  let remainingCapacity = capacity;
  
  for (const item of items) {
    if (remainingCapacity >= item.weight) {
      // Take whole item
      totalValue += item.value;
      remainingCapacity -= item.weight;
    } else {
      // Take fraction of item
      totalValue += 
        (item.value / item.weight) * remainingCapacity;
      break;
    }
  }
  
  return totalValue;
}

Proving Greedy Correctness

To prove a greedy algorithm is correct, typically use one of:

Greedy Stays Ahead
Exchange Argument

Show that after each step, the greedy solution is at least as good as any other solution.

Prove: greedy_solution[i] ≥ optimal_solution[i]
for all steps i

Show that any optimal solution can be transformed into the greedy solution without making it worse.

Start with any optimal solution
Exchange one element with greedy choice
Show the solution is still optimal
Repeat until solution matches greedy

Greedy vs Dynamic Programming

Aspect	Greedy	Dynamic Programming
Choice	Make local optimum choice	Consider all choices
Subproblems	Independent	Overlapping
Backtracking	Never	Sometimes needed
Correctness	Not always optimal	Always optimal (if applicable)
Efficiency	Usually faster	More computation
Examples	Huffman coding, Dijkstra	Knapsack, LCS

Quick Test: If you can find a counterexample where greedy fails, you need dynamic programming instead.

Common Greedy Patterns

Sorting-Based

Sort items by some criterion, then process in orderExamples: Activity selection, Fractional knapsack

Priority Queue

Always process the “best” element nextExamples: Dijkstra, Huffman coding, Prim’s MST

Earliest Deadline First

Process items with earliest deadlines firstExamples: Job scheduling, Meeting rooms

Largest/Smallest First

Process extremes firstExamples: Minimize waiting time, Load balancing

Tips and Best Practices

Verify Correctness: Always check if greedy actually produces optimal results. Try to find counterexamples.

Sort First: Many greedy algorithms start by sorting the input by some criterion.

Use Priority Queue: When you need to repeatedly pick the “best” element, use a heap/priority queue.

Prove or Test: Either prove the greedy choice property holds, or extensively test your solution.

Just because a greedy approach is simple doesn’t mean it’s correct. Always validate with edge cases and counterexamples.

Debugging Greedy Algorithms

Check Greedy Choice

Is your greedy criterion actually optimal? Try small examples.

Test Edge Cases

Empty input, single element, all same values, extreme values

Compare with Brute Force

For small inputs, compare greedy result with exhaustive search

Look for Counterexamples

Can you find any case where greedy doesn’t give the optimal answer?

Dynamic Programming

When greedy doesn’t work

Divide and Conquer

For recursive subproblems

Backtracking

When you need to explore all options

Get Started

Data Structures

Algorithms

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Design Techniques

Overview

Core Principle

Problem: Minimum Coin Change

When to Use Greedy Algorithms

Use When

Avoid When

Greedy Choice Property

Classic Greedy Algorithm Examples

Proving Greedy Correctness

Greedy vs Dynamic Programming

Common Greedy Patterns

Sorting-Based

Priority Queue

Earliest Deadline First

Largest/Smallest First

Tips and Best Practices

Debugging Greedy Algorithms

Dynamic Programming

Divide and Conquer

Backtracking

Build docs developers (and LLMs) love

Get Started

Data Structures

Algorithms

Sorting Algorithms

Searching Algorithms

Graph Algorithms

Design Techniques

​Overview

​Core Principle

​Problem: Minimum Coin Change

​When to Use Greedy Algorithms

Use When

Avoid When

​Greedy Choice Property

​Classic Greedy Algorithm Examples

​Proving Greedy Correctness

​Greedy vs Dynamic Programming

​Common Greedy Patterns

Sorting-Based

Priority Queue

Earliest Deadline First

Largest/Smallest First

​Tips and Best Practices

​Debugging Greedy Algorithms

​Related Topics

Dynamic Programming

Divide and Conquer

Backtracking

Build docs developers (and LLMs) love

Overview

Core Principle

Problem: Minimum Coin Change

When to Use Greedy Algorithms

Greedy Choice Property

Classic Greedy Algorithm Examples

Proving Greedy Correctness

Greedy vs Dynamic Programming

Common Greedy Patterns

Tips and Best Practices

Debugging Greedy Algorithms

Related Topics