IPO

Problem

You start with capital w and may complete at most k projects before an IPO. Project i requires at least capital[i] capital on hand to start, and completing it adds a pure profit of profits[i] to your capital (the required capital is a threshold, not a cost — nothing is spent).

Projects can be done in any order, each at most once, one after another. Choose up to k projects to maximize your final capital, and return that maximum.

Examples

• k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] → 4 Only project 0 is affordable at first; finishing it raises capital to 1, unlocking projects 1 and 2. Take project 2 (profit 3) → final capital 0 + 1 + 3 = 4.
• k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] → 6 Enough picks to do everything: 0 → 1 → 2 yields 1 + 2 + 3 = 6.
• k = 2, w = 1, profits = [5,4], capital = [3,3] → 1 No project ever becomes affordable, so the answer is just the starting capital.

Constraints

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

An O(k · n) scan-per-pick is roughly 10^10 operations — the intended solution is O((n + k) log n).

Think about it first

TL;DR

Greedy: sort by required capital + max-heap of unlocked profits — O((n + k) log n) time, O(n) space.

Approach 1 — Brute force: rescan all projects each round

The direct simulation: up to k times, scan every unused project, find the affordable one with the highest profit, take it. The greedy choice itself is already correct here (argued below) — the waste is purely in the scanning.

def findMaximizedCapital(
    self, k: int, w: int, profits: list[int], capital: list[int]
) -> int:
    n = len(profits)
    used = [False] * n
    for _ in range(k):
        best = -1
        for i in range(n):
            if not used[i] and capital[i] <= w:
                if best == -1 or profits[i] > profits[best]:
                    best = i
        if best == -1:  # nothing affordable -> nothing ever will be
            break
        used[best] = True
        w += profits[best]
    return w

Complexity: O(k · n) time, O(n) space.

With k and n both up to 10^5, that is ~10^10 comparisons — the constraints kill it outright.

Why greedy is safe (exchange argument): completing a project never reduces capital (profits are non-negative and the capital requirement is a threshold, not a payment). So taking the highest-profit affordable project now leaves you with at least as much capital as any other choice would — every project affordable under the alternative is affordable under the greedy too. Any optimal schedule can be exchanged, pick by pick, into the greedy one without losing profit.

Approach 2 — Sort by capital + max-heap of profits

The affordable set only ever grows, because capital is monotonically non-decreasing. Rather than re-derive it each round, maintain it incrementally: sort projects by required capital once, keep a pointer i at the first still-locked project, and after each capital increase advance the pointer, pushing each newly unlocked profit into a max-heap. A binary heap gives O(log n) insert and O(log n) extract-max, so “highest profit among unlocked” is one pop. Each project is pushed exactly once across all rounds.

flowchart LR
  A["Projects sorted<br/>by required capital"] -->|"pointer advances<br/>while capital[i] &lt;= w"| B["Max-heap of<br/>unlocked profits"]
  B -->|"pop top profit,<br/>add to w"| C["Repeat up to k times"]
  C -->|"w increased"| A

import heapq


def findMaximizedCapital(
    self, k: int, w: int, profits: list[int], capital: list[int]
) -> int:
    projects = sorted(zip(capital, profits))  # by required capital
    unlocked: list[int] = []  # max-heap of profits, negated
    i = 0
    n = len(projects)
    for _ in range(k):
        while i < n and projects[i][0] <= w:
            heapq.heappush(unlocked, -projects[i][1])
            i += 1
        if not unlocked:
            break  # can't afford anything, and never will
        w -= heapq.heappop(unlocked)  # minus a negative: adds profit
    return w

Walkthrough of k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]:

1. projects = [(0,1), (1,2), (1,3)] after sorting by capital.
2. Round 1: unlock while requirement <= 0 → push profit 1, i = 1. Heap top is 1 → w = 1.
3. Round 2: unlock while requirement <= 1 → push profits 2 and 3, i = 3. Heap is now {2, 3} (profit 1 was consumed in round 1); top is 3 → w = 4.
4. k exhausted → return 4.

Third example (w = 1, both requirements 3): the while-loop unlocks nothing, the heap is empty on round 1, we break immediately and return 1.

Complexity: sorting O(n log n); each project pushed/popped at most once and k pops → O((n + k) log n) time; O(n) space for the sort and heap.

Approach 3 — No-heap special case worth knowing

If w already meets the largest capital requirement, every project is unlocked from the start and the problem collapses to “sum the k largest profits” — solved by sorting profits descending, no heap needed. Interviewers sometimes open with this simplification.

import heapq


def findMaximizedCapital(
    self, k: int, w: int, profits: list[int], capital: list[int]
) -> int:
    if w >= max(capital):  # everything affordable from the start
        return w + sum(sorted(profits, reverse=True)[:k])
    # general case: sort + max-heap (Approach 2)
    projects = sorted(zip(capital, profits))
    unlocked: list[int] = []
    i = 0
    n = len(projects)
    for _ in range(k):
        while i < n and projects[i][0] <= w:
            heapq.heappush(unlocked, -projects[i][1])
            i += 1
        if not unlocked:
            break
        w -= heapq.heappop(unlocked)
    return w

Walkthrough of k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]: w = 0 < max(capital) = 2, so the shortcut does not apply and the heap method runs — rounds unlock and take 1, then 2, then 3, returning 6. The shortcut fires only when affordability is trivial.

Complexity: O(n log n) time, O(n) space when it applies.

Common pitfalls

• Treating capital[i] as money that gets spent: it is only an entry threshold; w never decreases. Subtracting it is the classic mis-read.
• Forgetting the early break when the heap is empty — without it, popping an empty heap raises, and looping k times pointlessly hides the “capital can be permanently stuck” case.
• Sorting by profit instead of by capital: the pointer-unlock trick only works when projects are ordered by their requirement.
• Re-scanning affordability from scratch each round (the O(k·n) trap) — monotonically growing capital means unlocking is one-way and the pointer never moves backward.

Pattern takeaway

When a greedy repeatedly needs “the best option among those currently eligible” and eligibility is monotone (once eligible, always eligible), the recipe is: sort by the unlock key, advance a pointer to feed newly eligible items into a heap keyed by desirability, and pop the heap each round. Two orderings run at once — one by sorting, one by the heap — which is the common structure of scheduling-style heap problems.