Greedy Algorithms Explained: Complete Beginner's Guide

A greedy algorithm builds a solution one step at a time, always picking the choice that looks best right now and never reconsidering earlier choices — like packing a suitcase by always grabbing the most useful remaining item. When the problem has the right structure, this short-sightedness produces the perfect answer; when it does not, it fails badly.

Greedy algorithms matter because they are often the simplest correct solution when they apply. Huffman coding compresses files greedily, Dijkstra's algorithm routes maps greedily, and Kruskal's algorithm lays out minimum-cost networks greedily. Knowing when greed works — and when it does not — is a core design skill.

Key Concepts

• Greedy choice: each step takes the locally optimal option — biggest coin, cheapest edge, earliest-finishing activity.
• No backtracking: a greedy choice is never undone — the source of both its speed and its risk.
• Greedy-choice property: a globally optimal solution can be built from locally optimal choices; only some problems have it.
• Optimal substructure: optimal solutions contain optimal solutions to subproblems — needed for greedy to work.
• Activity selection: "always pick the earliest-finishing activity" maximises the number of scheduled activities.
• Coin change: with canonical denominations like Indian rupees, repeatedly taking the largest fitting coin minimises coin count.
• Huffman coding: repeatedly merging the two least frequent symbols builds an optimal compression tree.

How It Works

1. Define the greedy choice: a local rule, e.g., "take the largest denomination not exceeding the remainder."
2. Check the property: argue (or test) that some optimal solution includes this first choice.
3. Reduce: after the choice, the rest is a smaller instance of the same problem.
4. Repeat: keep applying the rule — typically O(n log n) to sort plus O(n) to select.
5. Test counterexamples: deliberately try inputs designed to fool the rule before trusting it.

Worked Example

Make ₹93 with the fewest notes/coins from {100, 50, 20, 10, 5, 2, 1}. Largest ≤ 93 is 50 → remainder 43. Largest ≤ 43 is 20 → remainder 23. Largest ≤ 23 is 20 → remainder 3. Largest ≤ 3 is 2 → remainder 1. Largest ≤ 1 is 1 → remainder 0. Result: 50 + 20 + 20 + 2 + 1 = ₹93 in 5 notes/coins — optimal for this canonical system. Now watch greed fail with denominations {1, 3, 4}, target 6: greedy takes 4, remainder 2, then 1 + 1 → 3 coins (4+1+1), but optimal is 3 + 3 = 2 coins. The greedy-choice property fails here — a perfect warning to verify before trusting the shortcut.

Common Misconceptions

• "Greedy always gives the optimal answer." Wrong — the {1, 3, 4} coins prove it. Greed is correct only with the greedy-choice property.
• "Greedy is just faster dynamic programming." Wrong. DP explores many possibilities and remembers results; greedy commits to one path.
• "Dijkstra works with negative weights." Wrong. Dijkstra finalises nodes greedily, and a negative edge can later reveal a shorter path to a finalised node — negative weights need Bellman-Ford.

Real-World Applications

• Huffman coding: optimal compression in ZIP, JPEG, and MP3.
• Spanning trees: Kruskal's and Prim's design cheapest cable and road networks.
• Dijkstra's shortest path: GPS navigation on non-negative weights.
• Scheduling: activity selection for meeting rooms and classrooms.

Greedy algorithms are the art of being correctly short-sighted: pick the best-looking move now, never look back. Where the problem rewards that boldness, greed delivers optimal answers at unbeatable speed.