IPO (Maximize Capital)
A hard Heap problem included in Striver A2Z. Below: the roles whose interviews prioritise this topic, and how to practise it.
- Topic
- Heap
- Sheets
- 1
- Core for
- 9 roles
- Platform
- LeetCode
The problem
Suppose you have an initial capital and can invest in at most k projects. Each project has a minimum capital requirement and a pure profit. You can only start a project if you have enough capital. After finishing a project, its profit is added to your capital. Design an algorithm to maximize your total capital after completing at most k projects.
Example 1
- Input
- k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
- Output
- 4
- Why
- Start with w=0. Only project 0 (capital 0) is affordable. Invest in it: profit 1, w becomes 1. Now projects 1 and 2 are affordable. Choose project 2 (profit 3): w becomes 4. After 2 projects, total capital is 4.
Example 2
- Input
- k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
- Output
- 6
- Why
- Start with w=0. Invest in project 0 (profit 1), w becomes 1. Invest in project 1 (profit 2), w becomes 3. Invest in project 2 (profit 3), w becomes 6. All 3 projects completed.
Example 3
- Input
- k = 1, w = 10, profits = [1,2,3], capital = [10,11,12]
- Output
- 11
- Why
- Start with w=10. Only project 0 (capital requirement 10) is affordable. Invest in it: profit 1, w becomes 11. Only 1 project allowed, so final capital is 11.
Constraints
- 1 <= k <= 10^5
- 0 <= w <= 10^9
- n == profits.length == capital.length
- 1 <= n <= 10^5
- 0 <= profits[i] <= 10^4
- 0 <= capital[i] <= 10^9
How to think about it
Updated 2026-09-09Capital only ever increases after finishing a project. This monotonicity means any project affordable right now remains affordable forever. At every step, the optimal choice among currently affordable projects is the one with maximum profit, which makes the choice a greedy pick from a dynamically expanding pool.
Approaches, worst first
Linear search per round
time O(k * n) · space O(n)
Repeat k times: scan all uncompleted projects, identify which ones have capital requirement <= w, and pick the one with the highest profit. Scan takes linear time on every pick.
Sorted pairs and max-heapWrite this one
time O(n log n + k log n) · space O(n)
Sort all projects by required capital ascending. In each of the k rounds, push all newly affordable projects into a max-heap keyed on profit. Pop the top profit, add it to w, and repeat. If the heap is empty, stop early.
Where people lose marks · 3
- Re-evaluating or sorting the heap whenever capital increases. Projects already in the heap are permanently eligible; you only ever add newly unlocked projects.
- Continuing the loop when the max-heap is empty. If capital w cannot afford any remaining projects, the loop must break immediately rather than attempting to pop empty heap memory.
- k can exceed n. You can complete at most n unique projects total, so capping the loop at min(k, n) prevents useless iterations.
The theory behind it
Heap — the ground this problem stands on. All Heap problems
What Heap is
A heap is a specialized tree that keeps only the single most extreme item at the very top. In a min-heap, every parent node is smaller than its children, so the smallest element in the entire collection sits immediately at the root. Unlike a binary search tree, a heap does not keep all items in full sorted order. It maintains only a partial order, making it fast at giving you the single smallest or largest item without spending time sorting everything else.
When to reach for it
Reach for a heap when a problem asks for the top k largest elements, the kth smallest value, or a running median from a stream of numbers. Signals include phrases like continuously finding the cheapest item, merging k sorted linked lists, or scheduling tasks with priorities. Whenever you need repeated access to the minimum or maximum value while items are added and removed dynamically, a priority heap is the tool.
How the pattern works
To find the k largest elements, keep a min-heap of fixed size k. Push incoming numbers into the heap; whenever the heap size grows past k, pop the top item, which is the smallest among them. After processing all elements, only the k largest remain. For a running median, balance two heaps: a max-heap holding the smaller half of numbers and a min-heap holding the larger half. In code, heaps are stored compactly as flat arrays where a node at index i has children at indices 2i plus 1 and 2i plus 2.
What each operation costs
| Operation | Time |
|---|---|
| read the minimum or maximum element | O(1) |
| insert a new element and sift into position | O(log n) |
| remove the top element and sift down | O(log n) |
| build a heap from an array of n items | O(n) |
What usually goes wrong with Heap
- Using a max-heap instead of a min-heap when keeping the k largest elements, causing the largest values to be evicted while small items stay behind.
- Assuming that extracting elements by iterating over the backing array yields sorted order, without popping items from the heap one by one.
- Forgetting that standard language libraries provide a min-heap by default, leading to wrong answers when a max-heap was required.
Which roles need this problem
Heap is a core topic for these 9 roles — if you're targeting one of them, this problem is early in your path, not optional.
Secondary for 11 more roles, including SDE / Backend Engineer, Data Engineer, ML Engineer.
Track this in your role's order
Pick your target role and all 370 problems — including this one — resequence to what that interview actually asks. Free.
Start freeMore Heap problems
Problem set and role mapping as of .