Pattern #32

Greedy Algorithms

Important interview questions, thinking patterns, Activity Selection, Jump Game, Gas Station, exchange argument proofs, and Go rules.

Must Solve

20 core questions — solve these first.

1.Best Time to Buy and Sell Stock II
Greedy: Accumulate all positive daily price differences (prices[i] - prices[i-1])medium
2.Jump Game
Greedy: Track max reachable index (farthest = max(farthest, i + nums[i]))medium
3.Jump Game II
Greedy levels: Update currentEnd = farthest when i reaches currentEndmedium
4.Gas Station
Greedy reset: If tank < 0 at station i, skip whole failed segment 0..i (start = i+1)medium
5.Candy
Two-pass greedy: Left-to-right pass + Right-to-left pass taking max candieshard
6.Assign Cookies
Sort greed & cookie sizes + 2 pointers matching smallest effective cookieeasy
7.Lemonade Change
Greedy change: Prefer giving $10 + $5 over three $5 bills for $20easy
8.Non-overlapping Intervals
Sort by END time + keep earliest finishing interval (removals = N - kept)medium
9.Minimum Number of Arrows to Burst Balloons
Sort by END time + shoot arrow at earliest balloon end positionmedium
10.Partition Labels
Track last index of each char + extend partition boundary end = max(end, last[char])medium
11.Task Scheduler
Greedy math on max task frequency or Max Heap + cooldown queuemedium
12.Queue Reconstruction by Height
Sort height DESC, k ASC + insert person at index k in result listmedium
13.Boats to Save People
Sort + 2 pointers: Pair heaviest person with lightest if weight <= limitmedium
14.Can Place Flowers
Single pass checking left, current, right zero conditionseasy
15.Maximum Units on a Truck
Sort box types by units per box DESC + greedy truck capacity fillingeasy
16.Bag of Tokens
Sort + 2 pointers: Buy score with lowest power (left), buy power with highest score (right)medium
17.Remove K Digits
Monotonic Stack + Greedy: Pop larger previous digits when smaller arrivesmedium
18.Reorganize String
Max Heap of char counts + alternate most frequent charactersmedium
19.Hand of Straights
TreeMap / HashMap count + greedily build consecutive groups of size groupSizemedium
20.Minimum Cost to Connect Sticks
Min Heap: Repeatedly pop and combine two smallest sticks (Huffman coding)medium

Also Important

10 more questions worth practicing.

21.Two City Scheduling
Sort by refund cost difference (costA - costB) + Send first N to A, rest to Bmedium
22.Maximum Length of Pair Chain
Sort pairs by end time + Greedy activity selectionmedium
23.Wiggle Subsequence
Greedy peak & valley direction countingmedium
24.Valid Parenthesis String
Greedy min & max open parenthesis bounds [minOpen, maxOpen]medium
25.Minimum Deletions to Make Character Frequencies Unique
HashSet of used frequencies + decrement frequency until uniquemedium
26.Furthest Building You Can Reach
Min Heap of brick jumps + replace smallest jumps with ladders when bricks run outmedium
27.IPO
Sort projects by capital + Max Heap for available profitshard
28.Minimum Number of Refueling Stops
Max Heap of passed fuel station capacitieshard
29.Course Schedule III
Sort courses by deadline ASC + Max Heap of course durations (replace longest when over deadline)hard
30.Activity Selection Problem
Classic Greedy: Sort by end time + pick earliest finishing activitymedium

How to Think

Need best local choice each step?Greedy Algorithm
Need maximum non-overlapping intervals?Sort by END time + Greedy selection
Need minimum resources / cost?Take cheapest / earliest / best available
Can current bad decision be fixed later?No! Greedy commits permanently without undo
Problem says max/min and sorting helps?Strong hint: Sort + Greedy

Go Activity Selection Template (Sort by End)

Standard Greedy Activity Selection in Go

import (
    "math"
    "sort"
)

func maxActivities(intervals [][]int) int {
    // 1. Sort by END time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })

    lastEnd := math.MinInt
    count := 0

    // 2. Pick activity that finishes earliest
    for _, interval := range intervals {
        if interval[0] >= lastEnd {
            count++
            lastEnd = interval[1]
        }
    }
    return count
}

👉 Total Time: O(N log N) | Space: O(1)

Greedy Proof & Coin Change Counterexample

A local best choice does NOT automatically mean global optimal! Consider making amount 6 using coins [1, 3, 4]:

❌ Greedy Choice (Take largest coin first)

Take 4 $\to$ Remainder 2 $\to$ Take 1 + 1. Total = 3 coins (4 + 1 + 1).

✅ Optimal Choice (Dynamic Programming)

Take 3 + 3. Total = 2 coins (3 + 3). Greedy fails!

👉 Exchange Argument Rule: Explain WHY choosing the local best now will not hurt future options!

Greedy vs Backtracking vs Dynamic Programming

Greedy

Pick local best NOW, commit permanently, NO UNDO. Fast O(N) or O(N log N).

Backtracking

Try choice, explore recursively, UNDO (backtrack) if it fails. Exponential time.

Dynamic Programming

Compare choices across OVERLAPPING SUBPROBLEMS when local choices are unsafe.

Visual Memory Rule

Best Choice NOW  →  Commit Permanently  →  Never Undo Choice
Jump Game        →  Track farthest reach = max(farthest, i + nums[i])
Gas Station      →  Skip failed segment 0..i -> start = i + 1
Activity Selection → Sort by END time (earliest finish leaves max space)

💡 Golden Rule: "Make the choice that leaves the future with the best possible options."

Common Interview Mistakes

1. Assuming Greedy Always Works

Using greedy on problems where local choices hurt future options (like 0/1 Knapsack or Unbounded Coin Change).

2. Sorting by Start Instead of End

Sorting by start time for Non-overlapping Intervals. Greedy selection requires sorting by END time.

3. Overcomplicating with Heavy DP

Writing an O(N²) DP solution for Jump Game or Gas Station when a simple O(N) Greedy pass exists!

4. Saying "Greedy Because I Take the Biggest"

Vague explanations in interviews. Always state why taking the earliest finishing or highest unit item leaves the future no worse!

Interview Rules

1. Best local choice each step? → Consider Greedy Algorithm
2. Sorting reveals order? → Sort by end time, cost, profit, or weight first
3. Intervals + max count? → Sort by END time (earliest finish)
4. Farthest reachability? → Jump Game (farthest = max(farthest, i + nums[i]))
5. Minimum removals? → Maximize kept items (removals = N - kept)
6. Dynamic best choice needed? → Greedy + Priority Queue (Min/Max Heap)
7. Need undoing choices? → Use Backtracking instead of pure Greedy
8. Overall Complexity → Typically O(N) or O(N log N)

Small Rules

Rule 1: Greedy commits immediately without undoing choices.
Rule 2: Sorting data first often reveals the optimal greedy ordering.
Rule 3: Explain WHY taking a choice cannot hurt future choices (Exchange Argument).
Rule 4: Transform problems (e.g. minimum removals = total - maximum non-overlapping kept).
Rule 5: Combine Greedy with Heaps when best candidates change dynamically (e.g. IPO, Refueling Stops).

Production Thinking

Earliest Deadline First Scheduler → Schedule real-time OS background tasks by nearest deadline ASC

Resource Capacity Allocation → Allocate smallest available worker pool node that satisfies request requirements

Network Routing (Dijkstra) → Greedily pick currently closest unvisited node (works for non-negative edge weights)

Batch Job Processing → Process highest unit value or smallest duration jobs first to maximize throughput

Remember This

Greedy               → Best choice NOW
Usually              → No undo
Intervals            → Earliest end
Jump Game            → Farthest reach
Dynamic best choice  → Heap
Need ordering        → Sort first
Local best           ≠ always global best
Must explain         → Why choice is safe

💡 Golden Rule: "Make the choice that leaves the future with the best possible options."