Greedy with Heap
What is this?
A greedy algorithm makes the best choice available right now and trusts that this adds up to the best overall answer. The catch is that "best available" keeps changing as new options open up and old ones expire. A heap keeps that moving target in order so the current best is always one quick pop away.
💡 Fun fact: This "always grab the best option now" idea is the same engine behind Dijkstra's famous shortest-path algorithm, which finds the fastest route through a map by repeatedly popping the closest unvisited place from a heap.
🔓 The 2 problems in this chapter are free. Sign in with Google or Microsoft to start solving.
Core idea: Many greedy algorithms repeat the same move: at each step, take the best available option right now. The trouble is that "best available" changes as you go — new options unlock, old ones expire. A heap maintains that shifting frontier so the current extreme is always one pop away. A close cousin, the monotonic stack, applies the same greedy instinct to ordering: keep the stack as good as possible and pop whatever blocks a better arrangement.
The pattern
Greedy works when a locally optimal choice is provably part of a globally optimal answer. The data structure's job is to surface that locally optimal choice cheaply.
- A heap lets you re-evaluate "what's best now" after each step in O(log n), which is exactly what you need when the set of affordable or reachable options grows over time.
- A monotonic stack enforces a greedy ordering: you push candidates and pop any that a later, better candidate makes obsolete — as long as a guard tells you the popped element will appear again.
The problems
- IPO — you can fund projects whose capital requirement you can currently afford. As your capital grows, more projects unlock. Push every affordable project's profit into a max-heap, pop the most profitable, add its profit to your capital, and repeat. The heap tracks the moving affordability threshold.
- Remove Duplicate Letters — build the lexicographically smallest result with each letter once. Use a monotonic stack: before pushing a letter, pop larger letters off the top only if they still occur later (a last-occurrence guard). The guard is what makes the greedy pop safe.
Key takeaways
- Greedy = best choice now — correct only when local optimality implies global optimality.
- Heap surfaces the current extreme as the option set shifts (IPO's unlocking projects).
- Push what becomes available, pop what's best — the two-heap-free engine behind IPO.
- Monotonic stack greedily fixes ordering — pop worse elements, guarded by last-occurrence so you never lose a required letter.
- Why interviewers love it: it tests whether you can prove the greedy move is safe, not just code it.
Order: IPO → Remove Duplicate Letters.
Core idea: Walk the string once, keeping a stack of "letters chosen so far"; before adding a new letter, pop any bigger letter off the top as long as it still appears later — because you can always re-add it then, and dropping it now buys you a smaller string.
A quick note before we start: this lesson lives in the priority queue folder, but Remove Duplicate Letters is not actually a heap problem. There's no "extract-min" over a changing set of priorities. It's a greedy problem solved with a monotonic stack — and pretending it's a priority queue will send you down the wrong path in an interview. We'll frame it correctly.
Problem, rephrased
Imagine you run a license-plate registry. Every car submits a string of region codes — single lowercase letters — but the law says a final canonical plate must contain each distinct code exactly once. Among all the legal plates you could form by deleting the extra copies (you may delete, but never reorder), the registry mandates you issue the alphabetically smallest one, because that's the canonical form everyone agrees on.
So given a string s of lowercase letters, produce the string that:
- contains every distinct letter of
sexactly once, and - is a subsequence of
s(relative order preserved — you only delete), and - is the lexicographically smallest such subsequence.
| Input | Output | Why |
|---|---|---|
"bcabc" |
"abc" |
Distinct letters are a,b,c; "abc" is the smallest arrangement reachable by deletion. |
"cbacdcbc" |
"acdb" |
Distinct letters are a,b,c,d; "acdb" beats "acdb", "cabd", etc. |
"bbcaac" |
"bac" |
Distinct letters a,b,c; we can't get "abc" because the only b's sit before the last a. |
That last row is the subtle one — you can't always reach the globally sorted order. You're constrained to subsequences of s.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson