Given an initial capital w, a project limit k, a profits array, and a capital array, the project at index earns profits[index] and requires at least capital[index] before starting. Complete at most k distinct projects and return the maximum final capital. Every completed profit is added immediately to the available capital.
Example 1
Input: k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]
Output: 4
Explanation: Capital 0 permits only project 0, raising the capital to 1. Projects 1 and 2 then become affordable, and project 2 raises the final capital to 4.
Example 2
Input: k = 2, w = 0, profits = [2, 3], capital = [1, 2]
Output: 0
Explanation: No project is affordable with capital 0, so no selection can increase the starting capital.
Brute Force Approach
The simplest idea explores every affordable project at each selection. A chosen project raises the current capital, and the same search continues with one fewer available selection.
A used array prevents repeated project selection. Every recursive state keeps the remaining selection count and current capital, while the largest result among all affordable choices becomes the state answer.
Algorithm
Begin with a
usedarray filled withfalsebecause every project must remain available exactly once before selection.Define a recursive search using
remainingandcurrentCapitalbecause both values fully describe the next project decision.Return
currentCapitalafterremainingreaches zero because the allowed number of selections has been exhausted.Keep
bestCapitalequal tocurrentCapitalbecause stopping early must remain valid under the at-most-krule.Try every unused affordable project because any eligible choice can unlock a different profitable sequence.
Mark a chosen project, add the matching profit, and recurse with one fewer selection so the branch records project completion.
Restore the chosen mark after recursion because later branches need the original project availability.
Return the largest branch result because maximum final capital is the required objective.
Dry Run
ipo-brute-force-approach
Solution
#include <bits/stdc++.h>using namespace std;class Solution {private: // Explores every affordable project sequence int search(int remaining, int currentCapital, vector<int>& profits, vector<int>& capital, vector<bool>& used) { // No remaining choice can increase the answer if (remaining == 0) { return currentCapital; } // Early stopping remains valid for at most k picks int bestCapital = currentCapital; // Try every project available for the current state for (int index = 0; index < profits.size(); index++) { // Used or unaffordable projects are invalid choices if (used[index] || capital[index] > currentCapital) { continue; } // Reserve the project for the current branch used[index] = true; // Add profit before exploring the next selection int nextCapital = currentCapital + profits[index]; // Explore every sequence after the chosen project int candidate = search( remaining - 1, nextCapital, profits, capital, used ); // Keep the strongest completed project sequence bestCapital = max(bestCapital, candidate); // Restore availability for the next branch used[index] = false; } // Return the best reachable capital for the state return bestCapital; }public: // Returns maximum capital after at most k projects int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) { // Track projects already selected by a branch vector<bool> used(profits.size(), false); // Start before any project selection return search(k, w, profits, capital, used); }};// Driver codeint main() { int k = 2; int w = 0; vector<int> profits = {1, 2, 3}; vector<int> capital = {0, 1, 1}; Solution obj; cout << obj.findMaximizedCapital( k, w, profits, capital ) << endl; return 0;}Note: The large branching factor creates exponential/factorial search, so direct recursion may fail for large inputs.
Complexity Analysis
Time Complexity: O(ND), where N is the number of projects and D = min(k, N) is the maximum number of projects that can be selected. Each recursive level may try up to N projects.
Space Complexity: O(N + D), because the used array stores N entries and the recursion stack reaches at most D = min(k, N) levels.
Optimal Approach
Backtracking repeats the same selection work across many project orders. Sorting projects by required capital creates one forward-moving boundary, so every newly affordable project enters consideration exactly once.
A max-heap stores profits from all affordable unselected projects. Choosing the largest available profit gives the greatest immediate capital increase, and a larger current capital can only preserve or expand the set of affordable future projects.
Algorithm
Pair every capital requirement with its corresponding profit so each project remains intact while sorting.
Sort all projects by required capital so affordable projects can be discovered using a single forward-moving pointer.
Keep a max-heap of profits from all currently affordable projects.
Repeat at most
ktimes, because at mostkprojects can be completed.Starting from the pointer's current position, move all newly affordable projects with required capital at most
winto the max-heap.Do not restart the scan from the beginning; the pointer continues from where it stopped in the previous iteration.
If the max-heap is empty, stop because no remaining project can be started with the current capital.
Remove the largest profit from the heap and add it to
w.Continue from the same pointer position in the next iteration to add any projects that became affordable after the capital increased.
Return
wafter completing at mostkprojects or when no more projects can be selected.
Dry Run
IPO Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Returns maximum capital with sorting and a heap int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) { // Pair every requirement with the matching profit vector<pair<int, int>> projects; for (int index = 0; index < profits.size(); index++) { projects.push_back({capital[index], profits[index]}); } // Expose projects in increasing capital order sort(projects.begin(), projects.end()); // Keep the largest affordable profit at the top priority_queue<int> maxHeap; int index = 0; // Complete at most k distinct projects for (int selection = 0; selection < k; selection++) { // Add every project newly affordable with w while (index < projects.size() && projects[index].first <= w) { maxHeap.push(projects[index].second); index++; } // No affordable project can increase capital if (maxHeap.empty()) { break; } // Choose the strongest currently available gain w += maxHeap.top(); maxHeap.pop(); } // Return capital after all reachable selections return w; }};// Driver codeint main() { int k = 2; int w = 0; vector<int> profits = {1, 2, 3}; vector<int> capital = {0, 1, 1}; Solution obj; cout << obj.findMaximizedCapital( k, w, profits, capital ) << endl; return 0;}Complexity Analysis
Time Complexity: O(N log N), where N is the number of projects, because sorting takes O(N log N) and every project enters and leaves the max-heap at most once.
Space Complexity: O(N), because the sorted project records and max-heap can each store up to N entries.
Interview follow-up Questions
No. Required capital acts only as an eligibility threshold. Project completion adds profit without subtracting the required amount.
Be the first to add a comment.