Watch 10 video solutions for IPO, a hard level problem involving Array, Greedy, Sorting. This walkthrough by NeetCodeIO has 34,378 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Suppose LeetCode will start its IPO soon. In order to sell a good price of its shares to Venture Capital, 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] 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.
Pick a list of at most k distinct projects from given projects to maximize your final capital, and return the final maximized capital.
The answer is guaranteed to fit in a 32-bit signed integer.
Example 1:
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1] Output: 4 Explanation: Since your initial capital is 0, you can only start the project indexed 0. After finishing it you will obtain profit 1 and your capital becomes 1. With capital 1, you can either start the project indexed 1 or the project indexed 2. Since you can choose at most 2 projects, you need to finish the project indexed 2 to get the maximum capital. Therefore, output the final maximized capital, which is 0 + 1 + 3 = 4.
Example 2:
Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2] Output: 6
Constraints:
1 <= k <= 1050 <= w <= 109n == profits.lengthn == capital.length1 <= n <= 1050 <= profits[i] <= 1040 <= capital[i] <= 109Problem Overview: You start with initial capital w and can complete at most k projects. Each project requires a minimum capital and yields a profit. After finishing a project, the profit is added to your capital. The goal is to choose projects that maximize your final capital.
Approach 1: Dynamic Programming with Memoization (Exponential → O(n * k) states, higher overhead)
This approach models the decision process: at each step, choose a project that can be afforded with the current capital or skip it. Recursion explores combinations of up to k projects while memoization stores intermediate results to avoid recomputation. Although this captures the problem structure clearly, the state depends on remaining projects and capital values, which can grow large. Time complexity is roughly O(n * k) states but with expensive transitions, and space complexity is O(n * k) for the memo table and recursion stack. Useful for understanding the decision space but rarely practical for large inputs.
Approach 2: Greedy with Priority Queue (Sorting + Max Heap) (O(n log n + k log n))
The key observation: whenever multiple projects are affordable, choosing the one with the highest profit always increases future options. Start by pairing each project's capital requirement with its profit and sort them by required capital. Iterate through the list and push all projects whose capital requirement is ≤ current capital into a max heap. This heap stores profits so you can always pick the most profitable available project.
Repeat the process for at most k selections: push newly affordable projects into the heap, then extract the maximum profit and add it to your capital. The heap operations come from a priority queue, while the strategy itself is a classic greedy choice. Sorting costs O(n log n), and each of the at most k heap operations costs O(log n). Space complexity is O(n) for the heap and sorted project list.
Recommended for interviews: The greedy heap solution is the expected answer. Interviewers want to see that you recognize the pattern: sort by capital, push feasible projects into a max heap, and always select the highest profit. Mentioning the dynamic programming interpretation shows problem understanding, but implementing the greedy + priority queue approach demonstrates practical algorithm design skills.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Memoization | O(n * k) states (high transition cost) | O(n * k) | Conceptual exploration of decision space or small constraints |
| Greedy with Sorting + Max Heap | O(n log n + k log n) | O(n) | Optimal solution for large inputs and expected interview answer |