PATTERN 15 OF 22

Greedy

Greedy algorithms make the locally optimal choice at each step, expecting it to lead to the globally optimal solution. Master reachability scanning, circular deficit tracking, greedy grouping, and partition extension to solve problems that reward choosing the best immediate option.

Time: O(n) for single-pass greedy, O(n log n) when sorting is required

Space: O(1) for most greedy algorithms, O(n) when counting/sorting is needed

Learn & Reference

Understanding the Pattern

Greedy Pattern

Greedy algorithms build solutions piece by piece, always choosing the option that looks best right now. Unlike DP, which considers all possibilities, greedy commits to each choice and never backtracks.

Greedy:  Choose best now → move forward → never reconsider
DP:      Consider all options → pick the best overall

The key question: does the locally optimal choice lead to the globally optimal solution? If yes, greedy works and is usually much simpler and faster than DP.

When Greedy Works

A problem has the greedy choice property if making the locally optimal choice at each step produces a globally optimal solution. Two ways to verify:

Greedy stays ahead: Show that after each step, the greedy solution is at least as good as any other.
Exchange argument: If an optimal solution differs from greedy at some step, show that swapping to the greedy choice doesn't make it worse.

Five Core Techniques

1. Greedy Reachability

Track the farthest position you can reach. Scan left to right, extending the frontier.

nums = [2, 3, 1, 1, 4]

i=0: farthest = max(0, 0+2) = 2
i=1: farthest = max(2, 1+3) = 4  ← reached end!
→ true

When to use: "Can you reach the end?", "Is it possible to get from A to B?"

2. BFS-Level Greedy

Treat the problem like BFS where each "level" is one decision. Track the current level boundary and the farthest you can reach from this level.

nums = [2, 3, 1, 1, 4]

Level 0: i=0, reach [1,2]     → jumps = 1, currentEnd = 2
Level 1: i=1,2, reach [4]     → jumps = 2, reached end!
→ 2 jumps

When to use: "Minimum number of steps/jumps to reach the end"

3. Circular Deficit Tracking

For circular problems, compute the running surplus/deficit. The optimal starting point is just after the deepest deficit.

gas  = [1, 2, 3, 4, 5]
cost = [3, 4, 5, 1, 2]
diff = [-2,-2,-2, 3, 3]   total = 0 (feasible)

Running sum: -2, -4, -6, -3, 0
                      ↑ deepest deficit at i=2
→ start at i=3

When to use: "Circular route", "starting point on a loop", "can you complete the circuit?"

4. Greedy Grouping from Minimum

Always start building groups from the smallest available element. Correctness: the smallest element must belong to some group, and its group must start with it.

hand = [1, 2, 3, 6, 2, 3, 4, 7, 8], groupSize = 3

Sorted: [1, 2, 2, 3, 3, 4, 6, 7, 8]
Group from 1: [1, 2, 3] ✓
Group from 2: [2, 3, 4] ✓
Group from 6: [6, 7, 8] ✓
→ true

When to use: "Divide into consecutive groups", "arrange in sets of K"

5. Greedy Partitioning

Scan left to right, extending each partition's boundary to include all occurrences of its characters. Close the partition at the earliest valid point.

s = "ababcbacadefegdehijhklij"

Last index: a→8, b→5, c→7, d→14, e→15, f→11, ...
Scan: extend to 8, then 5, 7, 5, 7, 5, 8, 7, 8 → close at 8 (size 9)
      extend to 14, 15, 11, 15, 14, 14, 15 → close at 15 (size 7)
      ...
→ [9, 7, 8]

When to use: "Partition string so each letter appears in at most one part", "maximum number of segments"

Common Mistakes

Applying greedy when DP is needed — Greedy fails for Coin Change with arbitrary denominations (e.g., coins [1, 3, 4], amount 6: greedy picks 4+1+1=3 coins, optimal is 3+3=2 coins). Always verify the greedy choice property.
Not sorting when order matters — Hand of Straights and many interval problems require sorting first. Greedy on unsorted input gives wrong answers.
Off-by-one in reachability — When checking farthest >= n-1 (not n), and iterating i < n-1 (not n) to avoid checking past the goal.
Circular array confusion — In gas station, when the tank goes negative, reset start to i+1 (not i). The current station is proven bad, the next one might work.
Confusing "can reach" with "minimum steps" — Jump Game (reachability) and Jump Game II (BFS-level) look similar but use different greedy strategies. Don't mix them up.

When to Use

The problem asks can you reach or is it possible — try greedy reachability

You need the **minimum number of steps/jumps/moves** — try BFS-level greedy

The problem involves a **circular array** or starting point on a loop — try deficit tracking

You need to **divide/group elements** into consecutive or equal-sized groups — try greedy from minimum

You need to **partition a string** so each character appears in only one part — try greedy partitioning

The problem has an obvious **locally optimal choice** that doesn't need to be reconsidered

Keywords: minimum jumps, can you reach, circular route, partition, maximum number of non-overlapping, earliest/latest

Template

1# --- Greedy Reachability Template ---
2def solve(nums):
3    farthest = 0
4    for i in range(len(nums)):
5        if i > farthest:
6            return False  # Can't reach this position
7        farthest = max(farthest, i + nums[i])
8    return True  # Can reach the end
9
10# --- Greedy Scan Template ---
11def greedy_scan(items):
12    result = 0
13    # Sort if order matters
14    # items.sort()
15
16    for item in items:
17        # Make the locally optimal choice
18        # Update result / state
19        pass
20
21    return result

{ }

Syntax Reference

1# --- Sorting ---
2nums.sort()                          # In-place sort O(n log n)
3sorted_nums = sorted(nums)          # New sorted list
4
5# --- Counting ---
6from collections import Counter
7count = Counter(nums)                # {val: freq}
8count[val] -= 1                      # Decrement
9if count[val] == 0: del count[val]  # Remove zero entries
10
11# --- Greedy scan ---
12farthest = 0
13for i in range(len(nums)):
14    if i > farthest: return False    # Stuck
15    farthest = max(farthest, i + nums[i])
16
17# --- Min / Max ---
18farthest = max(farthest, i + nums[i])
19total = sum(nums)

📋

Common Recipes

1# Recipe 1: Greedy Reachability (Jump Game)
2def can_jump(nums):
3    farthest = 0
4    for i in range(len(nums)):
5        if i > farthest:
6            return False
7        farthest = max(farthest, i + nums[i])
8    return True
9
10# Recipe 2: Circular Deficit (Gas Station)
11def can_complete_circuit(gas, cost):
12    total_tank = 0
13    curr_tank = 0
14    start = 0
15    for i in range(len(gas)):
16        diff = gas[i] - cost[i]
17        total_tank += diff
18        curr_tank += diff
19        if curr_tank < 0:
20            start = i + 1
21            curr_tank = 0
22    return start if total_tank >= 0 else -1
23
24# Recipe 3: Greedy Grouping (Hand of Straights)
25def is_n_straight_hand(hand, group_size):
26    if len(hand) % group_size != 0:
27        return False
28    count = Counter(sorted(hand))
29    for card in sorted(count):
30        while count[card] > 0:
31            for i in range(card, card + group_size):
32                if count[i] <= 0:
33                    return False
34                count[i] -= 1
35    return True

O(n)

Complexity

Technique	Time	Space	Example
Reachability scan	O(n)	O(1)	Jump Game
BFS-level greedy	O(n)	O(1)	Jump Game II
Circular deficit	O(n)	O(1)	Gas Station
Greedy grouping	O(n log n)	O(n)	Hand of Straights
Greedy partitioning	O(n)	O(1)	Partition Labels

Watch Out

✗Applying greedy when DP is needed — Greedy fails for Coin Change with arbitrary denominations (e.g., coins [1, 3, 4], amount 6: greedy picks 4+1+1=3 coins, optimal is 3+3=2 coins). Always verify the greedy choice property.
✗Not sorting when order matters — Hand of Straights and many interval problems require sorting first. Greedy on unsorted input gives wrong answers.
✗Off-by-one in reachability — When checking `farthest >= n-1` (not `n`), and iterating `i < n-1` (not `n`) to avoid checking past the goal.
✗Circular array confusion — In gas station, when the tank goes negative, reset start to `i+1` (not `i`). The current station is proven bad, the next one might work.
✗Confusing "can reach" with "minimum steps" — Jump Game (reachability) and Jump Game II (BFS-level) look similar but use different greedy strategies. Don't mix them up.

PRACTICE PROBLEMS

Dynamic Programming (1D)

Intervals