Explore greedy interview patterns: Kadane's maximum subarray, jump games, gas station, partition labels and more, each with the reason the greedy choice is safe.
The pattern
Greedy: take the best step now, and never look back
A greedy algorithm makes one locally best choice at a time and never undoes it. That makes it fast (usually one pass), but it's only correct when there's a reason the local choice can't hurt. Every problem here comes with that reason.
1Make the locally best choice
A greedy algorithm commits to the choice that looks best right now and never revisits it. Kadane's algorithm drops the running sum the moment it turns negative: a negative start can only hurt.
2Prove the choice is safe
Greedy is only correct when you can argue that some optimal answer agrees with your choice. In Jump Game, if an index can't reach the nearest good index, it can't reach a farther one either.
3When greedy fails, use DP
Greedy isn't always right: with coins 1, 3 and 4, the biggest-coin-first rule makes 6 as 4 + 1 + 1, but 3 + 3 is better. If you can't prove the greedy choice, try every choice with dynamic programming.
How to spot it
- A running value with a reset rule: best subarray, gas left in the tank.
- A frontier: the farthest reachable index, the nearest good index.
- A forced choice: the smallest card must start a group; a triplet that overshoots can never be used.
- If you can't explain why the choice is safe, it probably isn't: reach for DP.
Reading the pictures
- Each problem is a row (or two) scanned once. Teal is the element being read; faded elements are done or ruled out.
- The variables card holds the running value the greedy rule updates.
- The brute force on the right tries every option, which is what the greedy argument lets you skip.
NeetCode 150 · Greedy
All 8 problems
Pick a problem to see it solved step by step. They're in NeetCode's order, roughly easiest first.
Maximum Subarray
MediumBlind 75Return the largest sum of a non-empty contiguous subarray.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
nums
variables
- running sum
- 0
- best sum
- -2
Press Play or Step to watch the solution run.
Brute force vs the pattern
On this input:
- Pattern: O(n)
- 9 ops
- Brute force
- 45 ops
On a bigger input (300 numbers):
- Pattern
- 300 ops
- Brute force
- 45,150 ops
Add up every subarray: n²/2 of them, O(n²) even when each sum extends the previous one.
“ops” is an illustrative count of selected algorithm operations, with estimates for sorting. It excludes drawing and frame creation and is not a timing benchmark. The complexity describes the Python solution. On small inputs a brute-force search may find the answer sooner.
How it works: Maximum Subarray
Step by step
- Number being added
- Current subarray
- Best subarray so far
Press Start or Step: the step the animation is on lights up below.
- 1
Running sum 0
max_sub, cur_sum = nums[0], 0 - 2
Add the next number
cur_sum += n; max_sub = max(max_sub, cur_sum) - 3
Negative running sum → start over
if cur_sum < 0: cur_sum = 0 - 4
The best sum
return max_sub
Keep the best sum of a subarray ending at the current position. Extending it by the next number is always right, unless the running sum is negative: then the next subarray is better off starting fresh.
Why that's safe: a negative prefix makes every sum that includes it smaller, so no optimal subarray starts with one. The answer is the largest running sum seen.
Spot it in an interview
- Best contiguous run of anything additive: Kadane's algorithm.
- Greedy rule: drop a prefix as soon as it stops helping.
One pass, two numbers.
Credits
Learn more from NeetCode
The problem list and order come from the NeetCode 150 by NeetCode (neetcode.io). The solutions here follow the approaches NeetCode teaches in the linked videos; the animations, explanations and code were written for CodeQuest. If these help, NeetCode's videos and site are well worth your time.
Problem statements are summarised in our own words; the full versions are on LeetCode.