IPO

Problem Description

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

You are given n projects where the ith project has a pure profit profits[i] and a minimum capital of capital[i] is needed 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.

Return the maximized final capital after finishing at most k distinct projects.

Examples

Constraints

• 1 ≤ k ≤ 10⁵
• 0 ≤ w ≤ 10⁹
• n == profits.length == capital.length
• 1 ≤ n ≤ 10⁵
• 0 ≤ profits[i] ≤ 10⁴
• 0 ≤ capital[i] ≤ 10⁹

Two Heaps: Available Projects, Best Profit

You can only do a project if your current capital meets its minimum requirement. Among all affordable projects, you want the one with the highest profit. The greedy choice is always: do the highest-profit affordable project.

Use two heaps:

1. Min-heap sorted by capital requirement (all projects, sorted by how much you need to start them).
2. Max-heap sorted by profit (only projects you can currently afford).

Each round: move all newly affordable projects (capital requirement ≤ current w) from the min-heap to the max-heap. Then pick the best profit project from the max-heap, add its profit to w. Repeat k times.

Solution: Two-Heap Greedy

import java.util.*;

class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        // min-heap by capital requirement
        PriorityQueue<int[]> available = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            available.offer(new int[]{capital[i], profits[i]});
        }

        // max-heap by profit (projects we can afford right now)
        PriorityQueue<Integer> affordable = new PriorityQueue<>(Collections.reverseOrder());

        for (int i = 0; i < k; i++) {
            // unlock all projects now affordable
            while (!available.isEmpty() && available.peek()[0] <= w) {
                affordable.offer(available.poll()[1]);
            }

            if (affordable.isEmpty()) break; // no affordable projects left

            w += affordable.poll(); // pick the highest profit project
        }

        return w;
    }
}

import heapq

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:
        # min-heap by capital requirement
        available = sorted(zip(capital, profits))  # [(capital, profit), ...]
        available = [(c, p) for c, p in available]
        heapq.heapify(available)

        # max-heap by profit (negate for Python's min-heap)
        affordable = []
        idx = 0
        projects = sorted(zip(capital, profits))

        # rebuild as proper min-heap
        available = list(zip(capital, profits))
        heapq.heapify(available)
        affordable = []  # max-heap (negated profits)

        for _ in range(k):
            while available and available[0][0] <= w:
                cap, profit = heapq.heappop(available)
                heapq.heappush(affordable, -profit)

            if not affordable:
                break

            w += -heapq.heappop(affordable)

        return w

#include <vector>
#include <queue>

class Solution {
public:
    int findMaximizedCapital(int k, int w, std::vector<int>& profits, std::vector<int>& capital) {
        int n = profits.size();
        // min-heap by capital requirement: {capital, profit}
        std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>,
                            std::greater<>> available;
        for (int i = 0; i < n; i++) {
            available.push({capital[i], profits[i]});
        }

        // max-heap by profit
        std::priority_queue<int> affordable;

        for (int i = 0; i < k; i++) {
            while (!available.empty() && available.top().first <= w) {
                affordable.push(available.top().second);
                available.pop();
            }
            if (affordable.empty()) break;
            w += affordable.top();
            affordable.pop();
        }

        return w;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n + k log n). Building the min-heap is O(n log n). Each project is moved from available to affordable at most once (O(n log n) total), and each of the k selections costs O(log n).
• Space Complexity: O(n) for the two heaps.

Where it breaks: if w starts large enough to afford all projects, the available heap drains into the affordable heap on the first iteration and you simply pick the top k profits. If k > n, you can’t do more than n projects, so the affordable heap might empty before k rounds. The if affordable.isEmpty(): break handles this.

Common Mistakes

• Sorting projects by profit and greedily picking the highest profit each time without checking capital requirements. This ignores the constraint that you must afford a project before doing it.
• Forgetting to break when no affordable projects remain. Without the break, you’d loop k times doing nothing and return the unchanged w.
• Using capital directly as profit or vice versa when indexing.

Frequently Asked Questions

Why is the greedy choice correct? At each step, picking the highest-profit affordable project maximizes the capital gained in that round. More capital now unlocks more projects later. There’s no benefit to skipping a high-profit affordable project in favor of a lower-profit one.

What if k is larger than n? You can do at most n projects. The algorithm terminates naturally when the affordable heap is empty and no more projects can be unlocked.

← All Problems