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.
This approach uses a greedy algorithm in conjunction with priority queues to select the projects maximizing profits. The core idea is to iteratively choose the most profitable project that can be initiated with the current available capital.
Initially, projects are stored in a list along with their capital and profit requirements. We prioritize by try fetching the most profitable projects. We maintain available projects in a max-heap (or priority queue) to achieve this efficiently.
We attempt to start at most k projects, updating the available capital every time we include a new project. For every iteration, once we identify the most feasible projects that can be executed given the current capital, we pick and execute the one with the highest profit and update our available capital. This process repeats until no more projects can be started or we've reached k projects.
The solution uses two sorting steps and a manually managed max-heap (priority queue) to maintain the list of feasible projects based on the current capital. Given that C lacks inbuilt data structures for a priority queue, manual sorting is required whenever accessing the max element.
Initially, projects are sorted based on their capital requirements; during each main loop iteration, feasible projects are added to a mock priority queue (sorted array). If projects are listable, the topmost is selected and capital updated accordingly.
Time Complexity: O(N log N + K log N), where N is the number of projects. This involves an initial sort and effectively K max operations on a priority-like structure.
Space Complexity: O(N) due to storage used for auxiliary lists and heaps.
This dynamic programming approach delineates with the constraints arising from the number of projects executable. We maintain an accruing structure documenting the maximum possible capital achievable for the number of projects done. The dynamic programming strategy opts for inherent flexibility where feasible, owing to recursive checks across all projects capable of initiating.
Memoization ensures repeated subproblem results are accessed without re-computation, improving overall efficiency particularly in scenarios involving expedient overlap of capital ranges per project.
Despite the computationally exhaustive exploration of all project combinations, dynamic memorized caching dramatically curtails avoidant efforts during feasibility analysis—gaining crucial strategic leverage with convenience in considering bounded project completion restrictions.
The C solution employs a recursive solution with dynamic programming utilizing memoization. Recursive strategy carefully reviews every set of projects within feasible conditions, referencing precomputed results when similar conditions occur.
The solution includes memoization cache for incremental computational cost alleviation over the choices possible across feasible capital, maximum projects to complete, consequently yielding comprehensive checks on potential project execution paths.
Time Complexity: O(N * W * K) — represents total options reviewed in DP tableau per states, characterized by projects count, capital capability, projects aimed for completion.
Space Complexity: O(N * W) — retains memory for tailored subproblems caching overseeing potential states across projects under capital explored known projects.
| Approach | Complexity |
|---|---|
| Greedy Approach with Priority Queue | Time Complexity: O(N log N + K log N), where N is the number of projects. This involves an initial sort and effectively K max operations on a priority-like structure. Space Complexity: O(N) due to storage used for auxiliary lists and heaps. |
| Dynamic Programming with Memoization | Time Complexity: O(N * W * K) — represents total options reviewed in DP tableau per states, characterized by projects count, capital capability, projects aimed for completion. Space Complexity: O(N * W) — retains memory for tailored subproblems caching overseeing potential states across projects under capital explored known projects. |
| Default Approach | — |
| 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 |
IPO - Leetcode 502 - Python • NeetCodeIO • 34,378 views views
Watch 9 more video solutions →Practice IPO with our built-in code editor and test cases.
Practice on FleetCode