Overview

A Greedy Algorithm chooses the option that appears best at the current step and commits to it. This can avoid exploring an enormous number of possible solutions, producing simple and fast algorithms. However, a greedy strategy is correct only for problems whose structure guarantees that local choices lead to a global optimum.

Key concepts

• Choose the best available option now
• Add that choice to the solution
• Do not revisit earlier decisions
• Repeat until the solution is complete

What is a Greedy Algorithm?

Imagine choosing a road at every intersection by taking the route that currently looks shortest, without going back to reconsider. That immediate, irreversible decision captures the central greedy idea.

Why do we need Greedy Algorithms?

Some problems contain too many possible solutions to check individually. A valid greedy rule reduces this work by making one strong local choice at a time, often producing a much faster solution.

How does a Greedy Algorithm work?

• Start with an empty solution
• Examine the available choices
• Select the best valid choice at that moment
• Add it to the solution
• Repeat without undoing previous choices

Example: choosing currency notes

To make ₹880 using common Indian note values, repeatedly choose the largest note that does not exceed the remaining amount.

const notes = [500, 200, 100, 50, 20, 10];
let amount = 880;
const selected = [];

for (const note of notes) {
  while (amount >= note) {
    selected.push(note);
    amount -= note;
  }
}

console.log(selected);
// [500, 200, 100, 50, 20, 10]

This strategy works for the denominations in the example, but largest-first change is not optimal for every possible currency system. Greedy algorithms always require a correctness argument for the specific problem.

When does a Greedy Algorithm work?

Greedy Choice Property

There must be an optimal solution that begins with the locally best valid choice. This property justifies committing to that choice.

Optimal Substructure

After making the greedy choice, the remaining problem must have an optimal solution that combines with the choice to form an optimal overall solution.

If either property is missing, a greedy approach may return a valid but suboptimal answer.

Proving a Greedy strategy

• Exchange argument: show that an optimal solution can replace its first choice with the greedy choice without becoming worse
• Stays-ahead argument: show that the greedy partial solution is at least as good as any alternative after every step
• Structural proof: use the problem's mathematical properties to justify each local choice

Common Greedy problems

• Activity Selection
• Fractional Knapsack
• Huffman Coding
• Prim's Minimum Spanning Tree
• Kruskal's Minimum Spanning Tree
• Dijkstra's shortest paths with non-negative weights
• Job Scheduling

Time complexity

Many greedy algorithms sort candidates or maintain them in a priority queue, which is why O(n log n) appears frequently.

Greedy vs Dynamic Programming

Advantages of Greedy Algorithms

• Often easy to understand
• Usually simple to implement
• Can be faster than exhaustive or state-based methods
• Often uses relatively little additional memory
• Works efficiently when the greedy rule is provably valid

Limitations of Greedy Algorithms

• Does not always find the global optimum
• Committed choices cannot be undone
• Requires problem-specific correctness properties
• A plausible local rule can still produce the wrong result

Real-life applications

• GPS routing
• Network routing
• Data compression
• Task scheduling
• Project planning
• Resource allocation
• Traffic management

Tips for beginners

• State exactly what the local best choice means
• Test the rule against counterexamples
• Do not assume a greedy solution is correct because it feels intuitive
• Compare greedy and dynamic-programming solutions
• Practice classic problems and study their proofs

Key takeaways

• Greedy algorithms make irreversible local choices
• They can be simple, fast, and memory-efficient
• Correctness requires a greedy-choice property and optimal substructure
• Sorting often leads to O(n log n) complexity
• Greedy methods support scheduling, compression, shortest paths, and spanning trees
• When greedy fails, dynamic programming or backtracking may be appropriate