Table of Contents

# IPO – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.

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`

project has a pure profit ^{th}`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:4Explanation: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`

^{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}

# C++ IPO LeetCode Solution

```
``````
int findMaximizedCapital(int k, int W, vector<int>& P, vector<int>& C) {
priority_queue<int> low; // P[i]'s within current W
multiset<pair<int,int>> high; // (C[i],P[i])'s' outside current W
for (int i = 0; i < P.size(); ++i) // initialize low and high
if(P[i] > 0) if (C[i] <= W) low.push(P[i]); else high.emplace(C[i], P[i]);
while (k-- && low.size()) {
W += low.top(), low.pop(); // greedy to work on most profitable first
for (auto i = high.begin(); high.size() && i->first <= W; i = high.erase(i)) low.push(i->second);
}
return W;
}
```

# Java IPO LeetCode Solution

```
``````
public class Solution {
public int findMaximizedCapital(int k, int W, int[] Profits, int[] Capital) {
PriorityQueue<int[]> pqCap = new PriorityQueue<>((a, b) -> (a[0] - b[0]));
PriorityQueue<int[]> pqPro = new PriorityQueue<>((a, b) -> (b[1] - a[1]));
for (int i = 0; i < Profits.length; i++) {
pqCap.add(new int[] {Capital[i], Profits[i]});
}
for (int i = 0; i < k; i++) {
while (!pqCap.isEmpty() && pqCap.peek()[0] <= W) {
pqPro.add(pqCap.poll());
}
if (pqPro.isEmpty()) break;
W += pqPro.poll()[1];
}
return W;
}
}
```

# Python 3 IPO LeetCode Solution

```
``````
def findMaximizedCapital(self, k, W, Profits, Capital):
heap = []
projects = sorted(zip(Profits, Capital), key=lambda l: l[1])
i = 0
for _ in range(k):
while i < len(projects) and projects[i][1] <= W:
heapq.heappush(heap, -projects[i][0])
i += 1
if heap: W -= heapq.heappop(heap)
return W
```

Array-1180

String-562

Hash Table-412

Dynamic Programming-390

Math-368

Sorting-264

Greedy-257

Depth-First Search-256

Database-215

Breadth-First Search-200

Tree-195

Binary Search-191

Matrix-176

Binary Tree-160

Two Pointers-151

Bit Manipulation-140

Stack-133

Heap (Priority Queue)-117

Design-116

Graph-108

Simulation-103

Prefix Sum-96

Backtracking-92

Counting-86

Sliding Window-73

Linked List-69

Union Find-66

Ordered Set-48

Monotonic Stack-47

Recursion-43

Trie-41

Binary Search Tree-40

Divide and Conquer-40

Enumeration-39

Bitmask-37

Queue-33

Memoization-32

Topological Sort-31

Geometry-30

Segment Tree-27

Game Theory-24

Hash Function-24

Binary Indexed Tree-21

Interactive-18

Data Stream-17

String Matching-17

Rolling Hash-17

Shortest Path-16

Number Theory-16

Combinatorics-15

Randomized-12

Monotonic Queue-9

Iterator-9

Merge Sort-9

Concurrency-9

Doubly-Linked List-8

Brainteaser-8

Probability and Statistics-7

Quickselect-7

Bucket Sort-6

Suffix Array-6

Minimum Spanning Tree-5

Counting Sort-5

Shell-4

Line Sweep-4

Reservoir Sampling-4

Eulerian Circuit-3

Radix Sort-3

Strongly Connected Componen-t2

Rejection Sampling-2

Biconnected Component-1