aloalgoGreedy Algorithms Summary
A quick reference for greedy techniques and problems to practice. Greedy algorithms build solutions piece by piece, always choosing the option that looks best at the current moment without reconsidering previous choices. This makes them fast and simple to implement, but they only work when making locally optimal choices leads to a globally optimal solution.The hardest part of greedy problems is not writing the code. It is convincing yourself (and your interviewer) that the greedy approach actually produces the correct answer. In an interview setting, you should be prepared to explain why the greedy choice is safe, often using an exchange argument: assume the optimal solution makes a different choice and show that swapping to the greedy choice does not make the result worse.Key Concepts
The following table summarizes the core ideas behind greedy algorithms. Understanding these concepts will help you recognize when a greedy approach is appropriate and how to justify it.| Concept | Description |
|---|---|
| Greedy Choice | Make locally optimal choice at each step |
| Optimal Substructure | Optimal solution contains optimal solutions to subproblems |
| Sorting First | Many greedy problems require sorting input first |
| Proof by Exchange | Show swapping choices doesn't improve solution |
Complexity
| Pattern | Time | Space |
|---|---|---|
| With sorting | O(n log n) | O(1) - O(n) |
| Without sorting | O(n) | O(1) |
| With heap | O(n log k) | O(k) |
When Greedy Works
- Activity/Interval Selection: Sort by end time, pick non-overlapping
- Fractional Knapsack: Sort by value/weight ratio
- Huffman Coding: Build tree from lowest frequencies
- Minimum Spanning Tree: Kruskal's and Prim's algorithms
- Shortest Path: Dijkstra's algorithm (non-negative weights)
When Greedy Fails
- 0/1 Knapsack: Can't take fractions, need DP
- Coin Change (arbitrary): Non-standard denominations require DP
- Longest Path: Picking longest edge doesn't give optimal path
- Negative Edge Weights: Dijkstra fails, use Bellman-Ford
Chapters
- Greedy Algorithms - Core concepts and intuition
- When Greedy Works - Identifying greedy problems
Practice Problems
Easy
Medium
Hard
Was this helpful?
Company
Practice
© 2026 aloalgo. All rights reserved.