IPO

Difficulty: Hard Source: NeetCode

Problem

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to venture capitalists, LeetCode would like to work on some projects to increase its capital before the IPO. Since it has limited resources, it can only finish at most k distinct projects before the IPO. Help LeetCode design the best way to maximize its total capital after finishing at most k distinct projects.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] required to start it.

Initially, you have w capital. When you finish a project, you will obtain its pure profit and the profit will be added to your total capital. Pick at most k distinct projects from given projects to maximize your final capital, and return the maximized capital.

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

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

Constraints:

• 1 <= k <= 10^5
• 0 <= w <= 10^9
• n == profits.length == capital.length
• 1 <= n <= 10^5
• 0 <= profits[i] <= 10^4
• 0 <= capital[i] <= 10^9

Prerequisites

Before attempting this problem, you should be comfortable with:

• Greedy algorithms — always taking the most profitable currently affordable project
• Two heaps pattern — one heap for locked projects (min by capital), one for available projects (max by profit)
• Min-heap and max-heap — using Python’s heapq with negation for max-heap behavior

1. Brute Force — Scan All Projects Each Round

Intuition

For each of the k rounds, scan all projects, find all that we can currently afford, pick the one with the highest profit, collect it, and add the profit to our capital. This is correct but slow for large inputs.

Algorithm

1. Repeat at most k times: a. Find all projects where capital[i] <= w. b. If none exist, break. c. Pick the project with the maximum profit. Add its profit to w. Mark it as done.
2. Return w.

Solution

def findMaximizedCapital(k, w, profits, capital):
    n = len(profits)
    done = [False] * n

    for _ in range(k):
        best_profit = -1
        best_idx = -1

        for i in range(n):
            if not done[i] and capital[i] <= w:
                if profits[i] > best_profit:
                    best_profit = profits[i]
                    best_idx = i

        if best_idx == -1:
            break  # can't afford any project

        done[best_idx] = True
        w += best_profit

    return w


print(findMaximizedCapital(2, 0, [1, 2, 3], [0, 1, 1]))  # 4
print(findMaximizedCapital(3, 0, [1, 2, 3], [0, 1, 2]))  # 6
print(findMaximizedCapital(1, 0, [1, 2, 3], [1, 1, 2]))  # 0 (can't afford any)

Complexity

• Time: O(n * k) — scan all n projects for each of k rounds
• Space: O(n)

2. Two Heaps — Greedy Optimal

Intuition

We want to greedily pick the highest-profit affordable project in each round. The key insight: sort projects by capital requirement. Use a min-heap by capital (locked) to efficiently release projects as our wallet grows. Each round, push all newly affordable projects (capital ≤ w) onto a max-heap by profit (available). Then pop the most profitable available project, collect its profit, and repeat.

This is essentially a “sweep” — as w grows, more projects unlock and flow from the locked heap to the available heap.

Algorithm

1. Build locked = [(capital[i], profits[i]) for i in range(n)] as a min-heap.
2. available is a max-heap (negate profits) of projects we can currently afford.
3. Repeat at most k times: a. While locked is non-empty and locked[0][0] <= w, pop it and push -profit onto available. b. If available is empty, break (can’t afford anything). c. Pop the most profitable from available, add its profit to w.
4. Return w.

Solution

import heapq

def findMaximizedCapital(k, w, profits, capital):
    # Min-heap of locked projects sorted by capital requirement
    locked = list(zip(capital, profits))
    heapq.heapify(locked)

    available = []  # Max-heap of profits for affordable projects (negated)

    for _ in range(k):
        # Unlock all projects we can now afford
        while locked and locked[0][0] <= w:
            cap, profit = heapq.heappop(locked)
            heapq.heappush(available, -profit)

        if not available:
            break  # Can't unlock any new project

        # Take the highest-profit available project
        w += -heapq.heappop(available)

    return w


print(findMaximizedCapital(2, 0, [1, 2, 3], [0, 1, 1]))  # 4
print(findMaximizedCapital(3, 0, [1, 2, 3], [0, 1, 2]))  # 6
print(findMaximizedCapital(1, 0, [1, 2, 3], [1, 1, 2]))  # 0
print(findMaximizedCapital(2, 1, [2, 3, 5], [0, 1, 2]))  # 9: pick profit 3 (w=4), then profit 5 (w=9)

Complexity

• Time: O(n log n + k log n) — heapify is O(n log n); each of k rounds does O(log n) heap ops
• Space: O(n)

Common Pitfalls

Not unlocking all affordable projects before picking. In each round, you should push every project with capital <= w onto the available heap before selecting. If you push only one and then select, you might miss a higher-profit project that was also affordable.

Confusing which heap uses negation. The locked heap is a min-heap by capital (no negation needed). The available heap is a max-heap by profit (negate profits). Keep this straight or you’ll pick the wrong project each round.

Stopping too early when locked is empty but available is not. Just because there are no more projects to unlock doesn’t mean we’re done — we might still have profitable projects sitting in available from previous rounds. Only break when available is empty.