PATTERN 9: Greedy Algorithms

Qubits of DPK

April 11, 2026

Core DSA

Pattern 9 is where interviewers test judgment, not coding speed.

Many candidates use greedy.

Very few can justify greedy.

Core Idea (lock this)

“Make a locally optimal choice that leads to a globally optimal solution.”

Greedy works only when a proof exists.

Otherwise, it lies.

How to Recognize This Pattern (CRITICAL)

Think Greedy when:

You’re selecting or scheduling
You see:
Sorting suddenly feels necessary
DP feels like overkill

If local choice can be proven safe → greedy.

30 MUST-DO INTERVIEW PROBLEMS

(10 Easy → 10 Medium → 10 Hard)

EASY (1–10): Greedy Intuition Builders

Goal: build trust in greedy decisions.

#
Assign Cookies – LC 455
#
Lemonade Change – LC 860
#
Can Place Flowers – LC 605
#
Split a String in Balanced Strings – LC 1221
#
Minimum Cost to Move Chips – LC 1217
#
Minimum Difference Between Highest and Lowest of K Scores – LC 1984
#
Boats to Save People – LC 881
#
Minimum Operations to Make Array Increasing – LC 1827
#
Jump Game – LC 55
#
Maximum Units on a Truck – LC 1710

After these:

You should feel when greedy "just works".

️ MEDIUM (11–20): Greedy + Proof

English explanation must include why this choice is safe.

#
Jump Game II – LC 45
#
Gas Station – LC 134
#
Partition Labels – LC 763
#
Remove K Digits – LC 402
#
Candy – LC 135
#
Course Schedule III – LC 630
#
Reorganize String – LC 767
#
Hand of Straights – LC 846
#
Task Scheduler – LC 621
#
Minimum Number of Taps to Water Garden – LC 1326

Interviewers listen for:

"Why not another choice?"

HARD (21–30): Greedy with Constraints

These separate thinking from memorizing.

#
Job Sequencing with Deadlines – GFG
#
Minimum Number of Refueling Stops – LC 871
#
Maximum Performance of a Team – LC 1383
#
Non-overlapping Intervals – LC 435
#
Minimum Number of Arrows to Burst Balloons – LC 452
#
IPO – LC 502
#
Car Fleet – LC 853
#
Advantage Shuffle – LC 870
#
Minimum Initial Energy to Finish Tasks – LC 1665
#
Smallest Range Covering K Lists – LC 632

These require:

Sorting + priority queue
Strong justification
Calm reasoning

THE ONE SENTENCE THAT WINS GREEDY INTERVIEWS

Practice saying:

“This greedy choice is optimal because it leaves the most room for future decisions.”

That line signals maturity.

Common Interview Killers

Using greedy when DP is required
No proof / intuition explanation
Wrong sorting criteria
Confusing greedy with two pointers

INTERVIEW REVISION CARD — Pattern 9

1️⃣ Pattern in One Line

"Make the locally optimal choice at each step — but only when you can prove it leads to the global optimum."

2️⃣ Recognize It When...

Selecting, scheduling, or assigning resources
Trigger words: "minimum number", "maximum profit", "earliest", "fewest steps"
Sorting suddenly feels necessary before decisions
DP feels like overkill — no overlapping subproblems

3️⃣ Don't Confuse With...

DP (P13) → DP explores all choices; greedy commits to one without reconsidering
Sorting (P6) → sorting is often the setup for greedy, not the solution itself
Backtracking (P10) → backtracking tries all; greedy never undoes a choice

4️⃣ Approach in 3 Steps

#
Prove the greedy choice is safe — "this choice leaves maximum room for future decisions"
#
Sort or use a priority queue to always access the best candidate
#
Make the choice, update state, repeat

5️⃣ Invariant to Maintain

"At every step, the greedy choice made so far is part of some optimal solution."

6️⃣ Complexity to Justify

Time: O(N log N) with sort, O(N log N) with heap
Space: O(1) or O(N) depending on structure
Why: No backtracking, no revisiting decisions

7️⃣ Edge Cases to Always Check

Single element — greedy trivially correct
All elements same
Already optimal input — greedy should handle gracefully
Ties in priority — comparator must be deterministic
Empty input

8️⃣ One Line to Say in Interview

"This greedy choice is optimal because it leaves the most room for future decisions — I can prove no other choice leads to a better outcome."