Loading…

Module M14 · DSA Curriculum

Greedy Algorithms

Pick the locally best move at every step — and prove it leads to the globally best answer.

advancedPractice Full theoryPrereq:Arrays & Hashing

Start practice Read the theory See all problems

What you'll learn

Define the greedy-choice property and optimal substructure
Decide what to sort by (start, end, ratio) for a greedy problem
Apply the sort-then-sweep template (interval scheduling, jump game)
Justify a greedy algorithm with an exchange argument
Recognise when greedy fails and DP is required (with a counter-example)
State greedy complexity (usually dominated by the sort)

When to reach for this

Signals (use it)

"Maximum number of non-overlapping ..." → sort by end time
"Minimum number of ... to cover/reach" with a local best each step
Jump game / gas station / assign cookies style reachability
A clear 'best next move' that you can argue is always safe
Activity selection, Huffman coding, fractional knapsack

Anti-signals (don't)

Local best can be globally wrong → use DP (e.g. 0/1 knapsack, coin change with odd denominations)
You must explore combinations of choices → DP or backtracking
No sort order makes the greedy choice safe → greedy likely fails

Theory & deep dive

A greedy algorithm builds a solution by always taking the choice that looks best right now, never reconsidering. When it works, it's gloriously simple and fast — often a single sorted pass, O(n log n). The catch, and the entire skill, is knowing when greed actually produces the global optimum, because for many problems the locally best move is a trap.

The defining question is: does a greedy-choice property hold — can you always make a locally optimal choice that's part of some global optimum? If yes, greedy wins. If not, you usually need dynamic programming, which considers combinations of choices instead of committing immediately. Telling these apart, and being able to justify greed with an exchange argument or a counter-example, is exactly what interviewers probe.

This module covers the greedy-choice property, how to recognise greedy-friendly problems, the sort-then-sweep template, proof techniques (exchange argument), and the classic traps where greedy fails.

The big idea in plain words

Greedy means grabbing the best-looking option right now and never undoing it. To watch the most movies in a single day, always pick the movie that ends earliest - finishing sooner frees up the most time for everything after it. Simple and fast.

The catch: 'best right now' isn't always best in the long run, so you have to be sure the greedy choice is safe. Example: meetings [1-3], [2-4], [3-5]. Sorted by end time, take [1-3] first, then the next meeting that starts after 3 is [3-5] - that's 2 meetings, the most possible. Choosing by earliest end time is the rule that makes greedy actually correct here.

When greedy is valid

Greedy is correct only when two properties hold — and the first is the one people skip checking.

Property	Meaning
Greedy-choice property	A locally optimal choice is part of some global optimum — you never have to undo it
Optimal substructure	After committing the greedy choice, the rest is the same kind of problem, optimally solvable

DP also has optimal substructure; the difference is the greedy-choice property. DP considers all choices for a subproblem and picks the best; greedy commits to one immediately. If committing can ever be wrong, you must use DP.

Watch out

Greedy correctness is NOT obvious — plausible-looking greedy strategies are often wrong. Coin change with coins {1,3,4} and amount 6: greedy picks 4+1+1 (3 coins) but the optimum is 3+3 (2 coins). Always sanity-check with a small adversarial example.

Greedy or DP? (decision flow)

The honest answer in an interview is often: 'I'll try a greedy strategy, but let me test it against a small counter-example first — if it survives, I'll argue why it's always safe; if not, I'll switch to DP.'

The sort-then-sweep template

The most common greedy shape: sort by the right key, then make one decision per element in order. Interval scheduling (max non-overlapping meetings) is the archetype — sort by end time, then greedily take each interval whose start is after the last one you took. Sorting by end time is what makes the greedy choice safe: finishing earliest leaves the most room for the rest.

Java· Jump Game — greedy reachability

boolean canJump(int[] nums) {
    int farthest = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > farthest) return false;        // can't reach i
        farthest = Math.max(farthest, i + nums[i]);
    }
    return true;
}

Choosing the sort key

The art of greedy is picking what to sort by. The wrong key gives a wrong answer; the right key makes correctness provable.

Problem	Sort by	Why
Max non-overlapping intervals	end time	finishing early frees the most future room
Minimum rooms / max overlap	start & end events	sweep counts concurrent intervals
Fractional knapsack	value/weight ratio	most value per unit first
Assign cookies	both ascending	match smallest sufficient to each child
Merge / non-overlapping removal	start time	adjacency by start enables sweep

If you can't find a sort order that makes the local choice safe, that's a strong hint greedy doesn't apply — reach for DP.

The exchange argument

To prove a greedy algorithm correct (and to convince an interviewer), use an exchange argument: assume an optimal solution differs from the greedy one; show you can swap in the greedy choice without making the solution worse; conclude the greedy choice is at least as good. For interval scheduling: if an optimal schedule's first meeting ends later than greedy's earliest-ending pick, swapping in greedy's pick can't reduce how many fit — so greedy is optimal.

You don't always need a formal proof in an interview, but being able to sketch the exchange argument is the senior-level signal that separates 'I guessed greedy' from 'I know greedy is correct here'.

How to talk about this in the interview

“Be disciplined: "Greedy might work — let me first test 'sort by end time, take if it fits' against a small example." Once it survives, justify it: "Finishing earliest always leaves at least as much room for later intervals, so by an exchange argument the greedy choice is safe." If a counter-example breaks it, say so and pivot: "Greedy fails here — 6 with coins {1,3,4} — so I'll use DP instead." That willingness to disprove your own greedy is exactly what's being graded. Complexity is usually O(n log n) for the sort.”

Common mistakes

–Assuming greedy works without testing a counter-example (it often doesn't)
–Sorting by the wrong key (e.g. start time instead of end time for activity selection)
–Using greedy for 0/1 knapsack or coin change with arbitrary denominations (needs DP)
–Not being able to justify why the greedy choice is safe
–Reconsidering past choices — if you need to, it's not greedy, it's DP
–Confusing fractional knapsack (greedy works) with 0/1 knapsack (greedy fails)

Complexity summary

Greedy algorithms are usually dominated by an initial sort: O(n log n) time, O(1)–O(n) space. The sweep itself is O(n). The hard part is correctness, not complexity — always pair the algorithm with a justification or a disproving counter-example.

Practice problems

23 total

Merge Triplets to Form Target Triplet