IPO (LeetCode 502)
Imagine the company LeetCode wants to raise money through an IPO, and to make itself more attractive to investors it first wants to grow its capital by completing some projects. It only has the resources to complete at most k of them before the IPO. Help LeetCode pick the projects that grow its capital the most.
You're given n available projects. The i-th project pays out pure profit profits[i], but needs a minimum capital of capital[i] in hand before it can even be started.
You start with w capital, and every completed project's profit gets folded straight back into your capital, growing what you can afford to fund next.
Choose up to k distinct projects so that your final capital ends up as large as possible, and return that maximized amount.
Worked Examples
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]4k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]6⚖️Formal Constraints & Bounds
1 <= k <= 1050 <= w <= 109n == profits.lengthn == capital.length1 <= n <= 1050 <= profits[i] <= 1040 <= capital[i] <= 109
Core Insight
Because completing a project only ever increases capital w, any project affordable now stays affordable forever -- so greedily funding the most profitable currently-affordable project each round is always optimal.
Real-World Scenario & Production Applications
Venture capital fund sequencing, R&D project portfolio selection under a growing budget, and grant allocation with capital-eligibility gates.
Subproblems & Recurrence Decomposition3 Phases
Every project starts locked in a min-heap keyed by its required capital. This heap only ever shrinks: once a project is affordable it never re-locks, because capital w only grows.
min_heap = list(zip(capital, profits))
heapq.heapify(min_heap)
max_heap = []Step-by-Step Execution Trace Table
| Round | Unlocked into Max-Heap | Chosen Profit | New w |
|---|---|---|---|
| 1 | (cap=0, profit=1) | 1 | 0 + 1 = 1 |
| 2 | (cap=1, profit=2), (cap=1, profit=3) | 3 | 1 + 3 = 4 |
| 1 | min_heap = heapify(list(zip(capital, profit))) |
| 2 | max_heap = [] |
| 3 | for _ in range(k): |
| 4 | while min_heap and min_heap[0][0] <= w: |
| 5 | cap, prof = heappop(min_heap) |
| 6 | heappush(max_heap, -prof) |
| 7 | if not max_heap: |
| 8 | break |
| 9 | w += -heappop(max_heap) |
| 10 | return w |
Conceptual Narrative
Two heaps, but unlike the running-median pattern where they split data by VALUE, here they split candidates by ELIGIBILITY — one heap holds what you can't afford yet, the other holds what you can afford right now, ranked by payoff.
🧭 Conceptual Foundation & Pattern Intuition
A venture fund starts with capital w and may complete at most k projects, each requiring an up-front capital[i] and yielding profit[i]. Since completing a project only ever increases w (never decreases it), any project affordable today stays affordable forever after — capital never has to be "returned." This monotonicity is exactly what makes a greedy exchange argument work: among everything currently affordable, always taking the single most profitable one can never be beaten by saving it for later, because later you will have strictly more capital and the same option still available.
🏟️ The Analogy: A Startup Accelerator With a Capital Gate
Imagine an accelerator that reviews a stack of pitch decks. Some pitches require more seed capital than the accelerator currently has — those sit in a waiting room sorted by "cheapest to unlock first." Every time the accelerator's bank balance grows, it pulls every deck it can now afford out of the waiting room and drops it into a shortlist sorted by projected profit. It then always funds the single most profitable pitch in that shortlist. Because funding a pitch only adds money to the bank, nothing already unlocked ever gets re-locked — the shortlist only grows.
🔑 The Key Idea in the Code
The min-heap only ever shrinks (projects move out, never back in); the max-heap only ever grows within a round. Together they turn "greedily pick the best affordable option, k times" into O((N + k) log N).
Pushing all projects into profit max-heap initially: Projects can only be selected if required capital current available capital . Pushing all projects into the max-heap ignores capital constraints.
Repeated full linear scan : Scanning all remaining projects every round to check affordability takes quadratic time. Sort projects by capital once and advance a single pointer.
Exhausting available capital prematurely: If the profit max-heap is empty before completing projects (no affordable projects remain), the loop must terminate early and return current capital .
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
At most k selections + each choice has a prerequisite (capital) that only grows over time + maximize a cumulative reward.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: capital w is monotonically non-decreasing, so any project affordable now remains affordable in every future round.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to negate profit for the max-heap (Python's heapq is min-heap only).
Breaking out of the round loop instead of the outer k loop when the max-heap is empty but more capital-gated projects still exist for a later round -- actually the correct break IS on max-heap empty, since no project is currently affordable and capital cannot grow without funding one.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I keep a min-heap of (capital, profit) for locked projects and a max-heap of profit for unlocked ones. Each of the k rounds, I move every project with capital <= w into the max-heap, then greedily fund the most profitable one, adding its profit to w. If nothing is unlocked, I stop early. Runs in O((N + k) log N) time and
O(N)space."
Complexity & Mathematical Proof
O((N + k) log N)
Look at the execution steps: Building the capital min-heap of N projects is O(N) via heapify. Across all k rounds, each project is unlocked (pushed into the max-heap) at most once total, and each round pops at most one project from the max-heap. Total heap operations are O(N + k), each O(log N).
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The min-heap and max-heap together never hold more than N (capital, profit) pairs.
Derivation Progression
O(N) heapify
All N (capital, profit) pairs are heapified once up front.
Across all k rounds, every project is unlocked into the max-heap at most once (O(N log N) total), and each round pops at most one project (O(k log N) total).
Dominated by the one-time unlock cost plus at most k pops.
Variable Definitions
Number of candidate projects
Maximum number of projects that can be completed
Memory Architecture & Bounds
O(1) Iterative
O(N) Min-heap and max-heap together hold at most N pairs
O(1) Single integer capital
Boundary Best / Worst Cases
if k = 1.
.
when k ≥ N.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Trigger: "maximize capital after completing at most k distinct projects". Greedy selection with dynamic availability: you can only start projects where capital[i] <= w, and you want to greedily pick the one with maximum profits[i]. A Senior SWE splits the dimensions: Sort by Capital Requirement + Max-Heap of Available Profits.
, . Time budget: , easily handling operations in ms.
Stalling out early: if available_profits is empty and the next project in the sorted list requires more capital than current , no further projects can ever be unlocked; terminate the loop early and return .
IPO (LeetCode 502)
Imagine the company LeetCode wants to raise money through an IPO, and to make itself more attractive to investors it first wants to grow its capital by completing some projects. It only has the resources to complete at most k of them before the IPO. Help LeetCode pick the projects that grow its capital the most.
You're given n available projects. The i-th project pays out pure profit profits[i], but needs a minimum capital of capital[i] in hand before it can even be started.
You start with w capital, and every completed project's profit gets folded straight back into your capital, growing what you can afford to fund next.
Choose up to k distinct projects so that your final capital ends up as large as possible, and return that maximized amount.
Worked Examples
k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]4k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]6⚖️Formal Constraints & Bounds
1 <= k <= 1050 <= w <= 109n == profits.lengthn == capital.length1 <= n <= 1050 <= profits[i] <= 1040 <= capital[i] <= 109
Core Insight
Because completing a project only ever increases capital w, any project affordable now stays affordable forever -- so greedily funding the most profitable currently-affordable project each round is always optimal.
Real-World Scenario & Production Applications
Venture capital fund sequencing, R&D project portfolio selection under a growing budget, and grant allocation with capital-eligibility gates.
Subproblems & Recurrence Decomposition3 Phases
Every project starts locked in a min-heap keyed by its required capital. This heap only ever shrinks: once a project is affordable it never re-locks, because capital w only grows.
min_heap = list(zip(capital, profits))
heapq.heapify(min_heap)
max_heap = []Step-by-Step Execution Trace Table
| Round | Unlocked into Max-Heap | Chosen Profit | New w |
|---|---|---|---|
| 1 | (cap=0, profit=1) | 1 | 0 + 1 = 1 |
| 2 | (cap=1, profit=2), (cap=1, profit=3) | 3 | 1 + 3 = 4 |
| 1 | min_heap = heapify(list(zip(capital, profit))) |
| 2 | max_heap = [] |
| 3 | for _ in range(k): |
| 4 | while min_heap and min_heap[0][0] <= w: |
| 5 | cap, prof = heappop(min_heap) |
| 6 | heappush(max_heap, -prof) |
| 7 | if not max_heap: |
| 8 | break |
| 9 | w += -heappop(max_heap) |
| 10 | return w |
Conceptual Narrative
Two heaps, but unlike the running-median pattern where they split data by VALUE, here they split candidates by ELIGIBILITY — one heap holds what you can't afford yet, the other holds what you can afford right now, ranked by payoff.
🧭 Conceptual Foundation & Pattern Intuition
A venture fund starts with capital w and may complete at most k projects, each requiring an up-front capital[i] and yielding profit[i]. Since completing a project only ever increases w (never decreases it), any project affordable today stays affordable forever after — capital never has to be "returned." This monotonicity is exactly what makes a greedy exchange argument work: among everything currently affordable, always taking the single most profitable one can never be beaten by saving it for later, because later you will have strictly more capital and the same option still available.
🏟️ The Analogy: A Startup Accelerator With a Capital Gate
Imagine an accelerator that reviews a stack of pitch decks. Some pitches require more seed capital than the accelerator currently has — those sit in a waiting room sorted by "cheapest to unlock first." Every time the accelerator's bank balance grows, it pulls every deck it can now afford out of the waiting room and drops it into a shortlist sorted by projected profit. It then always funds the single most profitable pitch in that shortlist. Because funding a pitch only adds money to the bank, nothing already unlocked ever gets re-locked — the shortlist only grows.
🔑 The Key Idea in the Code
The min-heap only ever shrinks (projects move out, never back in); the max-heap only ever grows within a round. Together they turn "greedily pick the best affordable option, k times" into O((N + k) log N).
Pushing all projects into profit max-heap initially: Projects can only be selected if required capital current available capital . Pushing all projects into the max-heap ignores capital constraints.
Repeated full linear scan : Scanning all remaining projects every round to check affordability takes quadratic time. Sort projects by capital once and advance a single pointer.
Exhausting available capital prematurely: If the profit max-heap is empty before completing projects (no affordable projects remain), the loop must terminate early and return current capital .
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
At most k selections + each choice has a prerequisite (capital) that only grows over time + maximize a cumulative reward.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: capital w is monotonically non-decreasing, so any project affordable now remains affordable in every future round.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Forgetting to negate profit for the max-heap (Python's heapq is min-heap only).
Breaking out of the round loop instead of the outer k loop when the max-heap is empty but more capital-gated projects still exist for a later round -- actually the correct break IS on max-heap empty, since no project is currently affordable and capital cannot grow without funding one.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I keep a min-heap of (capital, profit) for locked projects and a max-heap of profit for unlocked ones. Each of the k rounds, I move every project with capital <= w into the max-heap, then greedily fund the most profitable one, adding its profit to w. If nothing is unlocked, I stop early. Runs in O((N + k) log N) time and
O(N)space."
Complexity & Mathematical Proof
O((N + k) log N)
Look at the execution steps: Building the capital min-heap of N projects is O(N) via heapify. Across all k rounds, each project is unlocked (pushed into the max-heap) at most once total, and each round pops at most one project from the max-heap. Total heap operations are O(N + k), each O(log N).
O(N) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. The min-heap and max-heap together never hold more than N (capital, profit) pairs.
Derivation Progression
O(N) heapify
All N (capital, profit) pairs are heapified once up front.
Across all k rounds, every project is unlocked into the max-heap at most once (O(N log N) total), and each round pops at most one project (O(k log N) total).
Dominated by the one-time unlock cost plus at most k pops.
Variable Definitions
Number of candidate projects
Maximum number of projects that can be completed
Memory Architecture & Bounds
O(1) Iterative
O(N) Min-heap and max-heap together hold at most N pairs
O(1) Single integer capital
Boundary Best / Worst Cases
if k = 1.
.
when k ≥ N.
Binary Heap Priority Queue Tree
Senior SWE Deconstruction & Hardware Caveats
Trigger: "maximize capital after completing at most k distinct projects". Greedy selection with dynamic availability: you can only start projects where capital[i] <= w, and you want to greedily pick the one with maximum profits[i]. A Senior SWE splits the dimensions: Sort by Capital Requirement + Max-Heap of Available Profits.
, . Time budget: , easily handling operations in ms.
Stalling out early: if available_profits is empty and the next project in the sorted list requires more capital than current , no further projects can ever be unlocked; terminate the loop early and return .