LeetCode Greedy Algorithm Patterns — When Greedy Beats DP

Greedy algorithms are deceptively simple in concept: at every decision point, take the locally optimal choice and never look back. No memoization table, no recursive subproblems, no backtracking. Just one pass, one decision, done. In practice, greedy solutions are often the shortest, most elegant code you will write in a LeetCode session. Jump Game (#55) — a problem that looks like it might require dynamic programming — reduces to a single pass tracking the maximum reachable index. Gas Station (#134) reduces to checking whether total gas minus total cost is non-negative and tracking a running balance.

The hard part of greedy problems is not coding them. A greedy solution, once you know it works, is usually trivial to implement. The hard part is proving — or intuiting — that the greedy approach is correct. There are thousands of optimization problems where taking the locally best option leads you away from the globally optimal answer. Coin Change (#322) is the canonical example: greedy works perfectly for US currency (quarters, dimes, nickels, pennies) but fails spectacularly for arbitrary denominations. Getting greedy vs DP classification right is a skill that separates good LeetCode performers from great ones — and it is exactly the kind of judgment that senior engineers are evaluated on in interviews.

This guide teaches you the theoretical foundation — the greedy choice property and optimal substructure — and then maps that theory onto the concrete LeetCode problem categories where greedy reliably works. You will also learn the most common greedy failure cases so you can avoid the trap of applying greedy where DP is required. By the end, you will have both the intuition and the problem list to make greedy a reliable part of your interview toolkit.

A problem is solvable by greedy if and only if it has two properties: optimal substructure and the greedy choice property. Optimal substructure means that an optimal solution to the whole problem contains optimal solutions to its subproblems — this is a property shared by both greedy and dynamic programming, which is why greedy and DP are often confused. The distinguishing property is the greedy choice property: making the locally optimal choice at each step never rules out reaching the globally optimal solution.

Greedy algorithms work when the problem has the 'greedy choice property' — making the locally optimal choice never rules out reaching the globally optimal solution. This is the formal definition, and while it sounds abstract, it maps to a concrete intuition: can you always commit to the best available option right now without needing to reconsider it later? If yes, greedy works. If future decisions might make your current choice look wrong in hindsight, greedy fails and you need DP.

The proof technique for greedy correctness is called the 'exchange argument': assume there exists an optimal solution that differs from the greedy solution at some step, then show that swapping that step's choice to the greedy choice produces a solution that is at least as good. If the exchange never makes things worse, the greedy choice is always safe. You will rarely need to formally prove this in an interview, but understanding the exchange argument helps you quickly assess whether a greedy approach is legitimate or wishful thinking.

Spotting greedy-solvable problems in an interview comes down to asking one question: 'Can I always take the best option now without regretting it later?' For interval scheduling, always picking the interval that ends earliest is never regrettable — it leaves maximum room for future intervals. For the jump game, always tracking the farthest reachable position is never regrettable — a farther reach is strictly better. When you can frame the problem so that the greedy choice is monotonically non-regrettable, you have found your greedy invariant.

Interval scheduling is the most important greedy pattern for LeetCode. The canonical insight is: when you need to select or merge intervals, sort by end time (not start time) and greedily commit. Merge Intervals (#56) sorts by start time and merges overlapping intervals in a single pass. Meeting Rooms II (#253) uses a min-heap sorted by end time to track concurrent room usage. Non-overlapping Intervals (#435) — perhaps the most elegant greedy interval problem — asks for the minimum number of intervals to remove so the rest are non-overlapping. The greedy solution: sort by end time, greedily keep the interval with the earliest end that does not overlap with the previous kept interval, and count removals. This works because keeping the earliest-ending interval is never regrettable — it leaves maximum room for subsequent intervals.

Activity selection / jump game patterns involve greedy tracking of a running maximum or running feasibility variable. Jump Game (#55): iterate left to right, maintain maxReach = max(maxReach, i + nums[i]). If i ever exceeds maxReach, return false. This is pure greedy — at each position, we commit to the best possible reach from that index. Jump Game II (#45) extends this to finding the minimum jumps: track curEnd (the boundary of the current jump) and curFarthest (the farthest reachable from within the current jump). When i reaches curEnd, increment jumps and update curEnd = curFarthest. No DP table needed.

Sorting-based optimization covers problems where establishing the right order enables a greedy sweep. Gas Station (#134): compute the net gain/loss at each station (gas[i] - cost[i]). If total net is negative, no solution exists. Otherwise, sweep left to right tracking running tank. When tank goes negative, reset the starting station to i+1 — the greedy insight is that any starting point before i+1 cannot reach i+1 (since we already know the prefix sum went negative). Candy (#135): two-pass greedy — left pass ensures each child with higher rating than their left neighbor gets one more candy, right pass does the same for the right neighbor direction.

The following table covers the 10 most important greedy problems on LeetCode, organized by sub-pattern. These problems appear frequently in interviews at top-tier companies and collectively cover every major greedy technique. Mastering these 10 gives you a complete greedy toolkit.

Jump Game (#55, Easy/Medium) is the greedy entry point: single-pass maxReach tracking. Jump Game II (#45, Medium) extends it to minimum jumps with a two-pointer boundary approach. Gas Station (#134, Medium) is the greedy running-sum classic — understand why resetting the start to i+1 is always correct. Non-overlapping Intervals (#435, Medium) is the interval scheduling masterclass. Merge Intervals (#56, Medium) tests sort-then-sweep. Meeting Rooms II (#253, Medium) requires a min-heap for concurrent interval tracking. Task Scheduler (#621, Medium) uses a frequency-based greedy formula. Candy (#135, Hard) uses two-pass directional greedy. Assign Cookies (#455, Easy) is the simplest two-pointer greedy for warming up. Minimum Number of Arrows to Burst Balloons (#452, Medium) is identical in structure to non-overlapping intervals — a perfect pattern recognition test.

When drilling these problems, practice articulating your greedy invariant before coding. For each problem, write one sentence explaining why the greedy choice is never regrettable. This habit builds the proof intuition that lets you confidently apply greedy to novel problems in interviews rather than guessing.

Greedy and dynamic programming share optimal substructure, which is why they are so easy to confuse. The deciding factor is the greedy choice property. DP is required when the optimal choice at the current step depends on what choices you made (or will make) in future steps — when committing to a local optimum now can close off globally optimal paths later. Greedy is correct when commitment to the local optimum is always safe — when future decisions cannot make the current choice look regrettable.

A practical heuristic: if you can sort or order the elements and make one-directional decisions without ever needing to reconsider a past choice, suspect greedy. If you find yourself wanting to branch — 'I could include this element or skip it, and I'm not sure which is better without knowing future elements' — that is a sign DP may be needed. The 0/1 Knapsack problem is the archetype: at each item, you choose include or exclude. The greedy approach (take items by best value-to-weight ratio) fails because including a high-ratio item may leave insufficient capacity for a combination of lower-ratio items that has higher total value.

Coin Change (#322) is the most common greedy trap in LeetCode interviews — greedy works for US currency but fails for arbitrary denominations, which is why it requires dynamic programming. With coins [1, 5, 6, 9] and target 11, greedy takes 9 first, then 1+1 for total 3 coins. The optimal solution is 5+6 = 2 coins. This failure is not a coincidence — it reflects that the greedy choice property does not hold: choosing the largest denomination now (9) ruled out the globally optimal combination. DP correctly explores all subproblems to find the minimum.

A complementary test: if the problem asks for a count of minimum/maximum without caring about the actual sequence of choices, and you can establish that the greedy order is always dominant, greedy is likely correct. If the problem requires tracking a combination of elements (a subset, a subsequence, a partition), DP is usually required because the correct combination depends on global, not local, reasoning.

The three most dangerous greedy traps in LeetCode interviews are Coin Change (#322), Longest Increasing Subsequence (#300), and 0/1 Knapsack variants. Each of these problems has a surface-level greedy intuition that fails — understanding exactly why they fail deepens your greedy choice property intuition far more than studying additional greedy successes.

Coin Change (#322): the greedy trap is always taking the largest coin that fits. This works for canonically structured currency systems (where each denomination is a multiple of the smaller ones) but fails for arbitrary denominations. The failure mode is that a large denomination may prevent you from reaching the target with a combination of smaller denominations that has fewer coins total. DP solves this by computing the minimum coins for every subamount from 0 to target, building up the answer from proven subproblems.

Longest Increasing Subsequence (#300): the greedy trap is always appending the next element that is larger than the last element in your current subsequence. But which element to end on matters — a greedy local choice (e.g., appending 5 instead of 3) may be immediately larger but closes off a longer continuation. The DP approach computes for every index i the length of the LIS ending at i, then takes the maximum. The patience sorting / binary search approach achieves O(n log n) but is itself a non-obvious greedy with a careful invariant — not the naive greedy that fails.

0/1 Knapsack: the greedy trap is sorting items by value-to-weight ratio and including the best-ratio items until the capacity is exhausted. This is correct for the fractional knapsack (where you can take partial items) but fails for 0/1 knapsack (take all or nothing). The reason: including a high-ratio item early may use capacity that could be better allocated to a combination of lower-ratio items with higher aggregate value. DP builds the solution by considering every (item, remaining capacity) pair.

The ability to quickly and correctly classify a problem as greedy vs DP is one of the clearest markers of seniority in coding interviews. Junior candidates often guess — they try greedy first and switch to DP when it fails, or they default to DP for every optimization problem out of caution. Senior candidates evaluate the greedy choice property deliberately: they articulate the greedy invariant, test it on a few examples, and either commit confidently or recognize the failure mode and switch to DP.

The core diagnostic question — 'Can I always take the best option now without regretting it later?' — is the fastest path to correct classification. For interval scheduling problems, the answer is almost always yes (sort by end time, commit greedily). For subsequence and subset selection problems, the answer is almost always no (future choices depend on past commitments). For running-sum feasibility problems like Gas Station and Jump Game, the answer is yes once you identify the right greedy invariant (reset start position, track maximum reach). For problems with arbitrary value combinations like Coin Change and Knapsack, the answer is definitively no.

Building this classification speed requires drilling real problems under time pressure — not just reading solutions. YeetCode's spaced repetition system is particularly effective for greedy and DP pattern recognition because the key skill is pattern recall: seeing an interval scheduling problem and immediately knowing the sort-by-end-time invariant, or seeing a coin problem and immediately flagging it as DP. Spaced repetition surfaces problems at the exact intervals that lock these pattern associations into long-term memory, which is what produces the fast, confident classification that interviewers reward.

Start with the 10-problem greedy list above. For each problem, practice explaining the greedy invariant in one sentence before writing any code. Then drill the three canonical DP problems (Coin Change, LIS, Knapsack) until you can articulate precisely why greedy fails for each. That combination — confident greedy application plus sharp greedy failure detection — is the complete greedy toolkit that top-performing interview candidates carry into every coding round.