Skip to main content
CodePeetCodePeet
CodePeet 250

IPO

HARDProblemSolveExternal Links

Description

You are given n projects, each described by two values: a minimum capital requirement and a pure profit. You start with an initial capital w. You can complete at most k distinct projects. When you finish a project, its profit is added to your total capital.

Importantly, the capital requirement is only a threshold — it is not consumed or spent. You simply need to have at least that much capital to begin the project. After completing a project, your capital grows by the profit amount, potentially unlocking access to more expensive projects.

Your goal is to select and complete at most k projects in the best possible order to maximize your final capital.

Examples

Example 1

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

Output: 4

Explanation: We start with capital 0. The only project we can afford is project 0 (requires capital 0, profit 1). After completing it, our capital becomes 0 + 1 = 1. Now we can afford project 1 (requires 1, profit 2) and project 2 (requires 1, profit 3). Since we want to maximize capital and can pick only 1 more project (k=2 total), we pick project 2 with profit 3. Final capital = 1 + 3 = 4.

Example 2

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

Output: 6

Explanation: Start with capital 0. Pick project 0 (requires 0, profit 1) → capital becomes 1. Pick project 1 (requires 1, profit 2) → capital becomes 3. Pick project 2 (requires 2, profit 3) → capital becomes 6. We completed all 3 projects in order, each unlocking the next.

Example 3

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

Output: 0

Explanation: All projects require at least capital 1, but we start with 0. We cannot afford any project, so our final capital remains 0. This edge case shows that when no project is affordable, the initial capital is returned unchanged.

Constraints

  • 1 ≤ k ≤ 10^5
  • 0 ≤ w ≤ 10^9
  • n == profits.length
  • n == capital.length
  • 1 ≤ n ≤ 10^5
  • 0 ≤ profits[i] ≤ 10^4
  • 0 ≤ capital[i] ≤ 10^9
  • The answer is guaranteed to fit in a 32-bit signed integer.

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is: at each step, look at all the projects you can currently afford, pick the one with the highest profit, complete it, add the profit to your capital, and repeat up to k times.

Imagine you are an investor with a limited budget. Every round, you scan through every available investment opportunity, check which ones you can afford, and pick the most profitable one. After cashing out, you repeat the process with your updated budget.

For each of the k rounds, we scan all n projects to find affordable ones, then pick the best. This requires tracking which projects have already been used so we don't repeat them.

Step-by-Step Explanation

Let's trace through with k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]:

Step 1: Initialize current capital w = 0. Mark all projects as available: used = [false, false, false].

Step 2 (Round 1): Scan all projects for affordable ones:

  • Project 0: capital[0] = 0 ≤ 0? Yes → affordable, profit = 1
  • Project 1: capital[1] = 1 ≤ 0? No → skip
  • Project 2: capital[2] = 1 ≤ 0? No → skip
  • Best affordable profit = 1 (project 0)

Step 3: Complete project 0. w = 0 + 1 = 1. Mark project 0 as used.

Step 4 (Round 2): Scan all projects for affordable ones (skip used):

  • Project 0: used → skip
  • Project 1: capital[1] = 1 ≤ 1? Yes → affordable, profit = 2
  • Project 2: capital[2] = 1 ≤ 1? Yes → affordable, profit = 3
  • Best affordable profit = 3 (project 2)

Step 5: Complete project 2. w = 1 + 3 = 4. Mark project 2 as used.

Step 6: k = 2 rounds completed. Return w = 4.

Brute Force — Scanning All Projects Each Round — Watch how each round scans every project to find affordable ones, then picks the most profitable. Profits and capitals are shown as paired arrays.

Algorithm

  1. Create a boolean array used of size n, initialized to false
  2. Repeat up to k times:
    a. Scan all projects to find the one with the highest profit among those that are affordable (capital[i] ≤ w) and not yet used
    b. If no affordable project exists, stop early
    c. Add the selected project's profit to w
    d. Mark the selected project as used
  3. Return w

Code

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<bool> used(n, false);
        
        for (int round = 0; round < k; round++) {
            int bestIdx = -1;
            int bestProfit = -1;
            
            for (int i = 0; i < n; i++) {
                if (!used[i] && capital[i] <= w && profits[i] > bestProfit) {
                    bestIdx = i;
                    bestProfit = profits[i];
                }
            }
            
            if (bestIdx == -1) break;
            
            w += bestProfit;
            used[bestIdx] = true;
        }
        
        return w;
    }
};
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:
        n = len(profits)
        used = [False] * n
        
        for round_num in range(k):
            best_idx = -1
            best_profit = -1
            
            for i in range(n):
                if not used[i] and capital[i] <= w and profits[i] > best_profit:
                    best_idx = i
                    best_profit = profits[i]
            
            if best_idx == -1:
                break
            
            w += best_profit
            used[best_idx] = True
        
        return w
class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        boolean[] used = new boolean[n];
        
        for (int round = 0; round < k; round++) {
            int bestIdx = -1;
            int bestProfit = -1;
            
            for (int i = 0; i < n; i++) {
                if (!used[i] && capital[i] <= w && profits[i] > bestProfit) {
                    bestIdx = i;
                    bestProfit = profits[i];
                }
            }
            
            if (bestIdx == -1) break;
            
            w += bestProfit;
            used[bestIdx] = true;
        }
        
        return w;
    }
}

Complexity Analysis

Time Complexity: O(k × n)

We perform up to k rounds. In each round, we scan all n projects to find the best affordable one. Each scan is O(n), giving us O(k × n) total. With k and n both up to 10^5, this is 10^10 operations — far too slow.

Space Complexity: O(n)

We use a boolean array of size n to track used projects.

Why This Approach Is Not Efficient

The brute force approach performs O(k × n) work because it re-scans all n projects in every round. With both k and n up to 10^5, this leads to up to 10^10 operations, which is far beyond the typical ~10^8 operations-per-second limit.

The root inefficiency is twofold:

  1. Repeated scanning: Every round re-checks projects that haven't become newly affordable. If our capital only went from 5 to 8, we don't need to re-check projects requiring capital 0–5 — they were already checked last round.

  2. Linear max-finding: Among affordable projects, finding the maximum profit takes O(n) each time. A data structure that maintains the maximum efficiently (like a max-heap) could reduce this to O(log n).

The key insight is: if we sort or organize projects by their capital requirement, we can progressively unlock projects as our capital grows — and use a max-heap to always pick the most profitable affordable project in O(log n) time.

Better Approach - Sorting with Linear Scan

Intuition

Instead of scanning all projects every round, we can sort projects by their capital requirement. This way, as our capital grows, we simply advance a pointer through the sorted list to find newly affordable projects.

For each round, we move the pointer forward to include all projects whose capital requirement is at most our current capital, then find the maximum profit among all unlocked projects.

Think of it like a store where products are arranged by price. As your budget increases, you walk further down the aisle to see more options. You don't re-check items you already passed — you just look at the new ones and pick the best from everything you've unlocked so far.

This avoids re-scanning already-checked projects, but still requires finding the max profit among all unlocked projects each round.

Step-by-Step Explanation

Let's trace with k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]:

Step 1: Pair and sort by capital: [(0,1), (1,2), (1,3)]. Pointer p = 0.

Step 2 (Round 1): Advance pointer while capital[p] ≤ w=0:

  • (0,1): 0 ≤ 0 → unlock. p moves to 1.
  • (1,2): 1 ≤ 0? No → stop.
  • Unlocked profits so far: [1]. Find max = 1.

Step 3: Select profit 1. w = 0 + 1 = 1. Remove profit 1 from unlocked pool.

Step 4 (Round 2): Advance pointer while capital[p] ≤ w=1:

  • (1,2): 1 ≤ 1 → unlock. p moves to 2.
  • (1,3): 1 ≤ 1 → unlock. p moves to 3.
  • Unlocked profits so far: [2, 3]. Find max = 3.

Step 5: Select profit 3. w = 1 + 3 = 4.

Step 6: k = 2 rounds done. Return w = 4.

Algorithm

  1. Create pairs of (capital[i], profits[i]) and sort by capital requirement
  2. Initialize pointer p = 0 and a list of unlocked profits
  3. Repeat up to k times:
    a. While p < n and sorted_capital[p] ≤ w: add sorted_profit[p] to the unlocked pool, increment p
    b. If unlocked pool is empty, stop
    c. Find the maximum profit in the unlocked pool, add it to w, remove it from the pool
  4. Return w

Code

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        vector<pair<int,int>> projects(n);
        for (int i = 0; i < n; i++) {
            projects[i] = {capital[i], profits[i]};
        }
        sort(projects.begin(), projects.end());
        
        vector<int> unlocked;
        int p = 0;
        
        for (int round = 0; round < k; round++) {
            while (p < n && projects[p].first <= w) {
                unlocked.push_back(projects[p].second);
                p++;
            }
            
            if (unlocked.empty()) break;
            
            auto it = max_element(unlocked.begin(), unlocked.end());
            w += *it;
            unlocked.erase(it);
        }
        
        return w;
    }
};
class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:
        n = len(profits)
        projects = sorted(zip(capital, profits))
        
        unlocked = []
        p = 0
        
        for _ in range(k):
            while p < n and projects[p][0] <= w:
                unlocked.append(projects[p][1])
                p += 1
            
            if not unlocked:
                break
            
            max_idx = unlocked.index(max(unlocked))
            w += unlocked[max_idx]
            unlocked.pop(max_idx)
        
        return w
class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] projects = new int[n][2];
        for (int i = 0; i < n; i++) {
            projects[i][0] = capital[i];
            projects[i][1] = profits[i];
        }
        Arrays.sort(projects, (a, b) -> a[0] - b[0]);
        
        List<Integer> unlocked = new ArrayList<>();
        int p = 0;
        
        for (int round = 0; round < k; round++) {
            while (p < n && projects[p][0] <= w) {
                unlocked.add(projects[p][1]);
                p++;
            }
            
            if (unlocked.isEmpty()) break;
            
            int maxIdx = 0;
            for (int i = 1; i < unlocked.size(); i++) {
                if (unlocked.get(i) > unlocked.get(maxIdx)) {
                    maxIdx = i;
                }
            }
            w += unlocked.get(maxIdx);
            unlocked.remove(maxIdx);
        }
        
        return w;
    }
}

Complexity Analysis

Time Complexity: O(n log n + k × n)

Sorting takes O(n log n). The pointer advances at most n times total across all rounds (each project is unlocked once). However, finding the maximum in the unlocked pool still takes O(n) per round in the worst case, giving O(k × n) for the selection phase. Total: O(n log n + k × n).

Space Complexity: O(n)

We store all projects in a sorted array and maintain an unlocked pool of up to n profits.

Why This Approach Is Not Efficient

The sorting improvement helps avoid re-scanning projects that are clearly too expensive, but the bottleneck remains: finding the maximum profit among unlocked projects is still O(n) per round.

In the worst case where all projects are affordable from the start, we have n items in the unlocked pool and need to find the max k times, costing O(k × n) — which can still be 10^10.

The insight is: we don't need to scan the entire pool each time. If we store the unlocked profits in a max-heap (priority queue), extracting the maximum becomes O(log n) instead of O(n). Combined with the sorted-order pointer trick, this brings the total down to O(n log n).

Optimal Approach - Greedy with Two Heaps

Intuition

The optimal approach combines two ideas:

  1. Min-heap for capital requirements: Store all projects in a min-heap ordered by capital requirement. This lets us efficiently pop off all projects that become affordable when our capital increases.

  2. Max-heap for profits: Store profits of affordable projects in a max-heap. This lets us instantly grab the most profitable project in O(log n).

The greedy strategy is provably optimal: at each step, we pick the project with the highest profit among all affordable ones. This is correct because:

  • Profits are pure gains — capital requirements are thresholds, not costs
  • More capital never restricts us — it only opens more opportunities
  • Maximizing capital at each step gives the best chance to unlock high-profit projects later

The two-heap interplay works beautifully: as our capital grows after each project, we drain the min-heap of all newly affordable projects and dump their profits into the max-heap. Then we pop the max-heap to select the best option.

Step-by-Step Explanation

Let's trace with k = 2, w = 0, profits = [1, 2, 3], capital = [0, 1, 1]:

Step 1: Build min-heap from (capital, profit) pairs: [(0,1), (1,2), (1,3)]. Create empty max-heap for profits.

Step 2 (Round 1): Move affordable projects from min-heap to max-heap:

  • Top of min-heap: (0,1). Is 0 ≤ w(0)? Yes → pop and push profit 1 into max-heap.
  • Top of min-heap: (1,2). Is 1 ≤ w(0)? No → stop.
  • Max-heap: [1].

Step 3: Pop max-heap → 1. w = 0 + 1 = 1.

Step 4 (Round 2): Move affordable projects:

  • Top of min-heap: (1,2). Is 1 ≤ w(1)? Yes → pop, push profit 2.
  • Top of min-heap: (1,3). Is 1 ≤ w(1)? Yes → pop, push profit 3.
  • Min-heap empty.
  • Max-heap: [3, 2].

Step 5: Pop max-heap → 3. w = 1 + 3 = 4.

Step 6: k=2 rounds done. Return w = 4.

Greedy Two-Heap Selection — Min-Heap Unlocks, Max-Heap Selects — Watch how the min-heap progressively releases affordable projects into the max-heap as capital grows, and the max-heap always yields the most profitable choice.

Algorithm

  1. Create a min-heap of (capital[i], profits[i]) pairs for all n projects
  2. Create an empty max-heap for storing profits of affordable projects
  3. Repeat up to k times:
    a. While the min-heap is not empty and the top element's capital ≤ w:
    • Pop from min-heap and push its profit into the max-heap
      b. If the max-heap is empty, break (no affordable projects remain)
      c. Pop the maximum profit from the max-heap and add it to w
  4. Return w

Code

class Solution {
public:
    int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
        int n = profits.size();
        
        // Min-heap: (capital_required, profit)
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> minHeap;
        for (int i = 0; i < n; i++) {
            minHeap.push({capital[i], profits[i]});
        }
        
        // Max-heap: profits of affordable projects
        priority_queue<int> maxHeap;
        
        for (int round = 0; round < k; round++) {
            // Transfer all newly affordable projects
            while (!minHeap.empty() && minHeap.top().first <= w) {
                maxHeap.push(minHeap.top().second);
                minHeap.pop();
            }
            
            if (maxHeap.empty()) break;
            
            w += maxHeap.top();
            maxHeap.pop();
        }
        
        return w;
    }
};
import heapq

class Solution:
    def findMaximizedCapital(self, k: int, w: int, profits: list[int], capital: list[int]) -> int:
        # Min-heap: (capital_required, profit)
        min_heap = [(c, p) for c, p in zip(capital, profits)]
        heapq.heapify(min_heap)
        
        # Max-heap: profits of affordable projects (negated for max behavior)
        max_heap = []
        
        for _ in range(k):
            # Transfer all affordable projects to max-heap
            while min_heap and min_heap[0][0] <= w:
                cap_req, profit = heapq.heappop(min_heap)
                heapq.heappush(max_heap, -profit)
            
            if not max_heap:
                break
            
            # Select the most profitable project
            w += -heapq.heappop(max_heap)
        
        return w
class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        
        // Min-heap: sorted by capital requirement
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < n; i++) {
            minHeap.offer(new int[]{capital[i], profits[i]});
        }
        
        // Max-heap: profits of affordable projects
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        for (int round = 0; round < k; round++) {
            // Transfer all affordable projects
            while (!minHeap.isEmpty() && minHeap.peek()[0] <= w) {
                maxHeap.offer(minHeap.poll()[1]);
            }
            
            if (maxHeap.isEmpty()) break;
            
            w += maxHeap.poll();
        }
        
        return w;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Building the min-heap takes O(n). Across all k rounds, each of the n projects is popped from the min-heap and pushed into the max-heap at most once — each operation is O(log n), totaling O(n log n). Each of the k rounds also pops once from the max-heap, costing O(k log n). Since k ≤ n, the dominant term is O(n log n).

Space Complexity: O(n)

Both heaps together hold at most n elements total. The min-heap starts with n elements and shrinks as items move to the max-heap. At any point, min-heap size + max-heap size ≤ n.