What Makes an Algorithm Greedy
A greedy algorithm makes the locally optimal choice at each step, hoping this leads to a global optimum. Greedy works when the problem has the “greedy choice property” (a locally optimal choice can be made without reconsidering it) and “optimal substructure” (an optimal solution contains optimal solutions to subproblems). Proving greedy correctness requires an exchange argument: show that replacing any solution’s choice with the greedy choice cannot make it worse. Greedy does NOT always work — dynamic programming is needed when subproblems overlap and greedy choices affect future subproblems.
Activity Selection / Interval Scheduling
Select the maximum number of non-overlapping activities. Sort by end time. Greedily pick the activity with the earliest end time that does not overlap with the last selected activity. Why sort by end time: picking the activity that ends earliest leaves the most room for future activities — the exchange argument shows no other choice can do better. O(n log n) for sorting, O(n) for the scan.
def activity_selection(intervals):
intervals.sort(key=lambda x: x[1]) # sort by end time
count, last_end = 0, float('-inf')
for start, end in intervals:
if start >= last_end:
count += 1
last_end = end
return countLC 435 (Non-overlapping Intervals — minimum removals): total – max non-overlapping. LC 452 (Minimum Arrows to Burst Balloons): same as activity selection. LC 646 (Maximum Length of Pair Chain): sort by second element, greedily pick non-overlapping pairs.
Jump Game (LC 55 and 45)
LC 55 (Can Jump): can you reach the end? Maintain the maximum reachable index. At each position i: if i > max_reach, stuck. Otherwise max_reach = max(max_reach, i + nums[i]). Return max_reach >= n-1. O(n). LC 45 (Minimum Jumps to Reach End): greedy BFS approach. Track current_end (end of current jump range) and farthest (maximum reachable from current range). For each position: update farthest. When i reaches current_end: take a jump (jumps++), set current_end = farthest. Stop when current_end >= n-1. O(n).
def jump(nums):
jumps = current_end = farthest = 0
for i in range(len(nums) - 1):
farthest = max(farthest, i + nums[i])
if i == current_end:
jumps += 1
current_end = farthest
return jumpsTask Scheduling with Cooldown (LC 621)
Minimum time to execute all tasks with cooldown n. Greedy insight: always execute the most frequent remaining task. Math formula: idle_slots = (max_freq – 1) * n – sum of (freq – 1) for all other tasks at max_freq. Total = num_tasks + max(0, idle_slots). Intuition: arrange tasks in “cycles” of (n+1) length. Fill each cycle starting with the most frequent task. Remaining slots in incomplete cycles are idle time.
Gas Station (LC 134)
Can you complete the circuit? If total gas >= total cost: a solution always exists (not obvious — requires proof). To find the starting station: greedily try each station as the start; if the tank ever goes negative, reset to the next station (the current span cannot contain the valid start). This works because we know a solution exists and we are eliminating invalid starts. O(n).
Candy (LC 135)
Assign candies such that each child gets at least 1, and children with higher ratings than their neighbor get more. Two passes: left→right (if rating[i] > rating[i-1]: candies[i] = candies[i-1]+1). right→left (if rating[i] > rating[i+1]: candies[i] = max(candies[i], candies[i+1]+1)). The second pass preserves the left-pass constraint via max. Total: sum of candies. O(n) time, O(n) space. Space-optimized O(1) space solution exists using slope counting.
Recognizing Greedy Problems
Clues: “minimum number of X”, “maximum X”, “optimal assignment”. Sorting the input by a key often reveals the greedy choice. Greedy vs DP: try greedy first (simpler). If you find a counterexample: switch to DP. Common greedy patterns: sort by end time (interval scheduling), sort by ratio (fractional knapsack), sort by deadline (earliest deadline first scheduling), sort by weight (Kruskal MST).
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: Coinbase Interview Guide
Asked at: LinkedIn Interview Guide