Greedy Algorithms

Concept

A Greedy Algorithm is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit.

A Greedy algorithm never worries about the future. It never looks back at the past. It makes the locally optimal choice at that exact microsecond, with the hope that these local optimums will mathematically combine into a global optimum.

The Mental Model

Imagine you are standing at the top of a mountain, and you want to find the fastest way to the bottom.

• Dynamic Programming / Backtracking: You pull out a map, calculate every single possible trail, simulate every path, and confidently choose the absolute shortest route. (Slow but mathematically guaranteed to find the true best path).
• Greedy: You put the map away. You look at your feet. You take one step in the direction that goes down the steepest. You do this repeatedly until you hit the bottom. (Incredibly fast, but you might accidentally walk yourself into a valley or off a cliff!).

When does Greedy work?

A problem can only be solved with a Greedy algorithm if it satisfies two mathematical properties:

1. Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum. (Taking the steepest step actually leads to the lowest point).
2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to the sub-problems.

If these two properties are not perfectly true, a Greedy approach will confidently return the wrong answer.

Classic Example: Coin Change

Problem: You are a cashier. A customer needs 41 cents in change. You have coins: 25, 10, 5, 1. Give them the fewest number of coins possible.

The Greedy Approach:
Always take the largest coin possible!

1. Need 41. Take 25. (Remaining: 16)
2. Need 16. Take 10. (Remaining: 6)
3. Need 6. Take 5. (Remaining: 1)
4. Need 1. Take 1. (Remaining: 0)
   Answer: 4 coins.

Because US currency denominations are mathematically designed to be “Greedy-friendly”, the Greedy algorithm works flawlessly and extremely fast in $O(N)$ time.

When Greedy Fails:
What if the coin denominations were [25, 20, 5, 1]?
You need 40 cents in change.

• Greedy: Takes 25. Takes 5. Takes 5. Takes 5. (4 coins).
• Optimal: Takes 20. Takes 20. (2 coins).

The Greedy algorithm fails because taking the locally optimal 25 prevented it from seeing the globally optimal 20 + 20 combination. When Greedy fails, you are forced to use Dynamic Programming to simulate all combinations.

Interview Strategy

Greedy problems are notoriously difficult in interviews because there is no single “Greedy Template” you can memorize. Every single Greedy problem requires a unique, clever mathematical observation.

If you are stuck on an array problem, the most common trick to unlocking a Greedy solution is to Sort the array first.
By sorting the data, you often arrange the elements in a way that makes the “locally optimal choice” incredibly obvious (e.g., matching the smallest with the largest).

Interview Questions

Q: Dijkstra’s Shortest Path Algorithm, Prim’s Minimum Spanning Tree, and Kruskal’s Algorithm… are these Greedy algorithms?
A: Yes! All three are legendary examples of Greedy algorithms.

• Dijkstra always pops the single absolute shortest path from the Priority Queue and blindly follows it.
• Prim’s always grabs the single cheapest edge connected to the tree.
• Kruskal’s sorts the edges and always grabs the absolute cheapest edge in the world.
  They never simulate future paths. They make locally optimal choices that mathematically guarantee the global optimum.