Back to DSA DashboardConcept Mastery
DSA Core Concept
Greedy
A Greedy algorithm is an algorithmic paradigm that makes the locally optimal choice at each step with the hope of finding a global optimum.
Why It Exists
Many optimization problems (like Dijkstra's shortest path or Huffman coding) are complex. Greedy algorithms bypass multi-step DP calculations, executing simple, fast logic.
Intuition for Beginners
“Think of counting change. If you want to give 36 cents in change, you pick the largest coin possible first (a quarter, 25c), leaving 11c. Then a dime (10c), leaving 1c. Finally a penny (1c). You choose the largest step at each moment.”
Visual Explanation
Greedy Local Choice vs Global Path:
[Start]
/ 10 \
(5) (2) <- Greedy picks 2 (smallest step)
/ \ / \
(99) (2) (50) (10) <- Path 2 -> 50 yields sum 52.
Path 5 -> 99 yields sum 104.
Greedy choice fails to yield absolute max! Coming Soon
Interactive Tracing Sandbox
Interactive step-by-step layout is currently under deployment. Complete trace state maps will be accessible in the next release.
Complexity Analysis
| Algorithm | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Choice Processing | O(N log N) | O(1) | Sorting is typically the bottleneck |
| Greedy Loop | O(N) | O(1) | Single pass calculations |
Production & Real World Applications
- •Huffman Coding: Text compression encoding characters based on frequency.
- •Minimum Spanning Trees: Kruskal/Prim algorithms connecting power networks.
Algorithmic Patterns
Sorting Preprocess
Sorting intervals or values first to make decisions sequentially.
Defending the Design (Interview Q&A)
Q:How do you prove that a greedy algorithm is correct?
Greedy correctness is typically proven using induction or exchange arguments (showing that replacing any choice in the optimal solution with the greedy choice does not degrade the result).
Common Traps & Mistakes
- ⚠️Using greedy on NP-hard problems (like Knapsack) where local choices yield sub-optimal results.
- ⚠️Forgetting to verify counterexamples where greedy splits fail.