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.