502. IPO

HardGreedyArraySortingHeap (Priority Queue)
Leetcode Link

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:

  1. Pair each project's capital and profit and push them into h1.
  2. Heapify h1 to structure it according to the minimum capital required.
  3. For up to k projects, do the following:
    • Move projects from h1 to h2 if they can be afforded with the current capital w.
    • If h2 has projects, pop the project with the maximum profit, add that profit to w.
    • 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.

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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece๏ผš

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

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:

  1. Zip the profits and capital lists together so that each tuple (c, p) in the new list h1 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.

  2. Transform the list h1 into a min-heap in-place using Python's heapify 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.

  3. 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.

  4. Begin a loop that will run at most k times, where k is the maximum number of projects that can be completed.

  5. Within the loop, move projects from the min-heap h1 to the max-heap h2 as long as the project's capital requirement is smaller than or equal to the current capital w. We use the heappop function to extract the project with the smallest capital requirement from h1 and the heappush function to push its profit (as a negative number to facilitate max-heap behavior in Python's min-heap) into h2.

  6. If h2 is not empty, it means we have at least one project that can be started given the current capital. Use heappop again, this time on h2, to extract the project with the largest profit (remembering to negate the value to transform it back from the negative value we used earlier).

  7. Update the current capital w by adding the profit of the chosen project to it.

  8. 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.

  9. After at most k iterations or when no further projects can be done, exit the loop and return the value of w, 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Breadth first search can be used to find the shortest path between two nodes in a directed graph.

Example 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:

  1. Pair each project's capital and profit: h1 = [(0, 1), (1, 2), (1, 3)].
  2. 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)].
  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 from h1 to h2 as long as the project's capital requirement is smaller than or equal to w. Since the first project requires 0 capital, which is equal to our current capital, we add it to h2 as (-1, 0) (we use negative profit for max-heap behavior). Now h1 = [(1, 2), (1, 3)] and h2 = [(-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 now w = 1.

  • We have completed one project. Decrease k by 1, now k = 1.

  • For the second iteration, w = 1. We transfer all projects which fit into our current capital w from h1 to h2. Now we can afford the remaining projects as they both require a capital of 1. Add them to h2: (-2, 1), (-3, 1) (again using negative profits). h1 is now empty and h2 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 is w = 4.

  • We have completed the second project. Decrease k by 1, now k = 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
Not Sure What to Study? Take the 2-min Quiz๏ผš

Which of the following array represent a max heap?

Time and Space Complexity

Time Complexity

The time complexity of the code can be analyzed as follows:

  1. Preparing the heap h1 involves pairing each element from capital with profits. This takes O(N) time where N is the number of projects.
  2. The heapify function on h1 runs in O(N) time.
  3. In the worst case, the loop runs k times. In each iteration, the inner while loop can push up to N elements to h2 (over all iterations), this gives us O(N*log(N)) for all heappush operations since each heappush operation takes O(log(N)).
  4. Each heappop operation on h1 takes O(log(N)) time, resulting in O(N*log(N)) for all heappop operations from h1.
  5. Each heappop from h2 takes O(log(K)). Since there are at most k such operations, the total time taken by all heappop operations from h2 is O(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:

  1. Two extra heaps h1 and h2 are used, of which h1 can contain up to N elements and h2 can contain up to k elements.
  2. 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.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Sorting Summary

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

Heap Fundamentals

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 Teaching Assistantย anything you don't understand.

Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.

โ†
โ†‘TA ๐Ÿ‘จโ€๐Ÿซ