DSA Tracker

Visualize

IPO

Two heaps: capital-gate, then greedy max-profit

time O(n log n)space O(n)

Capital only ever grows, so a project affordable now stays affordable forever — nothing you skip becomes ineligible later. That monotonicity means the right move each round is simply the highest-profit project among everything currently affordable. Sorting projects by capital once, then sliding a pointer forward as w grows, feeds a max-heap (keyed on profit) exactly the newly-unlocked candidates — never re-scanning ones already inside it.

Details

Animated on: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] — invest in at most k projects, each needing its listed capital up front, to maximize final capital. Expected: 4.

Problem:IPOHard

Two heaps: capital-gate, then greedy max-profit

step 1 / 8

1

Sorted by capital: A(cap 0, profit 1), B(cap 1, profit 2), C(cap 1, profit 3). Project A's capital 0 <= w(0), so push its profit 1 onto the max-heap.

Pseudocode
1FUNCTION maxCapital(k, w, profits, capital):
2  SORT projects BY capital ascending
3  i <- 0
4  FOR round <- 1 TO k:
5    WHILE i < LENGTH(projects) AND projects[i].capital <= w:
6      INSERT(maxHeap, projects[i].profit)
7      i <- i + 1
8    IF maxHeap IS EMPTY: BREAK
9    w <- w + EXTRACT-MAX(maxHeap)
10  RETURN w

← / → step · space play · Home restart

Every step in words

Show all 8 steps
  1. Sorted by capital: A(cap 0, profit 1), B(cap 1, profit 2), C(cap 1, profit 3). Project A's capital 0 <= w(0), so push its profit 1 onto the max-heap.
  2. i now points at B (capital 1), which needs more capital than w=0. No more projects are affordable yet — the heap holds one candidate, profit 1.
  3. Pop the root — profit 1, the only (so the best) affordable project. w becomes 0 + 1 = 1.
  4. Capital rose to w=1, unlocking B (cap 1). Push its profit 2 first.
  5. C (cap 1) is affordable too. Push its profit 3 — it outranks 2, so it sifts up to the root.
  6. i has now passed all 3 projects. Pop the root — profit 3, the best of the 2 affordable projects.
  7. w becomes 1 + 3 = 4. That completes k=2 rounds, so the loop stops here even though project B (profit 2) is left unused in the heap.
  8. RETURN w = 4 — the maximum capital reachable after at most k=2 projects.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve IPO in the editorAll Heap problemsBack to roadmap