IPO

Hard

#0489Time: O(k * n). The outer loop runs up to `k` times, and the inner loop runs `n` times to find the best project. In the worst case, this leads to `k * n` operations.Space: O(n). We use a boolean array `used` of size `n` to keep track of the projects that have been completed.7 companies

Patterns

Greedy

Algorithms

Sorting

Data structures

Array Heap (Priority Queue)

Companies

Docusign Salesforce Zeta PhonePe

Prompt

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 i^th 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 <= 10⁵
0 <= w <= 10⁹
n == profits.length
n == capital.length
1 <= n <= 10⁵
0 <= profits[i] <= 10⁴
0 <= capital[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process. For each of the k projects we can undertake, we iterate through all available projects to find the best one we can currently afford. The best project is defined as the one that is affordable (its capital requirement is less than or equal to our current capital) and offers the highest profit.

Algorithm

1. Initialize a boolean array used of size n to false to track completed projects.
1. Loop from i = 0 to k-1.
1. Inside the loop, initialize bestProjectIndex = -1 and maxProfit = -1.
1. Iterate through all projects from j = 0 to n-1.
1. If project j is not used and capital[j] <= w:
1. Check if profits[j] is greater than maxProfit. If so, update maxProfit = profits[j] and bestProjectIndex = j.
1. After iterating through all projects, if bestProjectIndex is still -1, it means no project is affordable. Break the outer loop.
1. Otherwise, add profits[bestProjectIndex] to w and set used[bestProjectIndex] to true.
1. After the outer loop finishes, return w.

Walkthrough

The algorithm iterates up to k times, representing the selection of at most k projects. In each iteration, it searches for the most profitable project among all projects that have not yet been chosen and are affordable with the current capital w. To do this, we loop through the profits and capital arrays. We maintain a variable to track the index of the best project found so far in the current iteration. A project i is a candidate if capital[i] <= w and it hasn't been selected before. Among all candidates, we pick the one with the maximum profits[i]. To avoid re-selecting a project, we can use a boolean array visited or modify the project's data (e.g., set its profit to -1) after it's chosen. If a suitable project is found, its profit is added to w, and it's marked as visited. If no affordable project can be found in an iteration, it means we cannot proceed further, so we break the loop. The final capital w is returned after the loop completes.

1class Solution {2    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {3        int n = profits.length;4        boolean[] used = new boolean[n];5 6        for (int i = 0; i < k; i++) {7            int bestProjectIndex = -1;8            int maxProfit = -1;9 10            // Find the most profitable affordable project11            for (int j = 0; j < n; j++) {12                if (!used[j] && capital[j] <= w) {13                    if (profits[j] > maxProfit) {14                        maxProfit = profits[j];15                        bestProjectIndex = j;16                    }17                }18            }19 20            // If no affordable project is found, break21            if (bestProjectIndex == -1) {22                break;23            }24 25            // "Take" the project26            w += profits[bestProjectIndex];27            used[bestProjectIndex] = true;28        }29 30        return w;31    }32}

Complexity

Time

O(k * n). The outer loop runs up to `k` times, and the inner loop runs `n` times to find the best project. In the worst case, this leads to `k * n` operations.

Space

O(n). We use a boolean array `used` of size `n` to keep track of the projects that have been completed.

Trade-offs

Pros

Simple to understand and implement.
Directly follows the problem's logic.

Cons

Inefficient for large inputs.
With k and n up to 10^5, k * n can be up to 10^10, which will result in a "Time Limit Exceeded" error.

This approach optimizes the selection process by using a greedy strategy combined with a max-heap and sorting. The core idea is that at any point, we should choose the most profitable project we can afford. To efficiently find this project, we first sort all projects by their capital requirement. Then, we use a max-heap to keep track of the profits of all projects that have become affordable.

Algorithm

1. Create an array of Project objects, each containing a capital and profit.
1. Sort the projects array based on capital in ascending order.
1. Initialize a max-heap (PriorityQueue with a reverse comparator) to store profits.
1. Initialize a pointer projectIndex = 0 for the sorted projects array.
1. Loop k times to select up to k projects.
1. Inside the loop, add all newly affordable projects to the heap: while projectIndex < n and projects[projectIndex].capital <= w, add projects[projectIndex].profit to the maxHeap and increment projectIndex.
1. If the maxHeap is empty, it means no more projects can be undertaken with the current capital. Break the loop.
1. Otherwise, pop the maximum profit from the maxHeap and add it to w.
1. After the loop, return the final capital w.

Walkthrough

The intuition is that as our capital w increases, the set of affordable projects only grows. Sorting by capital allows us to efficiently process projects as they become affordable. First, we combine the profits and capital arrays into a single list of Project objects (or pairs), where each object stores the capital and profit for one project. We sort this list of projects in ascending order based on their capital requirement. We use a Max-Heap (implemented as a PriorityQueue in Java with a reverse order comparator) to store the profits of projects we can afford but haven't started yet. We iterate k times. In each iteration:

We add all newly affordable projects to the max-heap. We use a pointer to traverse the sorted projects list. As long as the project's capital is less than or equal to our current capital w, we add its profit to the heap and advance the pointer.
If the heap is not empty, we extract the maximum profit (the root of the heap), add it to our capital w, and effectively "complete" that project.
If the heap is empty, it means there are no affordable projects, so we can't continue. We break the loop. After k iterations or breaking early, the final w is the maximized capital.

1import java.util.Arrays;2import java.util.Collections;3import java.util.PriorityQueue;4 5class Solution {6    private static class Project {7        int capital;8        int profit;9 10        Project(int capital, int profit) {11            this.capital = capital;12            this.profit = profit;13        }14    }15 16    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {17        int n = profits.length;18        Project[] projects = new Project[n];19        for (int i = 0; i < n; i++) {20            projects[i] = new Project(capital[i], profits[i]);21        }22 23        // Sort projects by their capital requirement24        Arrays.sort(projects, (a, b) -> a.capital - b.capital);25 26        // Max-heap to store profits of affordable projects27        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());28        29        int projectIndex = 0;30        for (int i = 0; i < k; i++) {31            // Add all affordable projects to the max-heap32            while (projectIndex < n && projects[projectIndex].capital <= w) {33                maxHeap.add(projects[projectIndex].profit);34                projectIndex++;35            }36 37            // If no projects can be started, break38            if (maxHeap.isEmpty()) {39                break;40            }41 42            // Greedily pick the most profitable project43            w += maxHeap.poll();44        }45 46        return w;47    }48}

Complexity

Time

O(n log n + k log n). Sorting the projects takes O(n log n). The main loop runs `k` times. Each project is pushed onto the heap at most once (total O(n log n) for all pushes) and we perform at most `k` polls from the heap (total O(k log n) for all polls).

Space

O(n). We need O(n) space for the `projects` array and the max-heap can store up to `n` profits in the worst case.

Trade-offs

Pros

Much more efficient than the brute-force approach.
Correctly implements the optimal greedy strategy.
Passes the given constraints.

Cons

More complex to implement due to the use of sorting and a priority queue.
Requires extra space for storing projects and the heap.

Solutions

Solution

1class Solution {2public3  int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {4    int n = capital.length;5    PriorityQueue<int[]> q1 = new PriorityQueue<>((a, b)->a[0] - b[0]);6    for (int i = 0; i < n; ++i) {7      q1.offer(new int[]{capital[i], profits[i]});8    }9    PriorityQueue<Integer> q2 = new PriorityQueue<>((a, b)->b - a);10    while (k-- > 0) {11      while (!q1.isEmpty() && q1.peek()[0] <= w) {12        q2.offer(q1.poll()[1]);13      }14      if (q2.isEmpty()) {15        break;16      }17      w += q2.poll();18    }19    return w;20  }21}

1using pii = pair < int , int > ; class Solution { public: int findMaximizedCapital ( int k , int w , vector < int >& profits , vector < int >& capital ) { priority_queue < pii , vector < pii > , greater < pii >> q1 ; int n = profits . size (); for ( int i = 0 ; i < n ; ++ i ) { q1 . push ({ capital [ i ], profits [ i ]}); } priority_queue < int > q2 ; while ( k -- ) { while ( ! q1 . empty () && q1 . top (). first <= w ) { q2 . push ( q1 . top (). second ); q1 . pop (); } if ( q2 . empty ()) { break ; } w += q2 . top (); q2 . pop (); } return w ; } };

1class Solution:2    def findMaximizedCapital(self, k: int, w: int, profits: List[int], capital: List[int]) -> int: h1 = [(c, p) for c, p in zip(capital, profits)] heapify(h1) h2 = [] while k: while h1 and h1[0][0] <= w: heappush(h2, - heappop(h1)[1]) if not h2: break w -= heappop(h2) k -= 1 return w

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem