Greedy Algorithms: Your Secret Weapon for Platform Interviews

You're staring at a problem description in a platform interview—maybe it's LeetCode, maybe it's something custom for a specific company—and the clock is ticking. The problem looks like a graph traversal, or dynamic programming, but then you notice something. You can make local optimal choices, and they just… work. That's the greedy algorithm screaming its name, and if you don't recognize it, you're toast. I've watched brilliant engineers fumble these because they overthink. They try to build a DP table for a problem that just needs a simple sort and a loop. You need to train your brain to spot these patterns, especially for platform interviews where time is your most precious resource. These aren't always the hardest problems, but they're often disguised, and missing the greedy approach costs you valuable minutes.

The "Why" Behind Greedy: Not Just for Speed

Greedy algorithms aren't just about speed; they're about elegance and often, simplicity. Your interviewer knows this. They know that a well-applied greedy solution can be implemented quickly and correctly, demonstrating a solid grasp of fundamental algorithm design. When you're under the gun in a 45-minute coding session, picking the approach that's both efficient and straightforward to code is a massive win. You'll complete the problem, test it, and still have time to discuss extensions or edge cases. This is a stark contrast to a complex DP solution that might take 30 minutes just to conceptualize, leaving you scrambling to write bug-free code in the remaining time. I've seen candidates deliver perfect greedy solutions in 15 minutes, then spend the rest of the time chatting about system design—that's how you impress.

Many new grads, and even some senior folks, jump straight to "dynamic programming" or "graph" because those sound more advanced. They forget that sometimes, the simplest path is the best. Think about Dijkstra's algorithm—it's inherently greedy. At each step, it picks the shortest path discovered so far. If you understand why that works, you're halfway to understanding the core principle. You're making the "best" local choice, hoping it leads to the global optimum. For greedy algorithms, that hope isn't just hope; it's provable correctness, and that's what we're after.

The Core Greedy Intuition: Local Optima, Global Truth

The fundamental idea behind any greedy algorithm is that you make the best choice at each step, and that sequence of locally optimal choices leads to a globally optimal solution. This isn't always true for every problem—that's the caveat. For many, though, it is. How do you know when it works? There are typically two properties:

1. Greedy Choice Property: A globally optimal solution can be reached by making a locally optimal (greedy) choice. This means that if you make the greedy choice, there's always an optimal solution that incorporates this choice. You don't have to worry about "ruining" future optimal choices.
2. Optimal Substructure: An optimal solution to the problem contains optimal solutions to subproblems. This is also a property of dynamic programming, but for greedy problems, the subproblems are usually simpler and don't require re-evaluating choices.

Let's take a classic example: Activity Selection Problem. You have a list of activities, each with a start and finish time, and you want to schedule the maximum number of non-overlapping activities. The greedy approach? Sort the activities by their finish times. Then, pick the first activity. After that, pick the next activity that starts after the first one finishes. Repeat. This works because picking the activity that finishes earliest leaves the maximum amount of time remaining for subsequent activities. You can prove this by contradiction, but intuitively, it makes sense. If you picked an activity that finished later, you'd have less time for the remaining activities, potentially reducing your total count.

This intuitive leap is what you need to cultivate. It's about recognizing when making the "obvious best" local choice doesn't paint you into a corner.

Pattern Recognition: Your Most Powerful Tool

Blindly applying greedy approaches without proving correctness is a recipe for disaster. But in an interview setting, you don't always have time for a rigorous proof. What you need is pattern recognition. Here are some common categories where greedy algorithms shine:

• Interval Problems: Think activity selection, merging intervals, scheduling tasks. Sorting by start or end times is a common first step.
  • Example: Given a list of intervals [start, end], determine the minimum number of intervals you need to remove to make the rest non-overlapping. Sort by end time, then iterate and count overlaps.
• Change-Making Problems (with specific coin denominations): If you have standard coin denominations (1, 5, 10, 25 cents), the greedy approach (always pick the largest coin possible) works. But if your denominations are weird (e.g., 1, 3, 4 cents for 6 cents change), greedy fails (three 1s vs. one 4 and one 1). This is a crucial distinction. For interviews, if they don't specify weird denominations, assume standard and go greedy.
• Fractional Knapsack: You can take fractions of items. Always pick the item with the highest value-to-weight ratio first. This is different from 0/1 Knapsack, which requires dynamic programming.
• Huffman Coding: Building the optimal prefix code tree is inherently greedy. At each step, you combine the two nodes with the smallest frequencies.
• Graph Algorithms: Dijkstra's (shortest path with non-negative edge weights) and Prim's/Kruskal's (minimum spanning tree) are prime examples. They make locally optimal choices (smallest edge, shortest path) to build a global solution.

You don't need to memorize every single greedy algorithm. Instead, learn to recognize the types of problems where this approach often applies. When you see a problem involving optimization (minimizing/maximizing something) and it feels like you can make a choice now without repercussions later, your greedy radar should be pinging.

The "Prove It" Moment (in 30 Seconds)

Alright, you've spotted a potential greedy solution. You've sorted your intervals or prioritized by some metric. Now, how do you quickly confirm it's correct without spending 15 minutes on a formal proof? You need a quick mental check, often called an "exchange argument."

Here's how it generally works:

1. Assume the Greedy Choice is NOT part of an optimal solution. This is your starting point for contradiction.
2. Construct an optimal solution (let's call it O) that does NOT use your greedy choice. Instead, O uses some other choice (let's call it X) at the point where your greedy choice (G) would have been made.
3. Show that you can replace X with G in O to create a new solution O'. This new solution O' is either better than O or equally optimal.
4. Conclude that O wasn't truly optimal, or that an optimal solution incorporating G exists. This contradicts your initial assumption, thus proving the greedy choice's validity.

This sounds heavy, but in an interview, it's a mental exercise. For the Activity Selection problem:

• Greedy Choice: Pick the activity a_k that finishes earliest among all compatible activities.
• Assume: There's an optimal solution O = {a_1, ..., a_m} that does NOT include a_k. Instead, O includes some a_j which finishes after a_k (or a_j just isn't a_k).
• Replace: If a_j is the first activity in O, and it finishes after a_k, then you could substitute a_k for a_j. a_k finishes earlier, so it still leaves the same or more time for subsequent activities in O. The number of activities stays the same (you swapped one for one), and you haven't made it worse. If anything, it opens up more possibilities for the remaining schedule.
• Conclusion: There exists an optimal solution that includes a_k.

This quick mental proof helps solidify your confidence. Don't write it all out unless explicitly asked, but have it ready to explain your logic. A good interviewer will appreciate you thinking through the correctness, not just jumping to code.

The Common Pitfalls: When Greedy Fails

Greedy isn't a silver bullet. You need to know its limitations. The most common pitfall is ignoring future consequences. When your "locally optimal" choice severely restricts or prevents a globally optimal path later, greedy will fail.

• 0/1 Knapsack: If you can't take fractions of items, picking the item with the highest value-to-weight ratio first might prevent you from fitting other valuable items. For example, if you have a knapsack capacity of 10, and items are (value=10, weight=10) and (value=9, weight=9) and (value=1, weight=1). Greedy might pick (10,10), leaving no space. But (9,9) and (1,1) would fit, giving value 10. This requires dynamic programming.
• General Graph Traversal: Finding the shortest path in a graph with negative edge weights. Dijkstra's, a greedy algorithm, breaks down here. You need Bellman-Ford or SPFA. Why? Because a locally shortest path might lead to a longer overall path if there's a negative edge later that makes another, initially longer path, ultimately shorter.
• Change-Making with Arbitrary Denominations: As mentioned, if denominations are non-standard (e.g., 1, 3, 4 cents for 6 cents), the greedy approach (one 4-cent, two 1-cent coins = 3 coins) is worse than the optimal (two 3-cent coins = 2 coins).

When faced with an optimization problem, quickly consider if any of these conditions are present. If you see negative weights, non-fractional items, or weird dependencies between choices, immediately pivot away from greedy and start thinking DP or backtracking. Don't waste precious interview time trying to force a greedy solution where it doesn't belong.

Practical Steps: From Problem to Code

Let's break down the process you'll use in an interview when you suspect a greedy approach:

1. Understand the Problem (5 minutes):

   • Read carefully. Identify inputs, outputs, constraints.
   • Draw small examples. Walk through them manually.
   • What are you trying to optimize (min/max)?
   • Are there any obvious brute-force solutions? (This helps understand the search space.)

2. Brainstorm Greedy Strategy (5-7 minutes):

   • "What's the best choice I can make right now, without looking too far ahead?"
   • Does sorting help? By what criterion? (e.g., finish times, value/weight ratio, shortest edge).
   • Consider the core "local optimal choice."
   • Self-check: Does this greedy choice seem to simplify the remaining problem?

3. Validate Greedy Intuition (3 minutes):

   • Run your greedy strategy on your small examples. Does it work?
   • Try to find a counterexample. If you can't, that's a good sign.
   • Mentally perform a quick exchange argument. "If I didn't make this greedy choice, could I do better? What if I swapped my non-greedy choice for the greedy one?"

4. Outline the Algorithm (5 minutes):

   • What data structures do you need? (e.g., List for sorting, PriorityQueue for Dijkstra/Prim).
   • What's the overall structure? (e.g., sort, then loop, taking elements and updating state).
   • Write down pseudo-code or high-level steps. Don't jump straight to syntax.

5. Code It Up (15-20 minutes):

   • Translate your outline into actual code.
   • Focus on correctness. Handle edge cases.
   • Write clean, readable code. Use meaningful variable names.

6. Test and Refine (5 minutes):

   • Run your code with the examples you drew earlier.
   • Consider edge cases: empty input, single element, all elements being the same.
   • Think about time and space complexity. Most greedy solutions are efficient (often O(N log N) because of sorting, or O(N) if no sort needed).

This structured approach prevents you from getting lost. It forces you to think before you code, which is always a good strategy in a timed setting.

Specific Techniques and Data Structures

Certain data structures become indispensable when implementing greedy algorithms. Mastering these is non-negotiable.

• Arrays.sort() / Collections.sort() (Java), list.sort() (Python), std::sort() (C++): Sorting is the foundational step for many greedy problems. You'll often sort based on a custom comparator or key function. For example, sorting intervals by their end times is a classic move.
• PriorityQueue (Java), heapq (Python), std::priority_queue (C++): These are essential for algorithms like Dijkstra's, Prim's, or any problem where you repeatedly need to extract the "best" (min/max) element from a collection. If your greedy choice involves always picking the smallest or largest current option, a min/max heap is your go-to. Think about finding the K largest elements or merging K sorted lists.
• HashMap / Dictionary / unordered_map: Useful for counting frequencies, mapping values, or quick lookups. While not exclusively greedy, they often support greedy choices by providing efficient access to data that influences the "best" local decision.

For instance, in a problem like "Minimum Platforms Needed" (given arrival/departure times, find minimum platforms to avoid conflicts), you might combine sorting with a sweep-line algorithm. Sort all events (arrivals and departures) by time. Iterate through the sorted events, incrementing a platform_count on arrival and decrementing on departure. The maximum platform_count seen is your answer. This neatly blends sorting and a greedy choice (always processing the earliest event first).

The Mental Shift: From DP to Greedy

Sometimes, a problem initially feels like DP. You think, "I need to build up a solution from subproblems." But then you look closer. If the "optimal choice" at each step doesn't depend on the choices made before that step in a complex, overlapping way, then it might be greedy.

Consider the "Maximum Subarray Sum" problem. A common DP solution is dp[i] = max(nums[i], nums[i] + dp[i-1]). This is correct. But there's also Kadane's algorithm, which is inherently greedy: keep track of the current maximum sum ending at the current position and the overall maximum sum. If adding the current number makes the current sum negative, reset it to zero (or the current number itself if all numbers are negative). This makes a locally optimal choice: extending the current subarray as long as it's beneficial. It's a fantastic example of a problem with both DP and greedy solutions, where the greedy one is often simpler to implement.

Your goal isn't just to solve the problem; it's to solve it optimally and efficiently within the interview constraints. Recognising a greedy opportunity saves you from over-engineering a DP solution. For an interview, this means fewer lines of code, fewer bugs, and a faster path to a working solution. That's how you come across as truly proficient, not just someone who memorizes algorithms.

Practice, Discuss, Internalize

Don't just read about these algorithms; work through them. LeetCode offers excellent problems tagged "Greedy." Start with easier ones and build up.

• Easy: Assign Cookies, Lemonade Change, Best Time to Buy and Sell Stock II.
• Medium: Jump Game, Non-overlapping Intervals, Minimum Number of Arrows to Burst Balloons, Partition Labels.
• Harder: Task Scheduler, Candy.

After solving a problem, look at other people's solutions. Did someone use a different greedy strategy? Why did it work? Or why didn't it work? Discuss with peers. Explain your logic out loud. The act of explaining forces you to solidify your understanding and identify gaps in your reasoning.

Mastering greedy algorithms isn't about memorizing every single greedy problem. It's about developing the intuition, recognizing the patterns, understanding the underlying principles, and knowing when to apply them—and crucially, when not to. This skill will serve you well, not just in platform interviews, but in your daily engineering work, where simple, elegant solutions often beat complex ones.

Ready to Ace Your Next Interview?

Practice with AI-powered mock interviews tailored to your target role and company. Start Practicing for Free | Explore Interview Prep