Greedy
Greedy is the idea of solving an optimization problem by always picking the "best" option available at each step, without considering later effects. The nice thing is that for many problems, a chain of locally best choices produces the globally optimal result.
The hard — and most important — part is not writing the code but proving that the greedy rule really works, because not every optimization problem can be solved greedily. Apply it wrongly and the solution still runs fast but gives a wrong answer.
The classic proof technique is the exchange argument: assume another optimal solution differs from the greedy choice, then show you can always "swap" toward the greedy choice without making the result worse. Once every difference can be swapped away, greedy is optimal too. In an interview, being able to state this argument matters more than the code itself.
Greedy is like walking where, at every fork, you always pick the direction that looks best right now, without planning ahead.
The nice thing is that for many problems a chain of locally best choices ends up globally optimal — but you have to prove that, otherwise the result may not be optimal.
How to spot it
When you see these cues in the problem, reach for Greedy
| Keyword in the problem | Why it points to this topic |
|---|---|
| locally optimal choice | Decide now, never revisit |
| single pass | Track a few state variables, not a dp table |
| global max / min | Prove the greedy choice reaches the optimum |
When to use
4 typical situations where this topic applies
Each step has one clearly "locally best" choice
The local choice never has to be revisited in later steps (no backtracking)
You can prove the greedy choice leads to the global optimum
An optimization problem without overlapping subproblems like in dynamic programming
When NOT to use
3 situations where this topic doesn't fit — know them so you don't overuse them
A local optimum does NOT guarantee a global optimum: use DP (e.g. 0/1 Knapsack — fractional works greedily, 0/1 does not)
You need to list every feasible solution: greedy returns only one — use Backtracking
The problem has overlapping subproblems: DP is very likely the better fit
Illustration
A diagram of how this topic works.
Making change for 36 with coins [25, 10, 5, 1]: at each step take the largest coin ≤ the remainder (25 → 10 → 1). Locally optimal choices give a globally optimal result for a standard coin system.
Code template
Most problems in this topic share this scaffold — copy it, then fill in the problem-specific logic.
function greedyPattern(nums: number[]): R {
let best = initState()
for (const x of nums) {
// Take the locally best choice, update running state
best = chooseLocalBest(best, x)
}
return best
}Recap
A quick summary — reread it before your interview
Key points
At each step pick the local extreme, never revisit earlier choices
Unlike dynamic programming: greedy does not store a table of subproblem results, only a running state
Always verify correctness — not every optimization problem can be solved greedily
Proof tool: the exchange argument — swap an optimal solution toward the greedy choice without making it worse
Common mistakes
Applying greedy to a problem that needs a global view → wrong answer
Not proving the greedy choice correct, just "feeling" it is reasonable
Confusing it with dynamic programming and storing a redundant dp table
Complexity
Thường O(n) hoặc O(n log n) nếu cần sắp xếp trướcPractice problems for this topic
Grouped by difficulty — work through them in order to build confidence