p88 — IPO

Source: LeetCode 502 · Hard · Topics: Heap, Greedy Companies (2024–2025): Goldman Sachs (high), Bloomberg (high), Amazon (medium), Google (medium) Loop position: Two heaps coordinated by a gating condition. Min-heap-by-capital gates affordability; max-heap-by-profit picks the best affordable. Canonical pattern for “filter by one key, optimize by another”.

1. Quick Context

Given initial capital w, do at most k projects. Each project i requires capital[i] to start and yields profits[i] (added to your capital). Maximize final capital.

Solution: Two-heap pattern.

  • Min-heap on capital: all unaffordable projects (with current w), keyed by required capital.
  • Max-heap on profit: all currently-affordable projects, keyed by profit.

Loop k times: drain min-heap into max-heap while top capital ≤ w; if max-heap empty break (nothing affordable); pop max profit and add to w.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/ipo/

STOP. 30-min timer.

3. Prerequisite Concepts

  • Two-heap pattern (min for one key, max for another).
  • Greedy with “promotion” between data structures as state changes.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: k rounds; each round, pick max-profit affordable project; add profit to capital.

2. Clarify: Same project picked twice? No, one-time. Can w stay zero? Yes.

3. Examples: k=2, w=0, profits=[1,2,3], capital=[0,1,1] → w=0+1=1; now both [2,3] affordable → +3 → 4.

5. Brute: Try all combinations of size ≤ k respecting capital order; O(C(n,k)·k).

6. Target: O((n + k) log n).

7. Pattern: Two heaps.

8. Develop: see solution.py.

9. Test: k > # projects; w=0 and all need capital; one project blocks others.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why max-profit-affordable is greedy-optimal

Exchange argument: suppose OPT picks project P at round i but not max-profit-affordable Q at that round. Q yields ≥ P profit, and Q is affordable at round i. Swap P ← Q: Q’s higher profit means future affordability is at least as good (more capital). So Q dominates P. Repeat ⇒ greedy = OPT.

6.2 The two-heap coordination

  • Min-heap-by-capital = “waiting room” for projects whose capital requirement hasn’t been met.
  • Max-heap-by-profit = “available pool” of projects ready to execute.
  • Promotion: each round, drain min-heap → max-heap while top capital ≤ w.

Each project moves at most once between heaps ⇒ amortized O(log n) per project.

6.3 Why a single sort doesn’t work

You can sort by capital ascending and use a max-heap on profit alone (no min-heap needed). Walk a pointer through sorted projects; push profits while capital[ptr] ≤ w. This is equivalent and slightly simpler.

projects = sorted(zip(capital, profits))
ptr = 0
max_heap = []
for _ in range(k):
    while ptr < n and projects[ptr][0] <= w:
        heapq.heappush(max_heap, -projects[ptr][1])
        ptr += 1
    if not max_heap:
        break
    w += -heapq.heappop(max_heap)

Both are O((n + k) log n); the pointer version saves the min-heap overhead.

6.4 If k = ∞ — what changes?

Pick every project with profit > 0 (in some feasible order). The two-heap pattern still works — just keep looping until both empty. No new optimization needed.

6.5 Family: two-heap / gated greedy

  • LC 502 IPO (this).
  • LC 295 Find Median from Data Stream (max + min for two halves).
  • LC 480 Sliding Window Median.
  • LC 1942 Number of Smallest Unoccupied Chair (free chairs + busy ends).
  • LC 1834 Single-Threaded CPU (waiting + ready).

7. Anti-Pattern Analysis

  1. Pick min-capital affordable — wastes turns on low-profit projects.
  2. Pick max-profit overall (ignoring capital) — picks unaffordable; no progress.
  3. Re-sort projects each round — O(k n log n) instead of O((n+k) log n).
  4. Forget early termination when nothing is affordable — wastes loop iterations (harmless but signals weak code).
  5. Use min-heap-by-profit — same wrong direction as anti-pattern 1.

8. Skills & Takeaways

  • Two-heap pattern (or sort + single heap).
  • Greedy exchange argument for round-by-round optimization.
  • Affordability gating.

9. When to Move On

  • Solve cold in 20 min with two-heap or sort-then-heap.
  • Articulate exchange argument.
  • Cite LC 1834 as a sibling.

10. Company Context

  • Goldman Sachs: finance-themed; loves this problem.
  • Bloomberg: very common.
  • Amazon: L5/L6.
  • Google: L5; expects exchange argument.

Strong: “Two-heap or sort + max-heap; gate by affordability; greedy exchange argument for max-profit-affordable optimality; cited LC 1834 CPU as sibling.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Two-heapBuggyAfter hintCold+ sort + single heap equivalence
ExchangeNoneNoneVerbal+ formal write-up
FamilyNoneNoneLC 1834+ LC 1942 chairs
Edgek > nAfter testCold+ nothing affordable proof

12. Level Delta

  • Mid (L4): Two-heap with guidance; misses early termination.
  • Senior (L5): Cold; exchange argument verbal.
  • Staff (L6): + sort + single heap equivalence + family.
  • Principal (L7+): + framing as online matroid-intersection / activity selection on weighted matroid + LP duality for fractional relaxation.

13. Follow-up Q&A

Q1: Each project takes time; you have a time budget instead of k rounds. A1: Becomes knapsack-flavored; NP-hard. Approximations: dynamic programming on (time, capital) state if discretized.

Q2: Projects expire (deadline). A2: Like Course Schedule III: sort by deadline, swap-out lemma.

Q3: Maximize expected profit when profits are random. A3: Greedy on E[profit] if independent; otherwise stochastic DP.

Q4: k = ∞. A4: Pick every project with profit > 0; loop until both heaps drain or no affordable.

Q5: Negative profits allowed. A5: Skip them — never optimal to take a negative profit if not forced.

14. Solution Walkthrough

See solution.py:

  • find_maximized_capital_two_heap — explicit min + max heap.
  • find_maximized_capital_sort — sort by capital + single max heap (simpler, same asymptotic).
  • find_maximized_capital_brute — all subsets ≤ k.

15. Beyond the Problem

Principal code review: “IPO is the smallest online matroid intersection problem you can write down: at each step you pick the max-weight element subject to a feasibility constraint that changes with your state (here, capital). Two-heap is the standard implementation, but the deeper observation is that affordability is monotone in capital — once you can afford a project, you can always afford it later (capital never decreases) — so the ‘promotion’ direction is one-way. This monotonicity is what makes the greedy optimal: it’s the analog of matroid-greedy-optimality but lifted to an online setting where the matroid evolves. The Staff+ recognition: when you see ‘pick k things from a pool gated by current state, where state grows monotonically’, you almost always have a two-heap (or sort + heap) solution with a clean exchange-argument proof. Real-world analogs: ad-bidding budget allocation, GPU scheduling with VRAM constraints, CI test selection under cumulative-time budget. The lesson scales: monotone state + max-value-feasible greedy = optimal, and the implementation is always a coordinated heap pair.”