Greedy Algorithm Interview Patterns

Greedy algorithms are a cornerstone of technical interview preparation because they test your ability to identify efficient, intuitive solutions to optimization problems. While seemingly simple—make the best local choice at each step—knowing when and why a greedy approach is correct separates competent candidates from exceptional ones. Mastering common greedy patterns equips you to recognize the underlying structure of problems and articulate a rigorous justification for your solution, a skill highly valued in software engineering interviews.

The Greedy Paradigm and Its Core Property

At its heart, a greedy algorithm builds a solution piece by piece, always choosing the next piece that offers the most immediate, local benefit. It never reconsiders past choices. The critical question is: when does this short-sighted strategy lead to the globally optimal solution? The answer lies in the greedy choice property, which states that a locally optimal choice made at each step will lead to a globally optimal solution. Proving this property, even informally during an interview, is often the key to validating your approach.

You cannot apply a greedy strategy blindly. A classic counterexample is the traveling salesman problem: choosing the nearest unvisited city at each step (a greedy tactic) does not guarantee the shortest possible route. Therefore, your first mental step for any optimization problem should be to test if a greedy choice seems plausible. Often, sorting often precedes greedy selection. By arranging the input data (intervals by end time, tasks by frequency, or gas station metrics), you transform the problem into a state where the correct greedy choice becomes obvious and provable.

Core Pattern 1: Interval Scheduling

The interval scheduling problem is the quintessential greedy introduction. Given a set of intervals with start and end times, the goal is to select the maximum number of non-overlapping intervals. The greedy strategy is elegant: sort the intervals by their end time in ascending order. Always pick the interval that finishes first, remove all intervals that overlap with it, and repeat. This works because selecting the interval that ends earliest maximizes the remaining time for future selections.

Consider intervals: [1,3], [2,4], [3,5], [4,6]. Sorted by end time, they remain as listed. Your greedy choice is [1,3]. You discard [2,4] because it starts before 3 (overlaps). The next available is [3,5], which you select, then discard [4,6] as it overlaps. Your final set is two intervals, which is optimal. This pattern extends to problems like "Minimum Number of Arrows to Burst Balloons," where you find the minimum points to intersect all intervals.

Core Pattern 2: Jump Game and Reachability

The jump game problems ask if you can reach the end of an array where each element's value represents your maximum jump length from that position (e.g., [2,3,1,1,4]). The greedy approach is more efficient than dynamic programming. Instead of checking all possible jumps from each index, you maintain a variable, maxReach, which tracks the farthest index you can currently reach. You iterate, updating maxReach as max(maxReach, i + nums[i]). If at any point your current index i exceeds maxReach, you are stuck and return false. If maxReach reaches the last index, you succeed.

This works because it embodies the greedy choice: at every step, you are effectively asking, "From all the positions I can currently access, which one allows me to jump the farthest forward in the future?" You are greedily optimizing for future reachability. A common variant, "Jump Game II," asks for the minimum number of jumps. The greedy solution involves tracking the current "jump boundary" and making a jump when you reach it, incrementing the count and updating the boundary to the farthest point reached during that jump's exploration.

Core Pattern 3: Gas Station Circuit

The gas station problem presents a circular route with gas stations. Each station provides gas[i] amount of fuel, and traveling to the next station costs cost[i]. You must determine if you can complete the circuit and, if so, identify the unique starting station. A brute-force solution checks every start point, but a greedy $O(n)$ solution exists.

The greedy insight has two parts. First, if the total gas is less than the total cost, the journey is impossible. Second, if the journey is possible, the correct starting station can be found by tracking a running net gain/loss. You initialize totalTank and currTank to 0 and set startingStation = 0. As you iterate, add gas[i] - cost[i] to both. If currTank becomes negative at station i, you know you cannot start from any previous station up to i. You then greedily set the startingStation to i + 1 and reset currTank to 0. The station where you begin after the last reset is your answer. This works because if you fail traveling forward from A at station C, then starting at any point between A and C would also fail at C, as you would arrive with even less fuel.

Core Pattern 4: Task Scheduler with Cooldown

The task scheduler problem involves scheduling tasks (represented by letters) with a cooldown period n between two identical tasks. The goal is to find the minimum total time to complete all tasks. The greedy strategy focuses on the most frequent task. The intuition is that the schedule will be constrained by how we arrange the most frequent tasks to respect the cooldown.

The optimal formula is derived from a greedy framework. Let f_max be the frequency of the most common task. Imagine creating f_max "frames" or groups, each starting with an instance of this task. The idle slots between these tasks in the frame are of size n. You fill these slots with other tasks. The minimum time is at least (f_max - 1) * (n + 1) + (number of tasks with frequency f_max). The first term calculates the time up to the last frame: (f_max - 1) groups, each of length (task + n slots). The final frame is just the last instances of the most frequent tasks. However, if the number of total tasks exceeds this calculated minimum, it means there are so many tasks that you can fill all idle time without needing extra idles, so the answer is simply the total number of tasks. This pattern tests your ability to model scheduling constraints greedily based on task frequency.

Common Pitfalls

1. Assuming Greedy Works Without Proof: The most frequent mistake is forcing a greedy solution onto a problem that requires dynamic programming. For example, in the classic coin change problem (find the minimum coins for an amount with given denominations), a greedy approach of always taking the largest coin fails for denominations like [1,3,4] and amount 6. Greedy gives 4+1+1 (3 coins), while the optimal is 3+3 (2 coins). Correction: Always ask yourself if a future choice could invalidate the current local optimum. If the problem has overlapping subproblems and optimal substructure where you need to consider all combinations, dynamic programming is likely required.

1. Incorrect Sorting Key: In interval problems, sorting by start time instead of end time leads to a suboptimal selection. In a problem like "Maximum Profit in Job Scheduling," you might need to sort by end time for a weighted interval schedule, which is actually a DP problem, not a pure greedy one. Correction: Carefully model the greedy choice. If your rule is "pick the task that ends earliest to free up time," sort by end time. If it's "pick the shortest task first," sort by duration.

1. Overlooking Edge Cases in Reachability: In Jump Game, a common error is not handling the case where the starting position is 0 (you are stuck immediately). Another is incorrectly updating the maximum reach. Correction: Initialize maxReach = nums[0] and explicitly check for a zero at the starting point. In your loop, ensure you stop before the last element, as reaching it is sufficient.

1. Misapplying the Task Scheduler Formula: Candidates often memorize the formula (f_max - 1)*(n+1) + count_max but forget the critical final check: the answer is the maximum of this value and the total length of the task list. Correction: After calculating the formula-based minimum, compare it to the total number of tasks. The real answer is max(calculated_minimum, total_tasks) because a high number of tasks can saturate all idle slots.

Summary

• Greedy algorithms solve optimization problems by making a series of locally optimal choices, which must be proven to lead to a global optimum via the greedy choice property.
• Sorting the input data is a crucial preprocessing step for many greedy patterns, including interval scheduling and task scheduling, to reveal the optimal selection order.
• Key recognizable patterns include interval scheduling (sort by end time), jump game (track maximum reach), gas station (track net balance and restart), and task scheduler (prioritize by frequency and manage idle time).
• Understanding when greedy works versus when dynamic programming is needed is critical; greedy fails for problems where local choices have complex, negative future repercussions, such as the standard coin change problem.
• In an interview, always verbally justify your greedy choice, discuss the sorting key, and walk through a small example to demonstrate correctness before coding.