Greedy Algorithms

A greedy algorithm is a problem-solving approach that makes the locally optimal choice at each step, aiming to find a global optimum. It's like always taking the biggest cookie from the jar — you grab what looks best right now without considering what's left for later.

What Is a Greedy Algorithm?#

Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most immediate benefit. The key insight is that sometimes making the best local choice at each step leads to the best overall solution.

Real-World Analogies#

• Making Change: A cashier gives you change using the fewest coins by always picking the largest coin that doesn't exceed the remaining amount
• GPS Navigation: At each intersection, take the road that gets you closest to your destination
• Huffman Coding: Build an optimal prefix code by always combining the two least frequent symbols
• Packing Divisible Cargo: When goods can be split (like grain or liquid), always load whatever has the best value-per-kilogram ratio first — taking a partial amount of the last item if space runs out

Key Characteristics#

When Does Greedy Work?#

Greedy algorithms don't always produce optimal solutions. They work only when the problem has two key properties:

1. Greedy Choice Property#

Making the locally optimal choice at each step leads to a globally optimal solution. The standard way to prove this is the exchange argument: take any optimal solution, and show that you can swap in the greedy choice (replacing whatever different choice it made first) without making the result worse. If such a swap is always safe, the greedy choice is proven sound.

2. Optimal Substructure#

After making a greedy choice, the remaining problem is a smaller instance of the same problem, and the optimal solution to the whole problem is built on the optimal solution to that smaller subproblem. In activity selection, for example, once you commit to the first activity, the remaining problem is identical in structure — just with a smaller pool of candidates and an updated start constraint.

Greedy vs Other Approaches#

Activity Selection Problem#

Problem: Given a set of activities with start and end times, select the maximum number of activities that don't overlap. Think of it as scheduling the most meetings in a conference room.

Why Greedy Works#

The key insight is to always pick the activity that ends earliest. This leaves the most time available for subsequent activities. The exchange argument confirms this is safe: if an optimal solution starts with a different (later-ending) activity, we can swap in the earliest-ending one instead. The count stays the same or improves, so the greedy choice never hurts.

Fractional Knapsack#

Problem: You're a thief with a knapsack of limited capacity. Each item has a weight and value. You can take fractions of items. Maximize the total value you can carry.

Why Greedy Works#

Since we can take fractions, we should always take items with the highest value-to-weight ratio first. This maximizes value extracted per unit of capacity used. Crucially, the ability to take partial amounts eliminates the risk of committing to a "bad" early choice — whatever fraction we take of a high-ratio item will always yield at least as much value per kilogram as any lower-ratio item. This property makes the greedy approach provably optimal for the fractional version, even though it fails for the 0-1 variant (see the "When Greedy Fails" section).

Coin Change (Greedy Approach)#

Problem: Given coin denominations and a target amount, find the minimum number of coins needed. The greedy approach always picks the largest denomination that doesn't exceed the remaining amount.

When Greedy Works#

For many standard coin systems (like US coins: 1¢, 5¢, 10¢, 25¢), the greedy approach is optimal. These are called canonical coin systems — the denominations are designed so that taking the largest possible coin at each step always produces the minimum total number of coins.

When Greedy Fails#

For non-canonical coin systems — those not designed with the greedy property in mind — always picking the largest denomination can result in using more coins than necessary. The diagram below shows a concrete example: with coins [1, 3, 4], greedy picks 4 first and gets stuck using 3 coins total, while the optimal solution uses just 2 coins of value 3.

Jump Game#

Problem: Given an array where each element represents the maximum jump length from that position, determine if you can reach the last index starting from the first index.

Why Greedy Works#

At each position, we track the farthest index we can reach. We don't need to know the exact path taken to get to the current position — only whether it's reachable at all. If farthest ever falls below the current index i, we know i is unreachable and the answer is false. Conversely, as long as we stay within farthest, every position between 0 and farthest is reachable, so updating farthest = max(farthest, i + nums[i]) at each step correctly tracks the full reachable range in a single pass.

Common Greedy Patterns#

Pattern 1: Interval Scheduling#

Sort intervals by end time, then greedily select non-overlapping ones. Used in: meeting rooms, task scheduling, resource allocation.

Pattern 2: Fractional Selection#

Sort items by a ratio (value/cost), greedily take the best until a constraint is met. Used in: knapsack, task assignment, resource optimization.

When Greedy Fails#

Greedy algorithms fail when the greedy choice property doesn't hold — that is, when making the locally best decision at each step doesn't guarantee the best overall outcome. This typically happens when committing to an early choice closes off combinations that would have been more valuable later. The 0-1 Knapsack problem is a classic illustration.

Classic Example: 0-1 Knapsack#

The 0-1 Knapsack problem asks: given a knapsack with a fixed weight capacity and a set of items each with a weight and value, which items should you pack to maximize total value? The "0-1" means each item is either taken in full (1) or left behind (0) — you cannot split an item.

Formally:

• You have n items, each with weight w[i] and value v[i]
• Your knapsack holds at most W total weight
• Find the subset of items with maximum total value without exceeding W

Why greedy fails here: Unlike fractional knapsack, in 0-1 knapsack you must take whole items or nothing. The greedy approach of selecting by value-to-weight ratio fails here.

When to Use Dynamic Programming Instead#

Reviewing AI-Generated Code#

Understanding greedy algorithms helps you evaluate AI-generated solutions.

What to Verify#

Common AI Pitfalls#

Questions to Ask AI#

When AI generates greedy code, verify:

• "Why does greedy give the optimal solution here?"
• "What's the sorting criterion and why?"
• "Can you give a counter-example where greedy fails?"
• "Should this use DP instead of greedy?"

Summary#

Key Takeaways#

1. Greedy means local optimal choices — at each step, pick what looks best without reconsidering past decisions
2. Fast but not always correct — verify the greedy choice property holds before using it; a single counter-example is enough to rule greedy out
3. Prove correctness with the exchange argument — show that any optimal solution can be transformed to include the greedy choice without making it worse
4. Know the two core patterns — interval scheduling (sort by end time) and ratio-based selection (fractional knapsack) cover most greedy problems
5. Greedy vs. DP — if committing to an early choice affects which options remain available, reach for dynamic programming; greedy is only safe when the locally best choice is always globally harmless