IPO

HardTwo Heaps · Greedy🧩 Two Heaps LeetCode #502 ↗Updated Oct 30, 2026

Problem

You start with capital w and may complete at most k distinct projects. Project i can only be started if your current capital is ≥ capital[i]; finishing it adds profits[i] (the requirement is not spent). Choose projects to maximise your final capital and return it.

Inputk=2, w=0, p=[1,2,3], c=[0,1,1]Output4

Inputk=3, w=0, p=[1,2,3], c=[0,1,2]Output6

1 ≤ k, n ≤ 10⁵ · 0 ≤ w ≤ 10⁹ · 0 ≤ profits[i] ≤ 10⁴ · 0 ≤ capital[i] ≤ 10⁹ · answer fits in 32 bits

Try it yourself

Java

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

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Capital only grows, so a project affordable now stays affordable forever. Hence at each step simply take the most profitable affordable project: it maximises capital, which can only unlock more options. Sort by capital to unlock, max-heap by profit to choose.

PatternTwo Heaps

Instinct When you need the middle of a changing collection, or best-of-one-pile fed by another pile, split it into a max-heap low half and a min-heap high half.

Memory hack Small fries in a max-heap, big fish in a min-heap; the median lives on the shoreline between them.

Open the Two Heaps guide →

Approaches

Brute ForceBacktracking over Project Sequences

Time O(n^k)Space O(n)

Try every affordable unused project as the next pick, recurse with k-1 and the increased capital, and keep the best final capital (stopping early is also allowed). This explores all orders, so it needs no insight — and is useful to verify the greedy on small inputs.

Java

public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    return dfs(k, w, profits, capital, new boolean[profits.length]);
}

private int dfs(int k, int w, int[] profits, int[] capital, boolean[] used) {
    int best = w; // option: stop here
    if (k == 0) return best;
    for (int i = 0; i < profits.length; i++) {
        if (used[i] || capital[i] > w) continue;
        used[i] = true;
        best = Math.max(best, dfs(k - 1, w + profits[i], profits, capital, used));
        used[i] = false;
    }
    return best;
}

Exponential in k; only viable for tiny inputs.

BetterGreedy with Linear Scan

Time O(k·n)Space O(n)

Apply the greedy directly: in each of the k rounds scan every project, pick the unused affordable one with the highest profit and add it to w. Stop early when nothing is affordable. A used[] array avoids mutating the input.

Java

public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    int n = profits.length;
    boolean[] used = new boolean[n];
    for (int round = 0; round < k; round++) {
        int best = -1;
        for (int j = 0; j < n; j++) {
            if (!used[j] && capital[j] <= w
                    && (best == -1 || profits[j] > profits[best])) best = j;
        }
        if (best == -1) break; // nothing affordable
        used[best] = true;
        w += profits[best];
    }
    return w;
}

Correct and simple, but 10⁵ × 10⁵ scans is too slow.

OptimalSort by Capital + Max-Heap of Profits

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

Sort projects by required capital. Each round, push the profits of all newly affordable projects (pointer i only moves forward) into a max-heap, then take the top. Each project enters the heap once, so the repeated scan of the Better approach disappears.

Java

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, (a, b) -> Integer.compare(a[0], b[0]));
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
    int i = 0;
    while (k-- > 0) {
        while (i < n && projects[i][0] <= w) maxHeap.offer(projects[i++][1]); // unlock
        if (maxHeap.isEmpty()) break; // nothing affordable
        w += maxHeap.poll();
    }
    return w;
}

Each project is unlocked once and chosen in O(log n) — scales to 10⁵.

Pro tip

If w already covers the largest capital requirement, the answer is just w + the k largest profits — a quick early exit.

At a glance

Level	Approach	Time	Space
Brute Force	Backtracking over Project Sequences	`O(n^k)`	`O(n)`
Better	Greedy with Linear Scan	`O(k·n)`	`O(n)`
Optimal	Sort by Capital + Max-Heap of Profits	`O((n + k) log n)`	`O(n)`

Common pitfalls

Picking the cheapest project (lowest capital) instead of the most profitable affordable one.
Not breaking when the heap is empty — poll() returns null → NPE.
Re-sorting or re-scanning every round — keep one forward pointer over sorted projects.

Interview tips

Argue the greedy: capital never decreases, so maximising it now never closes options.
Point out the two orders: unlock by capital (sort), choose by profit (heap).
Mention it mirrors Single-Threaded CPU / Furthest Building — sort + heap sweeps.

Pattern

Unlock-then-choose heap → items become available by one key and are picked by another.

My notes saved in this browser