IPO | Webcoderspeed

Problem

Given k investments, profits[], capital[] (minimum capital required), starting capital w, maximize final capital.

Key insight (Two Heaps):

Min-heap of (capital, profit) — sorted by required capital
Max-heap of profits for affordable projects
Each round: move affordable projects to max-heap, pick max profit

Solutions

// C++
int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> available; // (cap, profit)
    priority_queue<int> maxProfit;
    for (int i = 0; i < (int)profits.size(); i++)
        available.push({capital[i], profits[i]});
    for (int i = 0; i < k; i++) {
        while (!available.empty() && available.top().first <= w) {
            maxProfit.push(available.top().second);
            available.pop();
        }
        if (maxProfit.empty()) break;
        w += maxProfit.top(); maxProfit.pop();
    }
    return w;
}

// Java
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    int n = profits.length;
    int[][] projects = new int[n][2];
    for (int i = 0; i < n; i++) projects[i] = new int[]{capital[i], profits[i]};
    Arrays.sort(projects, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> maxH = new PriorityQueue<>(Collections.reverseOrder());
    int i = 0;
    for (int round = 0; round < k; round++) {
        while (i < n && projects[i][0] <= w) maxH.offer(projects[i++][1]);
        if (maxH.isEmpty()) break;
        w += maxH.poll();
    }
    return w;
}

// JavaScript
function findMaximizedCapital(k, w, profits, capital) {
    const projects = profits.map((p, i) => [capital[i], p]);
    projects.sort((a, b) => a[0] - b[0]);
    const available = []; // max-heap by profit (use sorted array)
    let i = 0;
    for (let round = 0; round < k; round++) {
        while (i < projects.length && projects[i][0] <= w) {
            let pos = available.findIndex(p => p < projects[i][1]);
            if (pos === -1) available.push(projects[i][1]);
            else available.splice(pos, 0, projects[i][1]);
            i++;
        }
        if (!available.length) break;
        w += available.shift(); // take max profit
    }
    return w;
}

# Python
import heapq

def findMaximizedCapital(k, w, profits, capital):
    projects = sorted(zip(capital, profits))
    max_profit = []  # max-heap (negate)
    i = 0
    for _ in range(k):
        # Unlock all affordable projects
        while i < len(projects) and projects[i][0] <= w:
            heapq.heappush(max_profit, -projects[i][1])
            i += 1
        if not max_profit:
            break
        w -= heapq.heappop(max_profit)  # add profit (negated)
    return w

Complexity

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

Key Insight

Two-phase greedy: unlock affordable projects into max-profit heap, then always take the best available. Capital only grows, so projects unlocked stay unlocked.