IPO

How it works

Instead of using a min-heap for capital, we can simply sort the projects by their capital requirements upfront. A pointer then tracks which projects have become affordable. As capital grows, we advance this pointer and push newly affordable project profits into a max-heap. This avoids repeated heap operations on the capital side and is often faster in practice due to better cache performance from the sorted array traversal.

Steps

1. Create an array of indices [0, 1, ..., n-1] and sort it by capital[index].
2. Initialize a max-heap for profits and a pointer idx = 0.
3. Repeat up to k times:
   • While idx < n and capital[indices[idx]] <= w, push profits[indices[idx]] onto the max-heap and increment idx.
   • If the max-heap is empty, break.
   • Pop the maximum profit and add it to w.
4. Return w.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Using the Wrong Heap Type

A critical mistake is confusing which heap to use for which purpose. You need a min-heap ordered by capital (to efficiently find affordable projects) and a max-heap ordered by profit (to select the most profitable affordable project). Reversing these or using the wrong ordering will produce incorrect results.

Not Transferring Projects When Capital Increases

After completing a project and gaining profit, your capital increases, which may unlock previously unaffordable projects. Forgetting to transfer newly affordable projects from the capital heap to the profit heap before selecting the next project means you might miss the most profitable option available to you.

Not Handling the Case When No Projects Are Affordable

If your current capital is insufficient to start any remaining projects, the max-heap for profits will be empty. Failing to check for this condition and break out of the loop will cause errors (such as attempting to pop from an empty heap) or infinite loops.

Incorrect Greedy Strategy

Some developers try to optimize by considering both profit and capital together (e.g., profit-to-capital ratio) or by looking ahead multiple projects. This overcomplicates the solution. The optimal greedy strategy is simple: always pick the highest-profit project among those currently affordable.

Off-by-One Errors with k Projects

Remember that you can complete at most k projects, not exactly k. If there are fewer than k affordable projects total or if you run out of affordable projects before completing k, you should stop early rather than erroring or returning incorrect values.

from typing import List
import heapq

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int:
        n = len(profits)
        indices = list(range(n))
        indices.sort(key=lambda i: capital[i])

        maxProfit, idx = [], 0
        for _ in range(k):
            while idx < n and capital[indices[idx]] <= w:
                heapq.heappush(maxProfit, -profits[indices[idx]])
                idx += 1

            if not maxProfit:
                break
            w += -heapq.heappop(maxProfit)

        return w

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<int> indices(n);
        for (int i = 0; i < n; i++) {
            indices[i] = i;
        }
        sort(indices.begin(), indices.end(), [&](int a, int b) {
            return capital[a] < capital[b];
        });

        priority_queue<int> maxProfit;
        int idx = 0;
        for (int i = 0; i < k; i++) {
            while (idx < n && capital[indices[idx]] <= w) {
                maxProfit.push(profits[indices[idx]]);
                idx++;
            }
            if (maxProfit.empty()) {
                break;
            }
            w += maxProfit.top();
            maxProfit.pop();
        }

        return w;
    }
};