502. IPO
Problem Description
LeetCode is preparing for its Initial Public Offering (IPO) and wants to take on some projects to boost its overall capital before going public. However, there are constraints on how many projects it can undertake due to limited resources. Specifically, LeetCode can only complete at most k
distinct projects. The task at hand is to choose a subset of these projects to maximize the total capital, given that each project has its own potential profit and a minimum required capital to start. Initially, the available capital is w
. Once a project is completed, its profit increases the total capital. The goal is to find out the maximum capital that can be reached after completing at most k
projects.
The input includes several pieces of information: the integer k
representing the maximum number of projects LeetCode can complete, the initial capital w
, a list of integers profits
which denotes the profit from each project, and a list capital
showing the minimum capital required to start each project. The problem guarantees that the final answer will be small enough to fit into a 32-bit signed integer.
Intuition
The solution to this problem involves sorting projects by their capital requirements and using a greedy approach to pick projects that can be started with the current available capital and yield the highest profit.
Firstly, we need to categorize projects based on whether they are within our current capital capabilities. We use two heaps (priority queues) to do this: h1
for projects we cannot afford yet, and h2
for profitable projects we can do right away. h1
is min-heaped on capital required, so projects requiring less capital are at the top. Heap h2
is max-heaped on profits (we use negative values to achieve this in Python's min-heap), so the most profitable projects we can afford are at the top.
The algorithm proceeds as follows:
- Pair each project's capital and profit and push them into
h1
. - Heapify
h1
to structure it according to the minimum capital required. - For up to
k
projects, do the following:- Move projects from
h1
toh2
if they can be afforded with the current capitalw
. - If
h2
has projects, pop the project with the maximum profit, add that profit tow
. - If
h2
is empty, it means there are no more projects that can be done with the current capital, and we break the loop. - Decrease
k
by 1 because a project has been completed.
- Move projects from
By following this approach, we ensure that with each iteration, we are choosing the most profitable project that can be started with the available capital. Once k
reaches zero or there are no projects left that can be afforded, the algorithm ends. The value of w
at this point is the maximized capital we aimed to find.
Learn more about Greedy, Sorting and Heap (Priority Queue) patterns.
Solution Approach
The given Python solution makes use of a min-heap and a max-heap to efficiently determine which project to pick next. The overall approach can be broken down into several algorithmic steps using two primary data structures — heaps (implemented via Python's priority queue).
Here's the step-by-step implementation:
-
Zip the
profits
andcapital
lists together so that each tuple(c, p)
in the new listh1
consists of the capital required and the profit of a project. This allows us to keep each project's financials together for easy access later on. -
Transform the list
h1
into a min-heap in-place using Python'sheapify
function. This operation reorders the elements so that the project with the smallest capital requirement is at the root of the heap, which allows us to quickly find and extract the project with the lowest capital threshold. -
Initialize an empty list
h2
to use as a max-heap for profits, which we'll need later to keep track of the most profitable projects that we can afford within our current capital. -
Begin a loop that will run at most
k
times, wherek
is the maximum number of projects that can be completed. -
Within the loop, move projects from the min-heap
h1
to the max-heaph2
as long as the project's capital requirement is smaller than or equal to the current capitalw
. We use theheappop
function to extract the project with the smallest capital requirement fromh1
and theheappush
function to push its profit (as a negative number to facilitate max-heap behavior in Python's min-heap) intoh2
. -
If
h2
is not empty, it means we have at least one project that can be started given the current capital. Useheappop
again, this time onh2
, to extract the project with the largest profit (remembering to negate the value to transform it back from the negative value we used earlier). -
Update the current capital
w
by adding the profit of the chosen project to it. -
If
h2
is empty and we can no longer afford any projects with the current capital, exit the loop as we can't do any more projects. -
After at most
k
iterations or when no further projects can be done, exit the loop and return the value ofw
, which now represents the maximized capital.
The use of heaps allows the solution to be efficient even when dealing with a large number of projects, as projects that can't be afforded yet are quickly filtered out, and finding the most profitable of the remaining projects can be done in constant time (O(1)
) due to the heap's properties. The heap insertions and deletions (heappush
and heappop
) operate in logarithmic time (O(log n)
), ensuring that each project insertion or extraction does not slow down the algorithm significantly even for large numbers of projects.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach.
Consider the following scenario where LeetCode can complete at most k = 2
projects, the initial capital is w = 0
, the list of profits is profits = [1, 2, 3]
, and the list of minimum required capital for each project is capital = [0, 1, 1]
.
We will apply the described algorithm step by step:
- Pair each project's capital and profit:
h1 = [(0, 1), (1, 2), (1, 3)]
. - Heapify
h1
to structure it according to the minimum capital required. After heapifying,h1
still looks the same since the elements were already in the correct order:h1 = [(0, 1), (1, 2), (1, 3)]
. - Initialize an empty list
h2
to use as a max-heap for available profitable projects.
Now we begin our main loop which runs at most k
times:
-
For the first iteration,
w = 0
. We move projects fromh1
toh2
as long as the project's capital requirement is smaller than or equal tow
. Since the first project requires 0 capital, which is equal to our current capital, we add it toh2
as(-1, 0)
(we use negative profit for max-heap behavior). Nowh1 = [(1, 2), (1, 3)]
andh2 = [(-1, 0)]
. -
Pop the most profitable project from
h2
, which gives us(-1, 0)
. This means we earn a profit of 1 (negating the popped value). Our capital is noww = 1
. -
We have completed one project. Decrease
k
by 1, nowk = 1
. -
For the second iteration,
w = 1
. We transfer all projects which fit into our current capitalw
fromh1
toh2
. Now we can afford the remaining projects as they both require a capital of 1. Add them toh2
:(-2, 1), (-3, 1)
(again using negative profits).h1
is now empty andh2
is[-3, -2]
after re-heapifying for max-profit. -
Pop the most profitable project from
h2
, which is(-3, 1)
. We earn a profit of 3, so now our capital isw = 4
. -
We have completed the second project. Decrease
k
by 1, nowk = 0
. -
The loop ends as
k
is now 0.
With no more projects that can be completed due to the limit k
, we have finished our iterations. The maximized capital is now w = 4
, which is the value we return.
By processing the projects in this manner, LeetCode chose the most profitable projects available within their capital limits, thus maximizing their capital by the end of the process.
Solution Implementation
1from heapq import heappop, heappush, heapify
2
3class Solution:
4 def findMaximizedCapital(self, k: int, startingCapital: int, profits: List[int], capital: List[int]) -> int:
5 # Create a list of tuples, where each tuple consists of (project capital, project profit)
6 # and then transform this list into a min heap based on required capital to start projects.
7 min_heap_by_capital = [(c, p) for c, p in zip(capital, profits)]
8 heapify(min_heap_by_capital)
9
10 # Create a max heap for available projects to track the profits that we can achieve.
11 max_heap_by_profit = []
12
13 # Loop until we have completed k projects or there are no profitable projects available.
14 while k:
15 # Move projects we can afford from the min heap to the max heap.
16 while min_heap_by_capital and min_heap_by_capital[0][0] <= startingCapital:
17 # We push the negative profit to simulate the max heap using the min heap property.
18 heappush(max_heap_by_profit, -heappop(min_heap_by_capital)[1])
19
20 # If there are no projects available in the max heap, we break out of the loop.
21 if not max_heap_by_profit:
22 break
23
24 # Pop the project with the highest profit from the max heap and add it to our current capital.
25 startingCapital -= heappop(max_heap_by_profit)
26
27 # Increment the counter for how many projects we have completed.
28 k -= 1
29
30 # Return the maximized capital after completing up to k projects.
31 return startingCapital
32
1class Solution {
2 public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
3 int n = capital.length; // Number of projects
4
5 // Create a min-heap (priority queue) to keep track of projects based on required capital
6 PriorityQueue<int[]> minCapitalHeap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
7
8 // Populate the min-heap with project information - each item is an array where
9 // the first element is the capital required and the second element is the profit.
10 for (int i = 0; i < n; ++i) {
11 minCapitalHeap.offer(new int[] {capital[i], profits[i]});
12 }
13
14 // Create a max-heap (priority queue) to keep track of profitable projects that we can afford
15 PriorityQueue<Integer> maxProfitHeap = new PriorityQueue<>((a, b) -> b - a);
16
17 // Iterate k times, which represents the maximum number of projects we can select
18 while (k-- > 0) {
19 // Move all the projects that we can afford (w >= required capital) to the max profit heap
20 while (!minCapitalHeap.isEmpty() && minCapitalHeap.peek()[0] <= w) {
21 maxProfitHeap.offer(minCapitalHeap.poll()[1]);
22 }
23 // If the max profit heap is empty, it means there are no projects we can afford, so we break
24 if (maxProfitHeap.isEmpty()) {
25 break;
26 }
27 // Otherwise, take the most profitable project from the max profit heap and add its profit to our total capital
28 w += maxProfitHeap.poll();
29 }
30 return w; // Return the maximized capital after picking up to k projects
31 }
32}
33
1#include <queue>
2#include <vector>
3
4using std::pair;
5using std::priority_queue;
6using std::vector;
7
8// A pair of integers alias to represent a pair of capital and profit.
9using ProfitCapitalPair = pair<int, int>;
10
11class Solution {
12public:
13 // This function maximizes the capital by doing at most 'k' projects starting
14 // with initial capital 'w'. Projects have associated profits and capital requirements.
15 int findMaximizedCapital(int k, int w, vector<int>& profits, vector<int>& capital) {
16 // A min-heap that stores pairs of capital requirements and profits
17 // Such that the project with the least capital requirement is on top.
18 priority_queue<ProfitCapitalPair, vector<ProfitCapitalPair>, std::greater<ProfitCapitalPair>> minCapitalHeap;
19
20 // Populate the min-heap with the capital and profits of the projects.
21 int numProjects = profits.size();
22 for (int i = 0; i < numProjects; ++i) {
23 minCapitalHeap.push({capital[i], profits[i]});
24 }
25
26 // A max-heap to store profits of projects we can afford to invest in,
27 // so we can always choose the most profitable one next.
28 priority_queue<int> maxProfitHeap;
29
30 // Loop to perform up to 'k' investments.
31 while (k--) {
32 // Move all projects we can afford (with current capital 'w') to a max-heap.
33 // This heap will help us to quickly select the next most profitable project.
34 while (!minCapitalHeap.empty() && minCapitalHeap.top().first <= w) {
35 maxProfitHeap.push(minCapitalHeap.top().second);
36 minCapitalHeap.pop();
37 }
38
39 // If we cannot afford any project, break out of the loop.
40 if (maxProfitHeap.empty()) {
41 break;
42 }
43
44 // Pick the most profitable project and increase our capital.
45 w += maxProfitHeap.top();
46 maxProfitHeap.pop();
47 }
48
49 // After completing 'k' or the maximum number of profitable investments,
50 // 'w' is our maximized capital.
51 return w;
52 }
53};
54
1type ProfitCapitalPair = { capital: number, profit: number };
2
3// A function that maximizes the capital by doing at most 'k' projects
4// starting with initial capital 'W'. Projects have associated profits
5// and capital requirements.
6function findMaximizedCapital(k: number, W: number, Profits: number[], Capital: number[]): number {
7 // Initialize a min-heap based on capital requirements so the project
8 // with the least capital requirement is at the beginning.
9 let minCapitalHeap: ProfitCapitalPair[] = [];
10
11 // Populate the min-heap with capital and profits of the projects.
12 for (let i = 0; i < Profits.length; ++i) {
13 minCapitalHeap.push({ capital: Capital[i], profit: Profits[i] });
14 }
15 // Sort the heap to ensure the smallest capital requirement is at the start.
16 minCapitalHeap.sort((a, b) => a.capital - b.capital);
17
18 // Initialize an array to use as a max-heap to store profits
19 // of the projects we can afford, enabling us to choose the most profitable one.
20 let maxProfitHeap: number[] = [];
21
22 // Define a helper function to turn the array into a max-heap,
23 // using simple push-pop since TypeScript/JavaScript does not have a native priority queue structure.
24 const pushMaxHeap = (value: number) => {
25 maxProfitHeap.push(value);
26 maxProfitHeap.sort((a, b) => b - a); // Sort in descending order to keep max element at the start
27 };
28
29 const popMaxHeap = (): number => {
30 return maxProfitHeap.shift() || 0; // Remove and return the first element (max element)
31 };
32
33 // Loop to perform up to 'k' investments.
34 for (let i = 0; i < k; i++) {
35 // Move all projects we can afford (with current capital 'W') to the max-heap.
36 while (minCapitalHeap.length && minCapitalHeap[0].capital <= W) {
37 const project = minCapitalHeap.shift()!;
38 pushMaxHeap(project.profit);
39 }
40
41 // If we cannot afford any project, exit the loop.
42 if (!maxProfitHeap.length) {
43 break;
44 }
45
46 // Pick the most profitable project we can afford and increase our capital.
47 W += popMaxHeap();
48 }
49
50 // After completing 'k' or the maximum number of profitable investments,
51 // 'W' is our maximized capital.
52 return W;
53}
54
Time and Space Complexity
Time Complexity
The time complexity of the code can be analyzed as follows:
- Preparing the heap
h1
involves pairing each element fromcapital
withprofits
. This takesO(N)
time whereN
is the number of projects. - The
heapify
function onh1
runs inO(N)
time. - In the worst case, the loop runs
k
times. In each iteration, the inner while loop can push up toN
elements toh2
(over all iterations), this gives usO(N*log(N))
for allheappush
operations since eachheappush
operation takesO(log(N))
. - Each
heappop
operation onh1
takesO(log(N))
time, resulting inO(N*log(N))
for allheappop
operations fromh1
. - Each
heappop
fromh2
takesO(log(K))
. Since there are at mostk
such operations, the total time taken by allheappop
operations fromh2
isO(k*log(K))
.
Summing up all the operations, the resulting time complexity would be the sum of the heap operations across both heaps, which in big-O notation simplifies to the largest term. This would be O(N*log(N) + k*log(K))
.
Space Complexity
The space complexity can be analyzed as follows:
- Two extra heaps
h1
andh2
are used, of whichh1
can contain up toN
elements andh2
can contain up tok
elements. - There are no other significant uses of space beyond the input storage.
This gives us a space complexity of O(N + k)
. Since heaps use space proportionate to the number of elements they contain.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.