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.

class Solution:
    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 insight: the affordable set only ever grows (capital is monotonically non-decreasing). So instead of re-deriving it each round, maintain it incrementally: sort projects by required capital once, keep a pointer i to the first still-locked project, and after each capital increase slide the pointer forward, dumping each newly unlocked profit into a max-heap. A binary heap — the classic priority queue with O(log n) insert and O(log n) extract-max — hands us “highest profit among unlocked” instantly. Each project is pushed exactly once across all rounds.

import heapq


class Solution:
    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. ✓

And the degenerate 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

The insight: if w already meets the largest capital requirement (or after some prefix of picks it inevitably will, e.g. all requirements are 0), every project is unlocked and the problem collapses to “sum the k largest profits” — solvable by sorting profits descending, no heap at all. Interviewers sometimes probe with this simplification first.

import heapq


class Solution:
    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 this shortcut does not apply and the heap method runs — rounds unlock and take 1, then 2, then 3, returning 6. The shortcut only fires when the affordability question 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. This sort-plus-heap tandem — two orders maintained at once, one by sorting and one by heap — is the signature move of scheduling-style heap problems.