# IPO
**Difficulty:** HARD
[External](https://leetcode.com/problems/ipo)
Canonical: https://scaleengineer.com/dsa/problems/ipo
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [Salesforce](https://scaleengineer.com/companies/salesforce), [Zeta](https://scaleengineer.com/companies/zeta), [PhonePe](https://scaleengineer.com/companies/phonepe), [WinZO](https://scaleengineer.com/companies/winzo), [Gameskraft](https://scaleengineer.com/companies/gameskraft), [Stackline](https://scaleengineer.com/companies/stackline)
---
## Problem
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 `ith` 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 <= 105`
* `0 <= w <= 109`
* `n == profits.length`
* `n == capital.length`
* `1 <= n <= 105`
* `0 <= profits[i] <= 104`
* `0 <= capital[i] <= 109`

# Approaches
## Brute Force Simulation
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.
**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.
**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.
### Explanation
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.
```java
class Solution {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        boolean[] used = new boolean[n];

        for (int i = 0; i < k; i++) {
            int bestProjectIndex = -1;
            int maxProfit = -1;

            // Find the most profitable affordable project
            for (int j = 0; j < n; j++) {
                if (!used[j] && capital[j] <= w) {
                    if (profits[j] > maxProfit) {
                        maxProfit = profits[j];
                        bestProjectIndex = j;
                    }
                }
            }

            // If no affordable project is found, break
            if (bestProjectIndex == -1) {
                break;
            }

            // "Take" the project
            w += profits[bestProjectIndex];
            used[bestProjectIndex] = true;
        }

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

## Greedy Approach with Max-Heap and Sorting
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.
**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.
**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.
### Explanation
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.
```java
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;

class Solution {
    private static class Project {
        int capital;
        int profit;

        Project(int capital, int profit) {
            this.capital = capital;
            this.profit = profit;
        }
    }

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        Project[] projects = new Project[n];
        for (int i = 0; i < n; i++) {
            projects[i] = new Project(capital[i], profits[i]);
        }

        // Sort projects by their capital requirement
        Arrays.sort(projects, (a, b) -> a.capital - b.capital);

        // Max-heap to store profits of affordable projects
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        
        int projectIndex = 0;
        for (int i = 0; i < k; i++) {
            // Add all affordable projects to the max-heap
            while (projectIndex < n && projects[projectIndex].capital <= w) {
                maxHeap.add(projects[projectIndex].profit);
                projectIndex++;
            }

            // If no projects can be started, break
            if (maxHeap.isEmpty()) {
                break;
            }

            // Greedily pick the most profitable project
            w += maxHeap.poll();
        }

        return w;
    }
}
```
### Algorithm
- 1. Create an array of `Project` objects, each containing a `capital` and `profit`.
- 2. Sort the `projects` array based on `capital` in ascending order.
- 3. Initialize a max-heap (`PriorityQueue` with a reverse comparator) to store profits.
- 4. Initialize a pointer `projectIndex = 0` for the sorted `projects` array.
- 5. Loop `k` times to select up to `k` projects.
- 6. 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`.
- 7. If the `maxHeap` is empty, it means no more projects can be undertaken with the current capital. Break the loop.
- 8. Otherwise, pop the maximum profit from the `maxHeap` and add it to `w`.
- 9. After the loop, return the final capital `w`.

# Solutions
### Java

```java
class Solution {
public
  int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
    int n = capital.length;
    PriorityQueue<int[]> q1 = new PriorityQueue<>((a, b)->a[0] - b[0]);
    for (int i = 0; i < n; ++i) {
      q1.offer(new int[]{capital[i], profits[i]});
    }
    PriorityQueue<Integer> q2 = new PriorityQueue<>((a, b)->b - a);
    while (k-- > 0) {
      while (!q1.isEmpty() && q1.peek()[0] <= w) {
        q2.offer(q1.poll()[1]);
      }
      if (q2.isEmpty()) {
        break;
      }
      w += q2.poll();
    }
    return w;
  }
}

```

### CPP

```cpp
using 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 ; } };
```

### Python

```python
class Solution:
    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

```