IPO
Last Updated: April 4, 2026
Understanding the Problem
We have a set of projects, each requiring some minimum capital to start and yielding a certain profit upon completion. We start with w capital and can complete at most k projects. After completing a project, its profit gets added to our capital, potentially unlocking more expensive projects. The goal is to maximize the final capital.
The greedy insight here is straightforward: at each step, among all projects we can currently afford, we should pick the one with the highest profit. That gives us the most capital for future rounds, which in turn unlocks the most options. The challenge is doing this efficiently. With up to 10^5 projects and 10^5 rounds, we need a data structure that quickly tells us the most profitable affordable project.
Key Constraints:
1 <= k <= 10^5and1 <= n <= 10^5→ We might iterate up to k times, and each iteration needs to efficiently find the best project. A naive O(n) scan per iteration gives O(k * n) = O(10^10), which is too slow.0 <= w <= 10^9and0 <= capital[i] <= 10^9→ Capital values can be very large, so we can't use them as array indices. No bucket sort tricks.0 <= profits[i] <= 10^4→ Profits are bounded but this doesn't help much algorithmically.
Approach 1: Brute Force (Greedy with Linear Scan)
Intuition
The greedy strategy is clear: always pick the most profitable project you can afford. The simplest way to implement this is to scan all projects each round, find the one with the highest profit among those whose capital requirement is at most our current capital, complete it, and repeat up to k times.
We need to track which projects have been used since each project can only be completed once. A boolean array works for that.
Algorithm
- Create a boolean array
usedof size n, initialized to false. - Repeat up to k times:
a. Scan all n projects. Among those not yet used and whose capital[i] <= w, find the one with the maximum profits[i].
b. If no affordable project exists, stop early.
c. Mark that project as used and add its profit to w.
- Return
w.
Example Walkthrough
Code
- Time Complexity: O(k n). Each of the k rounds scans all n projects. In the worst case this is O(10^5 10^5) = O(10^10), which is far too slow.
- Space Complexity: O(n). The boolean
usedarray takes O(n) space.
This approach works correctly but is too slow for large inputs. What if we sorted projects by capital and used a max-heap to instantly retrieve the best affordable project?
Approach 2: Greedy with Sort + Max-Heap (Optimal)
Intuition
The key observation is that once a project becomes affordable, it stays affordable because our capital only increases. So instead of re-scanning every project each round, we can sort projects by their capital requirement and use a pointer to track which ones we have unlocked so far.
Here is the plan: sort all projects by capital. Maintain a max-heap of profits for all projects we can currently afford. Each round, push any newly affordable projects into the max-heap (since our capital just increased), then pop the top to get the most profitable one. The pointer never goes backward because capital only grows.
The greedy choice is optimal because capital only increases. If we pick the most profitable affordable project now, we end up with at least as much capital as any other choice. A higher capital means we unlock a superset of projects compared to any alternative path. So the greedy approach never paints us into a corner.
The sorting + max-heap combination is efficient because each project gets pushed into and popped from the heap at most once. The pointer only moves forward. So across all k rounds, the total heap work is O(n log n).
Algorithm
- Pair each project as
(capital[i], profits[i])and sort by capital ascending. - Initialize a pointer
idx = 0and a max-heap (empty). - Repeat k times:
a. While idx < n and projects[idx].capital <= w, push projects[idx].profit into the max-heap and increment idx.
b. If the max-heap is empty, no more affordable projects exist. Stop early.
c. Pop the maximum profit from the heap and add it to w.
- Return
w.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n). Each of the n projects is pushed into and popped from the heap at most once, each operation costing O(log n). The total heap work is O(n log n).
- Space Complexity: O(n). The sorted projects array and the heap each store up to n elements.