#502 IPO
the problem
In plain words
You may finish at most k distinct projects. Project i can only be started when your capital is at least capital[i]; finishing it adds its pure profit profits[i] to your capital (starting it doesn't spend anything). You begin with capital w. Return the largest capital you can end with.
in k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
out 4
With 0 only project 0 can start: capital becomes 1. Now projects 1 and 2 are affordable; take the one with profit 3 → 4.
in k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
out 6
0 → 1 → 3 → 6: each profit unlocks the next project.
- 1 ≤ k ≤ 10⁵
- 0 ≤ w ≤ 10⁹
- 1 ≤ n ≤ 10⁵, n == profits.length == capital.length
- 0 ≤ profits[i] ≤ 10⁴
- 0 ≤ capital[i] ≤ 10⁹
- The answer fits in a 32-bit signed int
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternGreedy with a heap
Profits are never negative and capital only grows, so in every round the biggest profit you can afford right now is the right pick. Sort by capital to unlock projects as w grows; keep the unlocked profits in a max-heap.
solutions
From brute force to optimal
k times: look through all unfinished projects, take the most profitable affordable one.
- Mark finished projects in a boolean array.
- Each round, scan for the biggest profit with capital[i] ≤ w.
- None found → stop early; otherwise add its profit to w.
k rounds × n checks — 10¹⁰ at the limits.
The finished flags.
class Solution { public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { boolean[] done = new boolean[profits.length]; for (int round = 0; round < k; round++) { int best = -1; for (int i = 0; i < profits.length; i++) { // most profitable project we can start right now if (!done[i] && capital[i] <= w && (best == -1 || profits[i] > profits[best])) best = i; } if (best == -1) break; // nothing affordable: capital can't grow any more done[best] = true; w += profits[best]; } return w; }}A pointer walks projects in capital order and unlocks everything w can afford; a max-heap of unlocked profits gives the best pick each round.
- Pair (capital, profit) and sort by capital.
- Each round: move the pointer, offering every newly affordable profit into a max-heap.
- Heap empty → nothing can ever be afforded again: stop.
- Otherwise w += poll().
One sort; each project is offered once and polled at most once, and there are at most k polls.
The sorted pairs and the heap.
class Solution { public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) { int n = profits.length; int[][] projects = new int[n][]; for (int i = 0; i < n; i++) projects[i] = new int[] {capital[i], profits[i]}; Arrays.sort(projects, Comparator.comparingInt(p -> p[0])); // cheapest to start first PriorityQueue<Integer> affordable = new PriorityQueue<>(Comparator.reverseOrder()); // max-heap of profits int next = 0; // first project still locked for (int round = 0; round < k; round++) { while (next < n && projects[next][0] <= w) { // capital grew: unlock more affordable.offer(projects[next++][1]); } if (affordable.isEmpty()) break; // nothing we can start w += affordable.poll(); // greedy: biggest profit now } return w; }}Dry run
in the room
How to say it in the interview
talk track
- Argue the greedy first: profits are ≥ 0 and capital never goes down, so the biggest affordable profit now can only widen what's affordable later.
- Then make it fast: sort + pointer to unlock, max-heap of profits to choose.
- Mention the early exit: an empty heap means w can never grow again.
traps
- Re-scanning every project each round — O(k · n).
- Polling an empty heap:
w += heap.poll()unboxes null and throws NullPointerException — check isEmpty first. - Thinking the capital is spent when a project starts — it's only a threshold.
what they ask next
Follow-ups
Why is the greedy choice safe?
Exchange argument: take a best plan whose first project isn't the biggest affordable profit p. Put p first instead (and drop it from later, if it was there): every step's capital is at least as high as before, so every later project is still affordable, and the total can't drop.
A version with two heaps?
Instead of sorting, keep a min-heap by capital; pop from it into the profit max-heap while capital ≤ w. Same O((n + k) log n).
before you submit
Edge cases to test
- Nothing affordable at the start (every capital[i] > w): return w.
- k > n: you run out of projects first — stop when the heap is empty.
- Zero-profit projects can be picked but never unlock anything.
- Huge w: everything is affordable at once, so the answer is w plus the k biggest profits.
practise next
Similar problems
- #1046Last Stone WeightEasyin Heaps
- #621Task SchedulerMediumin Heaps
- #253Meeting Rooms IIMediumin IntervalsLeetCode Premium