IPO — Greedy Capital Maximization with Two Heaps

Problem Statement#

Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to venture capital, LeetCode hopes 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.

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital capital[i] required to start it. Initially, you have w capital and can choose a project.

After finishing a project, the profit will be added to your total capital. Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the maximized capital.

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

Examples:

Input:  k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
Output: 4
 
Explanation:
  Initial capital w = 0.
  Project 0 (profit=1, capital=0): affordable, take it. w = 1.
  Project 2 (profit=3, capital=1): affordable, take it. w = 4.
  After 2 projects, capital = 4.

Input:  k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
Output: 6
 
Explanation:
  Take project 0: w → 1
  Take project 1: w → 3
  Take project 2: w → 6

Input:  k = 1, w = 0, profits = [1,2,3], capital = [1,1,2]
Output: 0
 
Explanation: Cannot afford any project with w=0.

Why This Problem Matters#

IPO is a hard problem that Google, Amazon, and Facebook use to test sophisticated greedy reasoning with two data structures working in concert. It requires you to recognize a two-phase greedy pattern: first unlock eligible projects (sorted by required capital), then greedily pick the best available one (highest profit).

The problem models a real portfolio optimization scenario: you start with limited capital, invest in projects to grow it, and want to maximize wealth after k investments. This is directly applicable in venture capital, phased project management, and resource-constrained optimization.

The two-heap design is elegant:

• A min-heap sorted by capital acts as a "locked" pool — projects you can't afford yet.
• A max-heap sorted by profit acts as an "unlocked" pool — projects you can currently afford.

Each round, you move all newly affordable projects from the locked pool to the unlocked pool, then pick the highest-profit project from the unlocked pool. Capital only increases, so once unlocked, a project stays unlocked — this is the key property that makes the greedy correct.

This pattern appears in "Course Schedule III" (unlock courses as time progresses), "Minimum Number of Refueling Stops" (unlock gas stations as you pass them), and many resource-constrained scheduling problems.

The Core Insight#

Two-heap structure:

1. Min-heap by capital: (required_capital, profit) — represents projects locked because you can't afford them yet.
2. Max-heap by profit (negated): (-profit) — represents projects you can currently afford.

Algorithm per round:

1. Move all projects with required_capital <= current_capital from the capital min-heap to the profit max-heap.
2. If the profit max-heap is non-empty, pop the highest-profit project and add it to capital.
3. If the profit max-heap is empty, no affordable project exists — stop early.

Why greedy is optimal: After unlocking all affordable projects, picking the highest profit is clearly optimal — you want maximum capital growth per round. More capital only unlocks more projects, so there is never a reason to pick a lower-profit project to "save" the high-profit one for later.

k=2, w=0, profits=[1,2,3], capital=[0,1,1]
 
Initial capital heap (sorted by capital):
  (0,1), (1,2), (1,3)
 
Initial profit heap: []
 
Round 1: w=0
  Unlock: (0,1) → profit_heap=[(-1)]
  Pick max profit = 1 → w = 0+1 = 1
 
Round 2: w=1
  Unlock: (1,2),(1,3) → profit_heap=[(-2),(-3)]
  Pick max profit = 3 → w = 1+3 = 4
 
Final capital = 4

Visual Dry Run#

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

Paired: [(0,1),(1,2),(2,3)] sorted by capital.

Final capital: 6

Edge case — k=1, w=0, all capital > 0:

Return w = 0.

Solution (Optimal)#

import heapq
 
def findMaximizedCapital(k: int, w: int, profits: list[int], capital: list[int]) -> int:
    # Create paired (capital, profit) and sort by capital
    projects = sorted(zip(capital, profits), key=lambda x: x[0])
 
    max_profit_heap = []    # max-heap of profits for affordable projects (negated)
    i = 0                   # pointer into sorted projects
 
    for _ in range(k):
        # Unlock all projects we can now afford
        while i < len(projects) and projects[i][0] <= w:
            heapq.heappush(max_profit_heap, -projects[i][1])
            i += 1
 
        # Pick the most profitable affordable project
        if not max_profit_heap:
            break   # no affordable project — stop early
 
        w -= heapq.heappop(max_profit_heap)  # add profit (negate the negated value)
 
    return w

function findMaximizedCapital(k, w, profits, capital) {
    const n = profits.length;
 
    // Sort projects by required capital
    const projects = profits.map((p, i) => [capital[i], p]);
    projects.sort((a, b) => a[0] - b[0]);
 
    // Max-heap of profits (sorted descending for max access)
    const available = [];
 
    const insertMaxHeap = (profit) => {
        let lo = 0, hi = available.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (available[mid] < profit) hi = mid;
            else lo = mid + 1;
        }
        available.splice(lo, 0, profit);
    };
 
    let i = 0;
 
    for (let round = 0; round < k; round++) {
        // Unlock newly affordable projects
        while (i < projects.length && projects[i][0] <= w) {
            insertMaxHeap(projects[i][1]);
            i++;
        }
 
        if (available.length === 0) break;  // no affordable project
 
        // Pick highest-profit project
        w += available[0];
        available.shift();
    }
 
    return w;
}

Complexity Analysis:

Sorting projects is O(n log n). Each project is pushed to the profit heap at most once (O(log n) each). Each of k rounds does one pop from the profit heap (O(log n)). Total: O(n log n + k log n) = O((n+k) log n).

Common Mistakes#

• Not sorting projects by capital. Without sorting, you can't efficiently find newly affordable projects as capital grows.
• Using a min-heap for profits. You want the maximum profit at each round, so negate profits when pushing to Python's min-heap, or use a custom max-heap.
• Moving i pointer backwards. Since capital only increases (never decreases), once a project is unlocked it stays unlocked. The pointer i only moves forward.
• Forgetting the break when no affordable projects exist. If max_profit_heap is empty after unlocking, you can't make any progress — break early. Without this, the loop runs k times unnecessarily.
• Sign error in Python. heapq.heappush(max_profit_heap, -profit) pushes negative values. When popping: w -= heapq.heappop(max_profit_heap) where the popped value is negative, so -= negative is effectively += positive. Double-check the signs.

Follow-up Questions#

• What if you can reinvest in the same project multiple times? Allow revisiting by not tracking which projects were taken. In Python, don't filter the heap for uniqueness.
• What if capital can decrease (e.g., some projects have negative profit)? The greedy still works — simply never pick negative-profit projects. Add a check: only pop from the profit heap if the top profit is positive.
• What if you want to minimize capital instead of maximize? Sort projects by profit ascending, maintain a min-heap of required capitals, and greedy select the cheapest available project per round.
• How does this differ from Course Schedule III? In Course Schedule III, you unlocked courses as time progressed (sorted by deadline). Here, you unlock projects as capital grows (sorted by required capital). The same two-phase greedy pattern, different triggering condition.
• What if k > n? You can take at most n projects total. The algorithm handles this: after all projects are processed, the loop ends due to the empty profit heap.

Related Problems#

• 502. IPO — this problem.
• 630. Course Schedule III — same two-phase greedy with time as the resource instead of capital.
• 1235. Maximum Profit in Job Scheduling — jobs with start/end times and profits, requires DP.
• 1167. Minimum Cost to Connect Sticks — different greedy, min-heap merging pattern.
• 295. Find Median from Data Stream — another two-heap design problem.
• 871. Minimum Number of Refueling Stops — greedy with a max-heap of fuel amounts at passed stations.

Key Takeaways#

• IPO uses two heaps: a min-heap sorted by required capital (locked pool) and a max-heap sorted by profit (unlocked pool)
• Each round: move all affordable projects from locked to unlocked pool, then pick the highest-profit project
• Capital only increases — once a project is unlocked it stays unlocked; the pointer into sorted projects only moves forward
• Greedy is optimal: after unlocking all affordable projects, picking the highest profit is always the best choice
• Early termination: if the profit heap is empty after unlocking, no affordable project exists — break immediately
• Time O(n log n + k log n), space O(n) — sorting plus k heap operations
• This "unlock as resource grows" two-heap pattern applies to LC 630, LC 871, and any phased resource-constrained scheduling