Greedy Algorithms
Practice & Revision
Greedy algorithm pattern recognition decision tree, cheat sheet, and Top 15 must-solve greedy interview problems.
1. Introduction
This section serves as your comprehensive reference and practice guide for Greedy algorithms. Master these templates, review the decision tree, and solve the curated Top 15 interview problems to prepare for technical interviews.
2. Greedy Decision Tree
Use this flow chart to determine the correct greedy strategy based on your problem:
3. Revision Cheat Sheet
Greedy Sorting Invariants
| Problem Scenario | Sort Criteria | Greedy Decision Rule | Complexity |
|---|---|---|---|
| Merge Intervals | Sort by start time | If next.start <= last.end, merge them. | O(N log N) |
| Activity Selection | Sort by end time | Pick next if next.start >= last.end. | O(N log N) |
| Fractional Knapsack | Sort by value/weight | Pack densest items fully first, then split last. | O(N log N) |
| Jump Game | No sort (linear scan) | Track maxReachable = max(maxReachable, i + nums[i]). | O(N) |
| Gas Station | No sort (linear scan) | Reset starting node if cumulative tank falls < 0. | O(N) |
4. Top 15 Must-Solve Greedy Problems
5. Problem-Solving Framework
When coding Greedy solutions, follow this 3-step checklist:
1. Verify if Sorting is Required:
- The majority of greedy failures in interviews are due to forgetting to sort the input array. Check if sorting by start-time, end-time, or weight-ratio establishes the greedy invariant.
2. Prove with Counter-Examples:
- Before coding, try to break your greedy logic. For example, if you think taking the largest coin works for Coin Change, test with coin set [1, 3, 4] and target 6 to identify if a DP approach is required.
3. Optimize Space to O(1):
- Greedy algorithms should be memory efficient. Avoid creating helper lists or tables if you can track states in-place using scalar variables (like maxReachable).
6. Quiz
Question 1: In 'Candy', why do we perform two separate passes (left-to-right and right-to-left)?
Answer: A single pass cannot satisfy ratings constraints in both directions simultaneously. The left-to-right pass ensures children with higher ratings than their left neighbor get more candy. The right-to-left pass ensures the same condition is met relative to their right neighbor, taking the maximum of both counts.Question 2: What is the optimal greedy strategy to burst the maximum number of balloons with the minimum number of arrows?
Answer: Sort balloons by their end coordinates. Shoot an arrow at the end coordinate of the first balloon; this arrow is guaranteed to burst all overlapping balloons that start before or at this point.Question 3: Why does 'Queue Reconstruction by Height' sort people by height in descending order first?
Answer: Sorting by height in descending order ensures that when we insert a person at indexK, all people already placed in the queue are taller than them. This directly satisfies their positioning constraint, simplifying insertions.
Question 4: True or False: Fractional Knapsack can be solved in O(N log N) time, whereas 0/1 Knapsack is NP-hard.
Answer: True. The ability to take fractions allows us to greedily take items sorted by value density. 0/1 Knapsack requires checking combinations of whole items, which is NP-hard and requires DP.Question 5: What is the space complexity of 'Lemonade Change'?
Answer:O(1) auxiliary space, since we only need to track the count of 5 and