LAUNCH OFFER: Only 12 Lifetime Access spots left at $149 $49.

Patterns/Greedy Algorithms

Greedy Algorithms

Top interview pattern

85 min read

Updated June 2026

What you'll learn

Identify which greedy mechanism a problem needs: sort-then-scan for selection, track-and-update for reachability, or build-and-prune for construction
Verify greedy correctness by testing small counterexamples and checking if locally optimal choices can ever produce a globally suboptimal result
Test greedy candidates against small inputs before committing, because greedy returns plausible but suboptimal answers when it fails
Select the correct sorting criterion for interval and scheduling problems: end time for maximum selection, start time for merging, deadline for sequencing

A greedy algorithm builds a solution one step at a time, picking the best available option and never backtracking. When the greedy choice property holds, this produces optimal solutions in O(n) or O(n log n) time instead of the exponential cost of exhaustive search. The hard part: greedy returns plausible but suboptimal answers when it fails, with no error or warning.

What Is a Greedy Algorithm?

Greedy vs DP: Decision Tree

Setup

Nodes visited

Backtracking

Complexity

A decision tree where each node has a value. Goal: find the path from root to leaf that picks the best choices.

Two strategies: Greedy always picks the locally best option. DP explores every possibility.

DP explicitly compares all choices at each step by filling a table. Greedy commits to one choice per step and never reconsiders. When the greedy choice property holds, both arrive at the same answer, but greedy runs in O(n log n) or O(n) versus DP's typical O(n²) or worse.

This works when two conditions hold:

Greedy choice property: picking the best option right now never forces a suboptimal outcome later.
Optimal substructure: solving smaller pieces optimally leads to solving the whole thing optimally.

When either condition fails, greedy silently gives wrong answers. Coin change with denominations [1, 3, 4] targeting 6 illustrates this:

Step 1: Greedy picks the largest coin that fits: 4. Remaining: 2.
Step 2: Largest coin ≤ 2 is 1. Remaining: 1.
Step 3: Pick 1 again. Total: 3 coins (4+1+1).
Optimal: 3 + 3 = 2 coins. Greedy missed this because it committed to 4 too early.

The greedy template relies on two ideas: a greedy criterion, the rule used to sort or rank items (e.g., "sort activities by end time"), and a compatibility check, whether an item fits with what you've already chosen (e.g., "does this activity start after the last selected one ends?"). The template puts them together:

Greedy Template

1def greedy_solve(items):

2 # 1. Sort or organize by greedy criterion

3 items.sort(key=greedy_criterion)

5 result = []

6 for item in items:

7 # 2. If compatible with current solution, take it

8 if is_compatible(item, result):

9 result.append(item)

11 return result

Interview Tip

Identify the greedy criterion and compatibility check before coding

Identify two things before coding: the greedy criterion (what to sort by) and the compatibility check (what makes an item valid). Activity selection: sort by end time, check start >= last end.

Three Greedy Mechanisms

Greedy algorithms come in three flavors, each with a different mechanism:

Sort-and-scan: Sort items by some criterion, then scan left to right, selecting each compatible item. Activity selection, non-overlapping intervals, assign cookies. The sort encodes the greedy priority; the scan applies it.
Track-and-update: Maintain a running state variable (farthest reachable, current tank, running sum) and update it as you iterate. Jump Game, Gas Station. No sorting needed; the array is processed in order.
Build-and-prune: Construct the answer piece by piece, using a stack or similar structure to retroactively fix earlier choices when a better option arrives. Remove K Digits, Largest Number. The stack allows limited "undo" within the greedy framework.

Recognizing which flavor a problem needs helps you choose the right data structure immediately: sort-and-scan uses an array, track-and-update uses one or two variables, and build-and-prune uses a stack.

Flavor	Data Structure	Example Problems	Time
Sort-and-scan	Sorted array	Activity Selection, Assign Cookies, Arrows to Burst Balloons	O(n log n)
Track-and-update	1-2 variables	Jump Game, Gas Station, Best Time to Buy/Sell Stock	O(n)
Build-and-prune	Stack	Remove K Digits, Largest Number, Next Greater Element	O(n)

Greedy vs Dynamic Programming

The biggest risk with greedy: no error, no crash, just a wrong answer that looks plausible.

Greedy vs DP: Coin Change

Can greedy always find minimum coins? It depends on the denominations.

Greedy coin change: always pick the largest denomination that fits. This works for some coin sets but not all.

	Greedy	Dynamic Programming
Choices	Makes one choice per step	Considers all choices per step
Backtracking	Never reconsiders	Implicitly considers alternatives via subproblems
Time complexity	Usually O(n log n) or O(n)	Usually O(n²) or O(n × target)
Space	Often O(1) extra	O(n) to O(n²) for DP table
Correctness	Only when greedy choice property holds	Always correct (if recurrence is right)
Correctness check	Test counterexamples: can a local choice ever hurt globally?	Verify recurrence covers all subproblems

When to Use Greedy

Scenario	Approach	Why
Each local choice is independent of future choices	Greedy	No decision can be improved by reconsidering
Current choice affects which future choices are available	DP	Need to compare all options to find global best
You need all valid solutions, not just the best	Backtracking	Must explore entire search space
Greedy criterion exists but counterexample found	DP	Greedy choice property fails
DP table shows same choice wins at every step	Greedy	DP collapses. The table is redundant

Classic counterexamples where greedy fails:

Coin Change with coins [1, 3, 4], target 6: greedy gives 3 coins (4+1+1), DP gives 2 (3+3).
0/1 Knapsack: items have weight-value tradeoffs. Greedy by value/weight ratio fails when items can't be fractioned.
Longest Increasing Subsequence: greedily picking the smallest next element doesn't maximize length.

Interview Tip

When you suspect greedy, try to break it first

Test with denominations [1, 3, 4] target 6. Greedy gives 4+1+1 (3 coins), but 3+3 gives 2. This 30-second check catches most wrong greedy approaches.

Common Mistake

The silent failure of greedy

Greedy doesn't crash when it's wrong. It returns a suboptimal answer with no error, no warning. As the coin change example above shows, you get a valid answer that happens to be wrong. Always verify the greedy choice property before committing to a greedy approach.

Complexity Comparison by Problem

Problem	Greedy	DP	Winner
Activity Selection	O(n log n)	O(n log n)	Greedy (simpler code)
Coin Change (standard)	N/A (wrong)	O(n × amount)	DP (greedy fails)
Coin Change (canonical)	O(amount)	O(n × amount)	Greedy (for special denominations)
Jump Game I	O(n)	O(n)	Greedy (O(1) space)
Jump Game II	O(n)	O(n²)	Greedy (10× faster)
Task Scheduler	O(n)	O(n × 26)	Greedy (formula approach)
0/1 Knapsack	N/A (wrong)	O(n × W)	DP (greedy fails)
Fractional Knapsack	O(n log n)	N/A	Greedy (items are divisible)

When greedy applies, it is always at least as fast as DP (often faster), uses less space, and produces simpler code. Use greedy when you can verify it's correct. Use DP when in doubt.

Interview Tip

Common follow-up: 'What if we change this constraint?'

This question often flips a greedy problem into a DP problem. For example: "What if activities have weights and you want to maximize total weight?" This is the weighted activity selection problem, which requires DP. Recognize the shift and pivot: "With weights, the locally optimal choice (earliest end) might not maximize total weight, so I'd switch to DP."

From Brute Force to Greedy

Activity selection with activities [(1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16)]:

Attempt 1: Brute Force Subset Enumeration

Try every possible subset of activities. For each subset, check if all activities are non-overlapping. Track the largest valid subset. This is correct but has O(2ⁿ) time complexity, making it impractical for n > 20. For our 11 activities, that's 2,048 subsets to check.

Brute Force: O(2ⁿ)

1def max_activities_brute(activities):

2 n = len(activities)

3 best = 0

5 for mask in range(1 << n):

6 subset = [activities[i] for i in range(n) if mask & (1 << i)]

7 # Sort by start time and check for overlaps

8 subset.sort()

9 valid = True

10 for i in range(1, len(subset)):

11 if subset[i][0] < subset[i-1][1]:

12 valid = False

13 break

14 if valid:

15 best = max(best, len(subset))

17 return best

Attempt 2: DP with Sorted Activities

Sort by end time. For each activity i, use binary search to find the latest non-overlapping activity j before it. DP recurrence: dp[i] = max(dp[i-1], 1 + dp[j]). This reduces to O(n log n) time but uses O(n) space for the DP table. Much faster than brute force, but the DP table reveals a pattern that makes it unnecessary.

DP: O(n log n)

1def max_activities_dp(activities):

2 activities.sort(key=lambda x: x[1]) # Sort by end time

3 n = len(activities)

4 dp = [0] * n

5 dp[0] = 1

7 def last_compatible(i):

8 # Binary search for latest activity ending <= activities[i][0]

9 lo, hi = 0, i - 1

10 while lo <= hi:

11 mid = (lo + hi) // 2

12 if activities[mid][1] <= activities[i][0]:

13 lo = mid + 1

14 else:

15 hi = mid - 1

16 return hi

18 for i in range(1, n):

19 # Option 1: skip activity i

20 exclude = dp[i - 1]

21 # Option 2: include activity i

22 j = last_compatible(i)

23 include = 1 + (dp[j] if j >= 0 else 0)

24 dp[i] = max(exclude, include)

26 return dp[-1]

Attempt 3: Greedy Collapse

The DP table reveals a pattern: at every step, when an activity is compatible (start ≥ last_end), the "include" branch wins. The "exclude" branch only wins when there's an overlap. Since we process in end-time order, the first compatible activity is always the one that ends earliest. Picking it always matches what the DP would choose.

The entire dp[0..n-1] array reduces to a single variable last_end. The O(n) space collapses to O(1). The O(n log n) binary search inside the DP loop becomes unnecessary because we process compatible activities in order.

Greedy: O(n log n)

1def max_activities_greedy(activities):

2 activities.sort(key=lambda x: x[1]) # Sort by end time

4 count = 1

5 last_end = activities[0][1]

7 for i in range(1, len(activities)):

8 if activities[i][0] >= last_end:

9 count += 1

10 last_end = activities[i][1]

12 return count

The core observation: When DP's optimal choice is always the same local choice, the table is redundant. The entire O(n) DP table collapses into a single variable (last_end).

This progression from O(2ⁿ) to O(n log n) to O(n log n) with O(1) space shows why greedy works here. Each simplification keeps the same answer, confirming the greedy choice is valid. The DP solution serves as a bridge between the brute force (obviously correct) and the greedy (fast but needs justification).

Interview Tip

Walk through this progression to show you derived the solution

Don't jump straight to the greedy solution. Start by saying "The brute force is 2^n subsets. We can improve with DP by sorting and using a recurrence. But notice that the DP always picks the same thing as the greedy choice, so the table is redundant."

Recognizing Greedy Problems

Category	Signal Phrases	Core Observation
Scheduling/Selection	"maximum non-overlapping", "minimum rooms"	Sort by end time; earliest finish leaves most room
Reachability/Coverage	"can reach end", "minimum jumps", "minimum stations"	Track farthest reachable point; greedily extend
Resource Allocation	"minimum cost", "assign tasks", "distribute"	Process highest-demand or largest items first
Construction/Ordering	"largest number", "remove k digits", "reorganize string"	Build answer piece-by-piece with greedy comparison

Scheduling/Selection: When you hear "maximum non-overlapping," the problem has a natural ordering (by end time) where each choice is independent of future choices. Picking the earliest-ending item can never block a better option because it leaves strictly more room. This independence is what makes greedy valid.

Reachability/Coverage: "Can reach end" or "minimum jumps" problems track the farthest position reachable so far. This boundary only moves forward, never backward. Once a position is reachable, it stays reachable. No backtracking is ever needed because extending your reach from any visited position can only push the boundary farther out.

Resource Allocation: "Assign tasks" and "minimum cost" problems work greedily when the highest-demand or largest item constrains the solution structure. Processing it first determines the skeleton; smaller items fill gaps. If the items don't have a clear dominance ordering, DP is needed.

Construction/Ordering: "Largest number" or "remove k digits" problems build the answer incrementally. At each position, the locally optimal digit choice (largest available, or removing a digit that's bigger than its successor) cannot be improved by a later choice because the higher-order positions dominate the result. The monotonic stack is the workhorse data structure for these problems.

Quick Category Identification

Use these signal words to instantly classify a problem:

If you see...	Think...	Template
"maximum non-overlapping" or "minimum removals"	Scheduling	Sort by end time, scan
"can reach end" or "minimum jumps"	Reachability	Track farthest variable
"cooldown" or "frequency" or "distribute"	Resource	Frequency counting + formula
"smallest/largest number" or "remove k"	Construction	Monotonic stack or comparator
"minimum cost" with weighted choices	Probably not greedy	Use DP instead

Key Insight

Verifying the Greedy Choice Property

The test: can a non-local choice ever produce a strictly better global result? If not, greedy applies. If even one counterexample exists, the problem requires DP.

Interview Tip

Start by identifying the category

When you see a new greedy problem, immediately classify it: scheduling, reachability, resource, or construction. This narrows your template options from dozens of approaches to one or two. Say it out loud: "This looks like a scheduling problem because we're selecting non-overlapping items."

Greedy Templates

Each greedy category follows a similar structure. Once you recognize which category a problem falls into, the code is mostly the same across problems.

Scheduling / Selection

Select the maximum number of non-overlapping items from a set with start/end times. Sort by end time, then greedily pick each compatible item. This template applies to activity selection, non-overlapping intervals, and balloon bursting.

When to use: The problem asks for maximum non-overlapping selections or minimum removals to eliminate all overlaps.

Scheduling Template

1def scheduling_greedy(intervals):

2 intervals.sort(key=lambda x: x[1]) # Sort by END time

3 count = 0

4 last_end = float('-inf')

6 for start, end in intervals:

7 if start >= last_end: # Compatible

8 count += 1

9 last_end = end

11 return count

13# Variant: minimum removals = len(intervals) - scheduling_greedy(intervals)

Why sort by end, not start: Sorting by end time ensures the first compatible item finishes as early as possible, leaving maximum room. Sorting by start time picks items that begin soonest, but they might run for a very long time, blocking many shorter items.

Common variations:

• "Minimum removals for non-overlapping" = n - scheduling_greedy(intervals)
• "Minimum arrows to burst balloons" = count of non-overlapping groups
• "Maximum number of events" = sort by end, pick earliest compatible

Interview Tip

Scheduling problems hide everywhere

"Minimum number of meeting rooms" is not this template (it needs a heap or sweep line). But "maximum events you can attend" is. The key difference: this template picks items that don't overlap. Meeting rooms counts simultaneous overlaps. Recognizing this distinction saves you from applying the wrong algorithm.

Reachability / Coverage

Determine if you can reach a target, or find the minimum steps to do so. Track the farthest reachable point and greedily extend it. Applies to Jump Game, Video Stitching, and minimum taps to water a garden.

When to use: You're moving through a sequence and each position offers a range of forward options. The question is reachability or minimum hops.

Why greedy works: The reachable set is always a contiguous range [0, farthest]. Extending farthest can never hurt. There's no tradeoff between "reaching far now" and "reaching far later" because a farther frontier strictly dominates a closer one.

Reachability Template

1def can_reach(nums):

2 farthest = 0

3 for i in range(len(nums)):

4 if i > farthest:

5 return False # Gap: unreachable

6 farthest = max(farthest, i + nums[i])

7 return True

9def min_jumps(nums):

10 jumps = 0

11 current_end = 0

12 farthest = 0

13 for i in range(len(nums) - 1):

14 farthest = max(farthest, i + nums[i])

15 if i == current_end: # Must jump

16 jumps += 1

17 current_end = farthest

18 return jumps

Interview Tip

Two variants of reachability

"Can you reach?" uses one variable (farthest). "Minimum jumps" uses two (farthest + current_end). The second variant is BFS-like: each "level" is a range of positions, and moving to the next level is one jump. Know both and state which one the problem needs.

Resource Allocation

Distribute limited resources optimally. The highest-demand item determines the structure; other items fill gaps. Applies to Task Scheduler, Reorganize String, and gas station problems.

When to use: There's a constraint on how resources are distributed (cooldown, capacity, fuel) and the most constrained element dictates the answer.

Resource Allocation Template

1def resource_allocation(tasks, constraint):

2 from collections import Counter

3 freq = Counter(tasks)

4 max_freq = max(freq.values())

5 max_count = sum(1 for v in freq.values() if v == max_freq)

7 # The dominant element creates the skeleton

8 slots = (max_freq - 1) * (constraint + 1) + max_count

10 # If enough diverse items, no idle needed

11 return max(len(tasks), slots)

Idle Time Formula: The max(len(tasks), slots) handles two regimes. When tasks are diverse, no idle time is needed and the answer is just the total count. When one task dominates, the cooldown frames create mandatory gaps and the formula determines the answer.

Construction / Ordering

Build the optimal sequence or number by making greedy comparisons at each position. Uses a monotonic stack or custom comparator. Applies to Remove K Digits, Largest Number, and Create Maximum Number.

When to use: You're constructing a result character-by-character or digit-by-digit, and higher-order positions dominate the outcome.

Construction Template (Monotonic Stack)

1def remove_k_digits(num, k):

2 stack = []

3 for digit in num:

4 while stack and k > 0 and stack[-1] > digit:

5 stack.pop()

6 k -= 1

7 stack.append(digit)

9 # If k removals remain, trim from end

10 stack = stack[:len(stack) - k]

12 # Remove leading zeros

13 return ''.join(stack).lstrip('0') or '0'

Largest Number (Custom Comparator)

1def largest_number(nums):

2 from functools import cmp_to_key

3 nums = [str(n) for n in nums]

4 nums.sort(key=cmp_to_key(lambda a, b: 1 if a+b < b+a else -1))

5 result = ''.join(nums)

6 return '0' if result[0] == '0' else result

Why higher-order positions dominate: In the number "4321", the 4 in the thousands place contributes 4000 to the value. Even if we have a perfect "111" for the remaining digits, the 4 dominates. This is why construction greedy works: improving a higher-order position always outweighs any change to lower-order positions. The monotonic stack ensures we fix the highest-order position first.

Edge cases to handle:

• Input is already monotonically increasing (e.g., "12345", k=2): pop from end
• All digits are the same (e.g., "11111", k=3): trim k digits from end
• Result has leading zeros (e.g., "10200", k=1): lstrip('0')
• All digits removed (e.g., "10", k=2): return "0"

Interview Tip

Construction greedy overlaps with monotonic stack

If you see "remove digits to minimize/maximize a number" or "build the smallest/largest sequence," think monotonic stack first. The greedy criterion is: pop the stack top if it's worse than the incoming element (and you have budget left). This is the intersection of two patterns. Construction greedy uses the same stack logic as monotonic stack problems, with an additional removal budget.

Activity Selection: Deep Dive

Given a set of activities with start and end times, select the maximum number of non-overlapping activities. This is the textbook greedy problem and the foundation for understanding all scheduling greedy algorithms.

The greedy strategy: sort by end time, then scan left to right. For each activity, if it starts at or after the previous selection's end, select it.

Activity Selection: Sort by End Time

We have 11 activities with start/end times. Goal: select the maximum number of non-overlapping activities.

The brute force approach tries all 2^11 = 2048 subsets. Greedy does it in O(n log n).

Activity Selection

1def max_activities(activities):

2 # Sort by end time (the key greedy decision)

3 activities.sort(key=lambda x: x[1])

5 selected = [activities[0]]

6 last_end = activities[0][1]

8 for i in range(1, len(activities)):

9 start, end = activities[i]

10 if start >= last_end: # No overlap

11 selected.append(activities[i])

12 last_end = end

14 return len(selected)

16# Example: [(1,4), (3,5), (0,6), (5,7), (8,11), (12,16)]

17# Sorted by end: [(1,4), (3,5), (0,6), (5,7), (8,11), (12,16)]

18# Selected: (1,4), (5,7), (8,11), (12,16) = 4 activities

Why sort by end time? An activity that ends earlier is compatible with more future activities. If two activities are both compatible with the current selection, the one that ends earlier can never be worse because it leaves at least as much room for subsequent picks.

Why Other Sort Keys Fail

Alternative sort criteria produce wrong answers:

Sort by start time: Consider [(0, 100), (1, 2), (3, 4)]. Sorting by start picks the long activity first, blocking everything. Result: 1 activity instead of 2.
Sort by duration (shortest first): Consider [(0, 3), (2, 5), (4, 7)]. Shortest-first picks (0,3) then can't pick (2,5) due to overlap, then picks (4,7). Gets 2. But also consider [(0, 2), (1, 10), (2, 3)]. Shortest picks (0,2) and (2,3), getting 2. If we'd picked (1,10) we'd get only 1. Shortest happens to work here, but it fails on [(6, 8), (1, 9), (5, 7), (7, 9)]: shortest-first picks (5,7) then (7,9) = 2, but (6,8) works just as well. More importantly, it can miss optimal solutions on certain inputs.
Sort by fewest conflicts: Sounds smart, but fails. Example: activity B overlaps with A and C, but A and C don't overlap each other. B has 2 conflicts, A and C have 1 each. Fewest-conflicts picks A first (1 conflict), then C (1 conflict), both selected, B blocked. But if you add more activities that only overlap with A and C, their conflict counts rise above B's, and fewest-conflicts picks B instead, blocking both A and C. The optimal answer depends on global structure, not local conflict counts.

Common Mistake

Sorting by start time is wrong

Sorting by start time produces suboptimal selections. Consider activities [(0, 100), (1, 2), (3, 4)]. Sorting by start picks (0, 100) first, blocking everything else. Sorting by end picks (1, 2) and (3, 4), yielding two activities instead of one.

Variants You'll See

Activity selection appears in disguise across many interview problems:

Non-overlapping Intervals: "Minimum removals" = n - max_non_overlapping. Identical algorithm, different question framing.
Minimum Arrows to Burst Balloons: Each arrow pops all overlapping balloons. Number of arrows = number of non-overlapping groups.
Merge Intervals: Not greedy selection, but uses the same sort-by-start-then-merge pattern. Different problem structure but related intuition.

Key Insight

Why Earliest End Time Wins

Sort by end time. Always pick the earliest-ending activity. This blocks the fewest future options because it frees up the timeline sooner than any alternative.

Interview Tip

Always clarify the overlap definition

Does [1, 5] and [5, 8] count as overlapping? Some problems use start >= last_end (non-overlapping at boundary), others use start > last_end (overlapping at boundary). Clarify this with the interviewer before coding. Getting this wrong produces off-by-one errors.

Jump Game: Tracking Reachability

Given an array where each element represents the maximum jump length from that position, determine if you can reach the last index. This is the canonical reachability greedy problem and one of the most commonly asked greedy questions.

Reachability is a monotonic property. Once you know you can reach position i, you can also reach every position before i. And from position i, you can potentially extend your reach to i + nums[i]. This makes the problem perfectly suited for a single-variable greedy scan.

Jump Game: Farthest Reachable

Invariant: farthest = max reachable index from any position ≤ i

2i=0

3i=1

1i=2

1i=3

4i=4

Array: [2, 3, 1, 1, 4]. Can we reach the last index? Start with farthest = 0.

Key insight: if we can reach position i, we can potentially reach i + nums[i]. The farthest we can reach is max over all reachable positions.

The brute force tries every possible jump sequence (exponential). The greedy insight: track a single variable, farthest_reachable. At each position, update it. If it ever reaches the end, return true. If the current index exceeds it, return false.

Worked Example

nums = [2, 3, 1, 1, 4]. Can we reach index 4?

i=0: farthest = max(0, 0+2) = 2. Can reach positions 0, 1, 2.
i=1: 1 ≤ 2, reachable. farthest = max(2, 1+3) = 4. Can reach positions 0 through 4. 4 ≥ 4, return True!

Now consider nums = [3, 2, 1, 0, 4]. Can we reach index 4?

i=0: farthest = max(0, 0+3) = 3.
i=1: farthest = max(3, 1+2) = 3.
i=2: farthest = max(3, 2+1) = 3.
i=3: farthest = max(3, 3+0) = 3. Position 3 is a "zero trap."
i=4: 4 > 3. Return False. The zero at index 3 blocks progress.

Jump Game I: Greedy O(n)

1def can_jump(nums):

2 farthest = 0

3 for i in range(len(nums)):

4 if i > farthest:

5 return False # Can't reach this position

6 farthest = max(farthest, i + nums[i])

7 if farthest >= len(nums) - 1:

8 return True

9 return True

Why greedy works: If position i is reachable and nums[i] = k, then every position from i to i+k is reachable. Extending farthest_reachable captures all reachable positions without backtracking. No "better" choice exists; every jump that extends the reach should be considered.

Why Greedy Is Safe Here

The key invariant: if position i is reachable, then every position j ≤ i is also reachable (you can always jump shorter). This means the reachable set is always a contiguous prefix [0, farthest]. Once a position is reachable, it stays reachable forever. No future decision can "un-reach" a position. This monotonicity is what makes the greedy approach valid.

Contrast this with a problem like "minimum cost to reach the end" where different paths have different costs. There, reaching position i cheaply matters, not just reaching it. That's when DP is needed because the path cost affects future decisions. The distinction: reachability is a boolean property (reach or not), while minimum cost is a value property (what's the cheapest way). Boolean properties tend to be greedy; value properties tend to be DP.

Interview Tip

Many greedy problems collapse to a single variable

Many greedy problems that look like they need a set or array actually collapse to a single variable. Jump Game needs only maxReach. Gas Station needs only tank. Stock trading needs only minPrice.

Gas Station: Circular Greedy

There are n gas stations along a circular route. Station i has gas[i] fuel and costs cost[i] fuel to reach the next station. Find a starting station that lets you complete the full circuit, or determine that none exists.

The brute force is O(n²): try starting at each station and simulate the full trip. The greedy approach reduces this to O(n) with a single pass by exploiting two key insights about circular traversal and deficit accumulation.

Gas Station — Circular Route

Gas stations in a circle. gas=[1,2,3,4,5], cost=[3,4,5,1,2]. Find a starting station to complete the circuit.

Key insight: if total gas >= total cost, a solution always exists. We need to find WHERE to start.

Two key insights drive the solution:

If total gas < total cost, no solution exists. The car will always run out. Return -1.
If total gas ≥ total cost, start right after the worst deficit. Scan with a running tank. When the tank goes negative, reset: the new candidate start is the next station.

Gas Station: O(n)

1def can_complete_circuit(gas, cost):

2 if sum(gas) < sum(cost):

3 return -1 # Impossible

5 tank = 0

6 start = 0

7 for i in range(len(gas)):

8 tank += gas[i] - cost[i]

9 if tank < 0:

10 # Can't start from 'start' through 'i'

11 start = i + 1

12 tank = 0

14 return start

Worked Example

gas = [1, 2, 3, 4, 5], cost = [3, 4, 5, 1, 2]. Total gas = 15, total cost = 15. Solution exists.

Station 0: tank = 1 - 3 = -2. Negative! Reset: start = 1, tank = 0.
Station 1: tank = 2 - 4 = -2. Negative! Reset: start = 2, tank = 0.
Station 2: tank = 3 - 5 = -2. Negative! Reset: start = 3, tank = 0.
Station 3: tank = 4 - 1 = 3. Positive, continue.
Station 4: tank = 3 + 5 - 2 = 6. Positive. Answer: start = 3.

Verification starting from station 3: gas 4, cost 1 to reach station 4 (tank=3). Station 4: gas 5, cost 2 to reach station 0 (tank=6). Station 0: gas 1, cost 3 to reach station 1 (tank=4). Station 1: gas 2, cost 4 to reach station 2 (tank=2). Station 2: gas 3, cost 5 to reach station 3 (tank=0). Full circuit completed with exactly zero fuel to spare.

The tank never goes negative during this circuit. That is the key invariant: starting from the correct station, the accumulated surplus from stations 3 and 4 is enough to cover the deficits at stations 0, 1, and 2. The total gas equals total cost (both 15), so the circuit is barely feasible.

Key Insight

Why the Reset Works

If starting at A fails at B, starting at any station C between A and B also fails. Why? From A to C, the cumulative surplus was non-negative (otherwise we would have failed before C). Starting at C loses that surplus. Without it, the deficit at B is even worse. So skip directly to B+1.

Interview Tip

Always lead with the total check

Before explaining the reset logic, state: "First, if total gas is less than total cost, it's impossible." The global feasibility condition is the foundation the greedy reset builds on. Then explain the reset: "When the tank goes negative, I can't start from any earlier station, so I try the next one."

Task Scheduler: Frequency-First Greedy

Given tasks with a cooldown period n (same task must wait n intervals before repeating), find the minimum number of intervals to complete all tasks. This is a frequency-based greedy problem where the most constrained element (highest-frequency task) determines the answer structure.

The brute force simulates the schedule step by step, always picking the highest-frequency available task. This works but is slow for large inputs. The formula approach derives the answer directly from the frequency distribution, giving O(n) time where n is the number of tasks.

Task Scheduler: Frequency Grid

Example 1 — Idle slots remain

AAABBB

Tasks: A×3, B×3. Cooldown n=2: same task must wait 2 slots before repeating. Find the minimum number of intervals.

The most frequent task determines the structure. Everything else fills around it.

The most frequent task determines the structure. With max frequency f and cooldown n:

Task Scheduler: O(n)

1def least_interval(tasks, n):

2 from collections import Counter

4 freq = Counter(tasks)

5 max_freq = max(freq.values())

6 # How many tasks have the maximum frequency

7 max_count = sum(1 for v in freq.values() if v == max_freq)

9 # (max_freq - 1) frames of size (n+1), plus the tail

10 formula_result = (max_freq - 1) * (n + 1) + max_count

12 # If we have many diverse tasks, no idle time needed

13 return max(len(tasks), formula_result)

The formula explained: The most frequent task creates (max_freq - 1) "frames" of size (n + 1). Each frame has one occurrence of the max-frequency task, followed by n cooldown slots. Less frequent tasks fill the gaps. If there are enough diverse tasks to fill all gaps, no idle time is needed, and the answer is simply len(tasks).

Worked Example

Tasks = [A, A, A, B, B, C], cooldown n = 2.

Max frequency: A appears 3 times. max_freq = 3.
Tasks at max frequency: Only A. max_count = 1.
Frame calculation: (3 - 1) × (2 + 1) + 1 = 2 × 3 + 1 = 7.
Total tasks: 6. max(6, 7) = 7.
Schedule: A B C A B _ A. The underscore is idle time.

Now consider Tasks = [A, A, A, B, B, B, C, C, D], cooldown n = 2. max_freq = 3 (A and B), max_count = 2. Formula: (3-1) × (2+1) + 2 = 8. Total tasks = 9. max(9, 8) = 9. No idle time needed because we have enough diverse tasks to fill all gaps: A B C A B D A B _.

Key Insight

Task Scheduler Formula

Formula: (max_freq - 1) x (n + 1) + max_count. The most frequent task creates (max_freq - 1) groups of size (n + 1). The last group has max_count tasks sharing the highest frequency. If formula < len(tasks), the answer is len(tasks) because no idle time is needed.

Interview Tip

Two valid approaches: formula vs simulation

The formula approach is O(n) and elegant. The simulation approach uses a max heap: pop the most frequent task, decrement its count, add it to a cooldown queue, and repeat. Both are valid. The formula is faster to code; the simulation is more intuitive to explain. Choose based on what you're more comfortable with under pressure.

Remove K Digits: Monotonic Construction

Given a non-negative integer represented as a string, remove k digits to make the smallest possible number. This is a construction greedy problem that uses a monotonic stack. It demonstrates where greedy and monotonic stack patterns converge.

The brute force approach tries all C(n, k) combinations of digits to remove, checking which produces the smallest number. For "1432219" with k=3, that's C(7,3) = 35 combinations. For larger inputs (n=100, k=20), that's C(100,20) ≈ 5 × 10²⁰ combinations, which is intractable. The greedy approach does it in O(n) time with a single left-to-right pass, handling any input size efficiently.

The greedy insight: Higher-order positions (leftmost digits) have the most impact on the number's value. If a digit is larger than the one following it, removing it produces a smaller number because the smaller digit "shifts left" into a higher-order position.

Remove K Digits — Monotonic Stack

Input: "1432219" k = 3

Stack (left = bottom)

∅

Removals left: 3

Remove K Digits: remove 3 digits from "1432219" to make the smallest number.

Greedy insight: at each position, remove digits that are larger than the next digit. Higher-order positions dominate.

Step-by-step trace for "1432219", k=3:

Push 1. Stack: [1].
Push 4. 4 > 1, no pop. Stack: [1, 4].
Next is 3. Pop 4 (4 > 3, k=2). Push 3. Stack: [1, 3].
Next is 2. Pop 3 (3 > 2, k=1). Push 2. Stack: [1, 2].
Push 2. 2 ≤ 2, no pop. Stack: [1, 2, 2].
Next is 1. Pop 2 (2 > 1, k=0). Push 1. Stack: [1, 2, 1].
Push 9. k=0, no more pops. Stack: [1, 2, 1, 9].

Result: "1219". All 3 removals were used optimally. Each removal replaced a larger digit in a higher-order position with a smaller digit, producing the smallest possible number. The pops occurred at positions 2, 3, and 5. The monotonic stack handled each case correctly without any backtracking or lookahead.

If k removals remain after processing all digits, trim from the end of the stack. This handles cases like "12345" with k=2: no digit is ever larger than the next, so no pops occur during the scan, and we trim "45" from the end to get "123".

Remove K Digits: O(n)

1def remove_k_digits(num, k):

2 stack = []

3 for digit in num:

4 while stack and k > 0 and stack[-1] > digit:

5 stack.pop()

6 k -= 1

7 stack.append(digit)

9 # If k removals remain, trim from the end

10 if k > 0:

11 stack = stack[:-k]

13 # Remove leading zeros

14 return ''.join(stack).lstrip('0') or '0'

Key Insight

Monotonic Stack for Digit Construction

While stack top > current digit and k > 0, pop. Push current digit. Popping a larger digit for a smaller one reduces the number. Higher-order positions dominate, so fix leftmost first. The budget k limits total removals.

Why the Greedy Criterion Works

The greedy criterion for Remove K Digits is: "if the current stack top is larger than the incoming digit, remove it." Why is this safe? Because the stack top occupies a higher-order position than the incoming digit would if the top stays. A larger digit in a higher-order position contributes more to the number's value. Replacing it with a smaller digit at that position always reduces the number, regardless of what comes after.

The intuition: any solution that keeps a larger digit before a smaller one at position i could be improved by removing the larger digit (if k allows). Therefore, the monotonic stack approach produces an optimal result.

Connection to Monotonic Stack Pattern

Remove K Digits sits at the intersection of greedy and monotonic stack. The stack maintains a non-decreasing sequence of digits. When a smaller digit arrives, it retroactively "fixes" the sequence by popping larger digits. This is the same mechanism used in:

Next Greater Element: monotonic decreasing stack, but the goal is finding the next larger element rather than building a result.
Largest Rectangle in Histogram: monotonic increasing stack of heights, popping when a shorter bar arrives.
Create Maximum Number: uses the same "pick best k elements" subroutine from two arrays, then merges them greedily.

Construction greedy reduces to monotonic stack operations with a removal budget constraint. The budget constrains how many pops you can do.

Interview Tip

Construction greedy always needs post-processing

When building a result string or sequence greedily, you're almost never done after the main loop. There's usually cleanup: strip leading zeros, handle the empty-result edge case, or reverse what you built. Identify the post-processing step early and handle it before returning.

Common Pitfalls

Greedy bugs are insidious because the code runs without errors, but the output is wrong. Most bugs fall into one of these six categories. Each one includes the wrong approach, the correct approach, and why the fix works.

Common Mistake

Pitfall 1: Sorting by the wrong key

Activity selection must sort by end time, not start time. This is the most common greedy bug. Sorting by start time picks long activities first, blocking shorter compatible ones.

Wrong vs Right: Sort Key

1# WRONG: Sort by start time

2activities.sort(key=lambda x: x[0])

3# With [(0, 100), (1, 2), (3, 4)]: picks (0, 100) first, gets 1 activity

5# RIGHT: Sort by end time

6activities.sort(key=lambda x: x[1])

7# With [(0, 100), (1, 2), (3, 4)]: picks (1, 2) then (3, 4), gets 2 activities

Common Mistake

Pitfall 2: Off-by-one in reachability

In Jump Game, the order of the check and update matters. Checking after updating means the condition can never trigger.

Wrong vs Right: Check Order

1# WRONG: update before check

2farthest = max(farthest, i + nums[i])

3if i > farthest: # This can never be true after the update!

4 return False

6# RIGHT: check before update

7if i > farthest:

8 return False

9farthest = max(farthest, i + nums[i])

Common Mistake

Pitfall 3: Forgetting max_count in Task Scheduler

When multiple tasks share the maximum frequency, the tail of the schedule contains all of them, not just one. Forgetting max_count underestimates the answer.

Wrong vs Right: Tail Count

1# WRONG: Only counts 1 task in the tail

2formula = (max_freq - 1) * (n + 1) + 1

4# RIGHT: Counts ALL tasks that share the max frequency

5max_count = sum(1 for v in freq.values() if v == max_freq)

6formula = (max_freq - 1) * (n + 1) + max_count

Common Mistake

Pitfall 4: Applying greedy to DP problems

The most dangerous greedy mistake isn't a code bug: it's applying greedy to a problem that requires DP. If the locally optimal choice can lead to a globally suboptimal result, greedy is wrong. Here are the most common traps:

Wrong vs Right: Problem Selection

1# WRONG: Greedy coin change with arbitrary denominations

2def coin_change_greedy(coins, amount):

3 coins.sort(reverse=True)

4 count = 0

5 for coin in coins:

6 count += amount // coin

7 amount %= coin

8 return count # Returns 3 for coins=[1,3,4], amount=6 (wrong!)

10# RIGHT: DP coin change

11def coin_change_dp(coins, amount):

12 dp = [float('inf')] * (amount + 1)

13 dp[0] = 0

14 for i in range(1, amount + 1):

15 for coin in coins:

16 if coin <= i:

17 dp[i] = min(dp[i], dp[i - coin] + 1)

18 return dp[amount] if dp[amount] != float('inf') else -1 # Returns 2

How to catch this: Before coding, try your greedy approach on 2-3 small inputs. If any input gives a wrong answer, greedy is invalid. For coin change, [1, 3, 4] with target 6 is the canonical counterexample.

Common Mistake

Pitfall 5: Leading zeros in construction greedy

Remove K Digits can produce results with leading zeros. For example, "10200" with k=1 should give "200", not "0200". Forgetting to strip leading zeros is a common edge case. This also affects "10" with k=1 (should return "0", not empty string) and "10" with k=2 (should return "0").

Wrong vs Right: Leading Zeros

1# WRONG: No leading zero removal

2result = ''.join(stack[:len(stack) - k])

3return result # Could return "0200"

5# RIGHT: Strip leading zeros, handle empty result

6result = ''.join(stack[:len(stack) - k])

7return result.lstrip('0') or '0' # Returns "200"

9# Also handle when all digits are removed:

10# "10" with k=2 -> stack=[], result="" -> lstrip('0')="" -> or '0' -> "0"

Common Mistake

Pitfall 6: Missing total feasibility check in circular greedy (Gas Station)

Gas Station requires checking total gas vs total cost before running the greedy scan. Without this check, the reset logic can report a valid start when none exists.

Wrong vs Right: Feasibility Check

1# WRONG: No total check

2def can_complete(gas, cost):

3 tank = 0

4 start = 0

5 for i in range(len(gas)):

6 tank += gas[i] - cost[i]

7 if tank < 0:

8 start = i + 1

9 tank = 0

10 return start # May return invalid start!

12# RIGHT: Check total first

13def can_complete(gas, cost):

14 if sum(gas) < sum(cost):

15 return -1 # Impossible: not enough fuel overall

16 tank = 0

17 start = 0

18 for i in range(len(gas)):

19 tank += gas[i] - cost[i]

20 if tank < 0:

21 start = i + 1

22 tank = 0

23 return start

Why this matters: Without the total check, the algorithm can return start = n (one past the last station) or a valid-looking but incorrect station. The total check is O(n) and should be the first line of your solution. Some implementations combine the total check with the scan by tracking both a running tank and a total surplus, which avoids iterating twice.

Key Insight

Debug checklist for greedy bugs

When your greedy solution gives wrong answers, check these in order: 1. Is the sort key correct? (Most common bug in scheduling greedy) 2. Is the comparison using > or ≥ consistently? (Off-by-one at boundaries) 3. Does the greedy choice actually work on this problem? (Try 3 small counterexamples) 4. Are edge cases handled? (Empty input, single element, all same values, leading zeros) 5. Is the feasibility check present? (Gas station total, reorganize string max_freq)

Practice Problems

Problems are grouped by greedy category and ordered by difficulty within each group. Start with the Easy problems to build intuition, then progress through Medium and Hard.

Scheduling / Selection

Problem	Difficulty	Approach
Non-overlapping Intervals	Medium	Sort by end time, count removals. This is activity selection in disguise: max non-overlapping = n - removals. Greedy criterion: earliest-ending interval is always safe to keep.
Minimum Number of Arrows	Medium	Sort by end, one arrow covers all overlapping balloons. Each new non-overlapping balloon needs a new arrow. Key: the arrow placement is at the end of the earliest-ending balloon in each group.
Meeting Rooms II	Medium	Not pure greedy. Sweep line or min-heap for simultaneous overlap count. Sort by start time, track room freeing via heap. The greedy here is: always reuse the room that frees earliest.
Minimum Interval to Include Query	Hard	Sort intervals and queries. Use a heap to track active intervals, greedily pick the smallest valid one for each query.

Reachability / Coverage

Problem	Difficulty	Approach
Jump Game	Medium	Track farthest reachable index with a single variable. Every reachable position extends the frontier. O(n) time, O(1) space. If current index exceeds farthest, there's a gap.
Jump Game II	Medium	BFS-like: maintain current range [start, end], expand to farthest in that range. Each expansion = one jump. O(n) time, O(1) space.
Video Stitching	Medium	Sort clips by start time. At each point, greedily pick the clip starting at or before current position that extends coverage the farthest. Classic interval coverage.
Minimum Taps to Water Garden	Hard	Convert taps to intervals [i-ranges[i], i+ranges[i]], then apply video stitching. The reduction to interval coverage is the key insight.

Resource Allocation

Problem	Difficulty	Approach
Assign Cookies	Easy	Sort both children by greed factor and cookies by size. Match smallest cookie to smallest satisfiable child. Two-pointer after sort. O(n log n).
Lemonade Change	Easy	Greedy change-making: prefer $10 bills over $5s when making change for $20 (using a $10+$5 saves more $5 bills for future $10 customers).
Gas Station	Medium	Total surplus check + deficit reset. If starting from A fails at B, every station between A and B also fails because the deficit only grows.
Task Scheduler	Medium	Frequency-first formula: (max_freq-1) * (n+1) + max_count. The most frequent task creates mandatory cooldown frames. Less frequent tasks fill gaps.
Candy	Hard	Two passes: left-to-right ensures each child gets more candy than a lower-rated left neighbor. Right-to-left does the same for right neighbors. Take max of both passes per child.

Construction / Ordering

Problem	Difficulty	Approach
Remove K Digits	Medium	Monotonic stack: remove digit if larger than next. Each pop maximally reduces the number at the highest possible position. Don't forget lstrip('0') and the empty result edge case.
Largest Number	Medium	Custom comparator: compare a+b vs b+a as strings. This total ordering produces the lexicographically largest concatenation. Handle the all-zeros edge case (return "0" not "000").
Reorganize String	Medium	Frequency-first placement with max-heap. Place most frequent char first, then interleave. Impossible if max_freq > (n+1)/2.
Create Maximum Number	Hard	Combine monotonic stack (pick best k digits from one array) with merge (combine two subsequences greedily). Try all splits of k between the two arrays.

Mixed / Advanced

Problem	Difficulty	Approach
Best Time to Buy/Sell Stock II	Medium	Add every upswing: if prices[i] > prices[i-1], add the difference. Greedy because each day's profit decision is independent of future decisions.
Partition Labels	Medium	Track last occurrence of each character. Extend current partition to include the last occurrence of every character seen. Pure scan-and-extend greedy.
Queue Reconstruction by Height	Medium	Sort descending by height, then insert at the k-index. Tallest people are placed first and shorter people slot in without affecting tall people's k-values.
Minimum Cost to Connect Sticks	Medium	Always merge the two smallest sticks first (min-heap). Greedy by Huffman coding principle: minimize total cost by doing cheap operations early.

Summary: When to Use Each Pattern

Pattern	Time	Space	Best For
Sort + scan greedy	O(n log n)	O(1)	Interval selection, scheduling
Single-variable greedy	O(n)	O(1)	Reachability, running totals, stock prices
Frequency formula	O(n)	O(1)	Task scheduling, string reorganization
Monotonic stack greedy	O(n)	O(n)	Digit removal, largest/smallest number construction
Custom comparator sort	O(n log n)	O(1)	Largest number, custom orderings
Two-pointer greedy	O(n)	O(1)	Cookie assignment, boat pairing

Test Your Understanding

12 questions covering greedy choice property, correctness verification, and common traps.

Practice this pattern

Apply the guide to complete interview problems with explanations and code.

Jump Game Gas Station Assign Cookies

Learn Greedy Algorithms in a guided sequence

The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.

Explore the course

Dynamic Programming Heaps and Priority Queues

Greedy Algorithms

What Is a Greedy Algorithm?

Greedy vs DP: Decision Tree

Three Greedy Mechanisms

Greedy vs Dynamic Programming

Greedy vs DP: Coin Change

When to Use Greedy

Complexity Comparison by Problem

From Brute Force to Greedy

Attempt 1: Brute Force Subset Enumeration

Attempt 2: DP with Sorted Activities

Attempt 3: Greedy Collapse

Recognizing Greedy Problems

Quick Category Identification

Greedy Templates

Scheduling / Selection

Reachability / Coverage

Resource Allocation

Construction / Ordering

Activity Selection: Deep Dive

Activity Selection: Sort by End Time

Why Other Sort Keys Fail

Variants You'll See

Jump Game: Tracking Reachability

Jump Game: Farthest Reachable

Worked Example

Why Greedy Is Safe Here

Gas Station: Circular Greedy

Gas Station — Circular Route

Worked Example

Task Scheduler: Frequency-First Greedy

Task Scheduler: Frequency Grid

Worked Example

Remove K Digits: Monotonic Construction

Remove K Digits — Monotonic Stack

Why the Greedy Criterion Works

Connection to Monotonic Stack Pattern

Common Pitfalls

Practice Problems

Scheduling / Selection

Reachability / Coverage

Resource Allocation

Construction / Ordering

Mixed / Advanced

Summary: When to Use Each Pattern

Test Your Understanding

Practice this pattern

Learn Greedy Algorithms in a guided sequence

Related patterns