What Are Greedy Algorithms?
The Intuitive Idea
A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.
In plain English: At each step, pick the option that looks best right now. Don’t worry about whether this will lead to the best overall solution. Just greedily grab the best thing available and move on.
Real-Life Analogy: You walk into an ice cream shop. They have 20 flavors. You don’t have time to deliberate. You just pick the flavor that looks best to you right now. That’s a greedy choice. You might end up with a suboptimal experience (maybe the flavor you picked is too sweet), but you made the best choice at that moment.
Another Analogy: You’re climbing a mountain, and you’re shrouded in fog. You can’t see the peak. So you just always step in the direction that goes up from where you’re standing. That’s the greedy approach to mountain climbing—and it might get you stuck on a local maximum instead of the global peak. This is the classic problem with greedy algorithms: they can get stuck in local optima.
A Third Analogy: You’re playing a video game where you need to collect coins. You can only see a few feet ahead. You move toward the nearest coin you can see. That’s greedy. But maybe if you’d gone the other way, you’d have found a huge pile of coins. You’ll never know, because you were greedy.
The Formal Definition
Okay, enough analogies. Let’s get formal.
A greedy algorithm works in phases. At each phase:
- You have some set of choices.
- You make the choice that looks best right now (the “greedy choice”).
- You then solve the remaining subproblem.
The key assumption: Making the greedy choice at each step leads to a globally optimal solution.
This assumption is not always true. We’ll see examples where it fails.
When Does Greedy Work?
Here’s the million-dollar question: When can you actually use a greedy algorithm and trust that it’ll give you the optimal solution?
The answer: Only when the problem has two specific properties:
- Greedy choice property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
- Optimal substructure: An optimal solution to the problem contains optimal solutions to subproblems.
We’ll dive deep into these properties in the next section. But first, let me give you some examples of problems where greedy works and where it doesn’t.
Problems Where Greedy Works:
- Activity Selection: Given a set of activities with start and end times, select the maximum number of non-overlapping activities. Greedy choice: Always pick the activity that ends earliest.
- Fractional Knapsack: Given items with weights and values, and a weight capacity, maximize the total value. You can take fractions of items. Greedy choice: Always take as much as possible of the item with the highest value-to-weight ratio.
- Huffman Coding: Given a set of characters and their frequencies, build a binary tree for encoding that minimizes the total encoded length. Greedy choice: Always merge the two nodes with the lowest frequencies.
- Minimum Spanning Tree (Prim’s and Kruskal’s algorithms): Given a connected, undirected, weighted graph, find the minimum-weight tree that connects all vertices. Greedy choice: Always pick the minimum-weight edge that doesn’t create a cycle (Kruskal’s) or that connects a vertex in the MST to one outside it (Prim’s).
Problems Where Greedy Fails:
- 0/1 Knapsack: Like fractional knapsack, but you can’t take fractions of items. Greedy by value-to-weight ratio fails.
- Shortest Path in a Graph with Negative Weights (but no negative cycles): Dijkstra’s algorithm (greedy) fails; you need Bellman-Ford.
- Longest Path in a Graph: The greedy “always go to the farthest vertex” fails.
- Making Change with Arbitrary Coin Denominations: The greedy “always use the largest coin possible” fails for some coin systems (like if you have coins of 1, 3, and 4 cents).
Why Does Greedy Sometimes Work and Sometimes Fail?
This is the key question. Why does greedy work for activity selection but fail for 0/1 knapsack?
The answer lies in the structure of the problem.
In activity selection, making the greedy choice (pick the activity that ends earliest) doesn’t limit your future choices in a bad way. After picking the earliest-finishing activity, you still have the maximum possible time left for selecting other activities.
But in 0/1 knapsack, making the greedy choice (take the item with the highest value-to-weight ratio) can limit your future choices. Maybe taking that high-density item fills up your knapsack, preventing you from taking two medium-density items that would have given you more total value.
This is why understanding the problem structure is so important. You need to ask: Does making the greedy choice limit my future choices in a way that could lead to a suboptimal solution?
A Taxonomy of Greedy Algorithms
Not all greedy algorithms are the same. Let me give you a taxonomy:
- Pure Greedy: At each step, make the greedy choice and never look back. Examples: Activity selection, fractional knapsack.
- Greedy with Backtracking: Make the greedy choice, but if it leads to a dead end, backtrack and try something else. Examples: Some constraint satisfaction problems.
- Greedy with Heuristic: Use a heuristic to guide the greedy choice. Examples: A* search (which we covered in the Graph Algorithms article), where the heuristic guides the search.
- Greedy Approximation Algorithms: Greedy algorithms that don’t give the exact optimum but give a close approximation. Examples: The greedy algorithm for set cover (gives a log(n) approximation).
As a frontend developer, you’ll mostly encounter pure greedy algorithms. But it’s good to know that there are variants.
The Problem: You’re a cashier. A customer buys something for $6.37. They give you $10. You need to give them $3.63 in change. You have coins of denominations $1, 25¢, 10¢, 5¢, and 1¢. How do you minimize the number of coins you give?
The Greedy Algorithm:
- Always give the largest coin that doesn’t exceed the remaining amount.
- Repeat until the remaining amount is 0.
Example: $3.63
- Give a $1 coin. Remaining: $2.63
- Give another $1 coin. Remaining: $1.63
- Give another $1 coin. Remaining: $0.63
- Give a 25¢ coin. Remaining: $0.38
- Give a 25¢ coin. Remaining: $0.13
- Give a 10¢ coin. Remaining: $0.03
- Give three 1¢ coins. Remaining: $0.00
Total coins: 3 + 2 + 1 + 3 = 9 coins.
Does This Work?
For US coin denominations (1, 5, 10, 25, 100), yes! The greedy algorithm gives the optimal (minimum coin) solution.
But here’s the thing: this is not true for arbitrary coin denominations.
Counterexample: Suppose you have coins of denominations 1, 3, and 4. You need to make change for 6.
- Greedy: 4 + 1 + 1 = 6 (3 coins)
- Optimal: 3 + 3 = 6 (2 coins)
The greedy algorithm fails here because the locally optimal choice (take the 4) leads to a suboptimal global solution.
This is why understanding when greedy works is so important. Let’s formalize this.
/**
* Greedy Coin Change Algorithm
*
* @param {number} amount - The amount to make change for
* @param {Array<number>} denominations - Available coin denominations (sorted descending)
* @returns {Object} Object containing the coins used and their count
*
* Note: This only works optimally for "canonical" coin systems
* (like US coins). For arbitrary denominations, use dynamic programming.
*/
function greedyCoinChange(amount, denominations) {
// Sort denominations in descending order (greedy needs this)
const sortedDenoms = [...denominations].sort((a, b) => b - a);
const coinsUsed = [];
let remaining = amount;
for (let denom of sortedDenoms) {
while (remaining >= denom) {
coinsUsed.push(denom);
remaining -= denom;
}
}
return {
coinsUsed,
coinCount: coinsUsed.length,
remaining // Should be 0 if change can be made
};
}
// Example: US coins
const usCoins = [100, 25, 10, 5, 1]; // Denominations in cents
console.log('Making change for $3.63 (363 cents):');
const result1 = greedyCoinChange(363, usCoins);
console.log('Coins used:', result1.coinsUsed);
console.log('Coin count:', result1.coinCount);
// Output: Coins used: [100, 100, 100, 25, 25, 10, 1, 1, 1]
// Coin count: 9
// Counterexample: Non-canonical coin system
const weirdCoins = [4, 3, 1];
console.log('\nMaking change for 6 cents with denominations [4, 3, 1]:');
const result2 = greedyCoinChange(6, weirdCoins);
console.log('Greedy solution - Coins used:', result2.coinsUsed);
console.log('Greedy solution - Coin count:', result2.coinCount);
// Output: Coins used: [4, 1, 1]
// Coin count: 3
console.log('Optimal solution: [3, 3], coin count: 2');
console.log('Greedy fails here!');
Why Study Greedy Algorithms as a Frontend Developer?
Okay, cool. But why should you, a frontend developer, care about greedy algorithms?
1. Layout Algorithms in CSS: CSS Flexbox and Grid use greedy layout algorithms. Understanding how they work helps you debug layout issues.
2. Task Scheduling: If you’re building a task manager or a calendar app, scheduling tasks optimally is a greedy algorithm problem.
3. Performance Optimization: Greedy algorithms are often used in performance optimization. For example, “greedy” code splitting (split at the most heavily imported modules first) is a heuristic that often works well.
4. Data Compression: If you’re working with data compression (like compressing images or fonts), Huffman coding is a greedy algorithm that’s directly relevant.
5. Interval Scheduling: If you’re building a booking system or a calendar, selecting non-overlapping intervals is a greedy algorithm problem.
We’ll explore these frontend applications in detail later. But first, let’s understand the theory.
