Problem 18.6 · Heaps and Priority QueuesHard

IPO

What it teaches: Unlock options over time: sorted by requirement, and a max-heap of the options you can currently afford.

Practise it on judges as “IPO”.

The problem

You start with capital w and may finish at most k projects. Project i needs capital[i] to start and adds profits[i] to your capital when done. Return the maximum final capital.

Example 1

Input: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
Output: 4

Do project 0 (capital 1), then project 2 (capital 4).

Constraints

1 ≤ k ≤ 10⁵
1 ≤ n ≤ 10⁵

Pattern clues in the wording

→ Choices unlock as a resource grows
→ Pick the best currently available, k times

These clues point to Two Heaps: Split values into a max-heap of the smaller half and a min-heap of the larger half to read the median instantly.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        return w;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	k = 2 w = 0 profits = [1,2,3] capital = [0,1,1]	4
2	k = 3 w = 0 profits = [1,2,3] capital = [0,1,2]	6

+ 1 hidden test the code runner will check

From slow to fast

Approaches

1. Sorted list + max-heap · O(n log n + k log n)

Sorted list + max-heap

Time O(n log n + k log n) Space O(n)

Sort indices by capital. Repeat k times: move every project with capital ≤ w into a max-heap of profits; if the heap is empty, stop; else add its top to w.

Approach 1

import java.util.*;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        Integer[] order = new Integer[n];
        for (int i = 0; i < n; i++) order[i] = i;
        Arrays.sort(order, Comparator.comparingInt(i -> capital[i]));
        PriorityQueue<Integer> best = new PriorityQueue<>(Comparator.reverseOrder());
        int next = 0;
        while (k-- > 0) {
            while (next < n && capital[order[next]] <= w) best.offer(profits[order[next++]]);
            if (best.isEmpty()) break;
            w += best.poll();
        }
        return w;
    }
}

Verdict: Each project enters the heap once.

Before you submit

Edge cases and common mistakes

Test these inputs

No affordable project at the start
k larger than n

Mistakes people make

Picking by profit-to-capital ratio (capital isn't spent, so ratio doesn't matter).

Interview

Follow-up questions

Why is the greedy choice safe?

Command Palette

The problem

Approaches

Sorted list + max-heap

Edge cases and common mistakes

Follow-up questions