aloalgo.comGreedy Algorithms
A greedy algorithm builds a solution piece by piece, always choosing the option that looks best at the moment. It never reconsiders previous choices, hoping that local optimal choices lead to a global optimum.How Greedy Works
The greedy approach follows a simple pattern:- Start with an empty solution
- At each step, add the best available option
- Repeat until the solution is complete
Simple Example: Making Change
Given coin denominations, find the minimum coins to make a target amount. With standard US coins, greedy works perfectly.Why Greedy is Powerful
- Speed: Usually O(n) or O(n log n) - much faster than brute force or DP.
- Simplicity: Easy to implement once you identify the greedy choice.
- Space efficient: Often O(1) extra space since we don't store subproblems.
Greedy vs Dynamic Programming
Both solve optimization problems, but they differ in approach:Common Greedy Problem Types
- Interval scheduling: Select maximum non-overlapping intervals.
- Activity selection: Choose activities to maximize participation.
- Huffman coding: Build optimal prefix-free codes.
- Minimum spanning tree: Connect all nodes with minimum total edge weight.
- Fractional knapsack: Maximize value when items can be split.
The Greedy Mindset
When facing a problem, ask yourself:- What's the "best" choice at each step? (biggest, smallest, earliest ending, etc.)
- Does making this choice ever hurt future choices? If no, greedy likely works.
- Can I find a counterexample? Try small cases where greedy might fail.
Interview Tips
- Mention the strategy: "I'll try a greedy approach here because..."
- Justify your choice: Explain why picking locally optimal leads to globally optimal.
- Test with examples: Verify greedy works on the given examples and edge cases.
- Know when to pivot: If you find a counterexample, acknowledge it and switch to DP.
Was this helpful?
Company
Practice
Learn
© 2026 aloalgo.com. All rights reserved.