Problem Statement

IPO

You have some money to start with, called your capital. There is a list of projects. Each project needs a minimum amount of capital before you are allowed to start it, and each project pays you a profit when you finish it. When you finish a project, its profit is added to your capital, so you have more money for the next one. You can do at most k projects. The goal is to end with as much capital as possible. The smart move at each step is simple: out of every project you can currently afford, do the one that pays the most. To make that fast, we use two helpers. A min-heap sorted by capital tells us which projects just became affordable as our money grows. A max-heap of profits lets us instantly grab the most profitable affordable project. A heap is like a self-sorting bucket: you toss items in, and it always knows which one is smallest (min-heap) or largest (max-heap) without you re-sorting everything.

hardHeapGreedyHeap / Priority QueueTime: O(n log n) · Space: O(n)

Signals to notice

maximize capital after k investmentstwo heaps: affordable and profitablegreedy selection

Brute force first

Try all combinations — O(C(n,k)).

The key insight

Min-heap by capital, max-heap by profit. Each round: move newly affordable projects to profit heap, pick most profitable. O(n log n).

Trace it on `k=2, w=0, profits=[1,2,3], capital=[0,1,1]`

sort by capital: projects=[(0,1),(1,2),(1,3)], idx=0, max_heap=[], w=0
Round 1 unlock: projects[0]=(0,1) cap 0<=w0 -> push profit 1, idx=1; projects[1] cap 1>0 stop. heap=[1]
Round 1 pick: pop max 1 -> w=1
Round 2 unlock: projects[1]=(1,2) cap 1<=w1 -> push 2, idx=2; projects[2]=(1,3) cap 1<=w1 -> push 3, idx=3. heap=[3,2]
Round 2 pick: pop max 3 -> w=4
k=2 rounds done -> return w=4

What must stay true

As capital grows, more projects become affordable. The profit heap always picks the best available option.

Shape of the loop

projects = sort(zip(capital, profits)) by capital ascending
idx = 0; max_heap = []   # max-heap of profits
repeat k times:
    while idx < n and projects[idx].capital <= w:
        push projects[idx].profit into max_heap; idx += 1
    if max_heap empty: break
    w += pop_max(max_heap)
return w

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Not pre-sorting by capital — the min-heap feeds the profit heap efficiently as budget increases.

Heap / Priority Queue Pattern