297. IPO
🔗 LeetCode Problem: 502. IPO
📊 Difficulty: Hard
🏷️ Topics: Array, Greedy, Heap (Priority Queue), Sorting
Problem Statement
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 <= 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
🌳 Visual Understanding - The IPO Problem
The Problem We're Solving:
Projects available:
Project 0: capital needed = 0, profit = 1
Project 1: capital needed = 1, profit = 2
Project 2: capital needed = 1, profit = 3
Initial capital: w = 0
Max projects: k = 2
Question: Which projects maximize final capital?
Step-by-step:
Initial: capital = 0
Can afford? Check capital needed ≤ current capital
Project 0: 0 ≤ 0 ✓ Affordable!
Project 1: 1 ≤ 0 ✗ Can't afford
Project 2: 1 ≤ 0 ✗ Can't afford
Choose Project 0 (only option)
New capital: 0 + 1 = 1
Can afford now?
Project 1: 1 ≤ 1 ✓ Affordable!
Project 2: 1 ≤ 1 ✓ Affordable!
Choose which? GREEDY: Pick highest profit!
Project 2 has profit 3 > Project 1 profit 2
Choose Project 2!
New capital: 1 + 3 = 4 ✓
Used k=2 projects. Done!
Final capital: 4 ✓
Understanding the Constraints:
1. Initial capital: w
This is what you start with
2. Capital needed: capital[i]
Must have at least this much to start project i
3. Profit: profits[i]
This is ADDED to your capital after completing project
4. Max projects: k
Can do AT MOST k projects (might do fewer)
5. Each project can only be done ONCE
Can't repeat projects
Key Observations:
1. Capital grows over time
After each project: capital += profit
More projects become affordable!
2. Greedy choice at each step
Among affordable projects, pick HIGHEST profit
This maximizes capital for future projects
3. Sequential decision-making
Can't plan all k projects upfront
Each decision depends on current capital!
4. Two-stage process:
Stage 1: Which projects are AFFORDABLE?
Stage 2: Among affordable, which is BEST?
The Challenge:
Why is this hard?
Naive approach: Try all combinations of k projects
Time: O(n choose k) - EXPONENTIAL!
Better: Greedy!
At each step:
- Find all affordable projects (capital[i] ≤ current capital)
- Pick one with maximum profit
- Update capital
- Repeat k times
But even this is O(k × n) which can be 10^10 operations!
Need efficient way to:
1. Track which projects are affordable (dynamic, changes each step)
2. Quickly find maximum profit among affordable projects
Solution: Use two data structures! 🎯
🧠 The AHA Moment - Two Heaps Strategy
The Key Insight:
Problem: Need to efficiently:
1. Track which projects become affordable as capital grows
2. Quickly pick maximum profit from affordable projects
Solution: Use TWO data structures!
1. Min-Heap by capital: Projects sorted by capital needed
2. Max-Heap by profit: Currently affordable projects
Why this works:
- Min-heap tells us which projects become affordable next
- Max-heap gives us best (highest profit) affordable project
- Both operations in O(log n)! 🎯
Visual Discovery - The Two-Heap Strategy
Example: k = 2, w = 0
Projects: [(capital=0, profit=1), (capital=1, profit=2), (capital=1, profit=3)]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Min-Heap (by capital needed):
[(0,1), (1,2), (1,3)]
Sorted by capital needed!
Max-Heap (by profit):
[] (empty initially)
Will contain affordable projects!
Current capital: 0
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROUND 1
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: Move affordable projects to max-heap
Check min-heap top: (0,1) - need capital 0
0 ≤ 0? YES! Affordable!
Move to max-heap: [(1)]
Check min-heap top: (1,2) - need capital 1
1 ≤ 0? NO! Stop checking.
Min-Heap: [(1,2), (1,3)]
Max-Heap: [(1)]
Step 2: Pick best project from max-heap
Best: profit = 1
Do this project!
capital = 0 + 1 = 1
Completed: 1 project
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ROUND 2
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Step 1: Move affordable projects to max-heap
Current capital: 1
Check min-heap top: (1,2) - need capital 1
1 ≤ 1? YES! Affordable!
Move to max-heap: [(3), (2)] (max-heap, 3 on top)
Check min-heap top: (1,3) - need capital 1
1 ≤ 1? YES! Affordable!
Move to max-heap: [(3), (2)] (already sorted)
Min-Heap: []
Max-Heap: [(3), (2)]
Step 2: Pick best project from max-heap
Best: profit = 3 (highest!)
Do this project!
capital = 1 + 3 = 4
Completed: 2 projects (reached k!)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
RESULT
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Final capital: 4 ✓
Projects done: Project 0 (profit 1) → Project 2 (profit 3)
Why Two Heaps is Optimal
Why not just sort and iterate?
- Projects become affordable DYNAMICALLY
- As capital grows, more become available
- Can't pre-determine order!
Why min-heap for capital?
- Always check projects with SMALLEST capital first
- They become affordable earliest
- Efficient to pop in order: O(log n)
Why max-heap for profits?
- Among affordable, want HIGHEST profit
- Greedy: maximize each step
- Efficient to get max: O(log n)
Combined:
- Each round: O(log n) to pop from min-heap
- Each round: O(log n) to pop from max-heap
- k rounds: O(k log n)
- Much better than O(k × n)! 🎯
🟢 Approach: Two Heaps + Greedy (Optimal)
🎨 Building the Complete Solution
Step 1: Sort Projects by Capital
Create list of (capital, profit) pairs
Sort by capital needed (ascending)
Why?
- Process projects in order of affordability
- Use as min-heap (or sorted list)
Step 2: Initialize Max-Heap for Profits
Max-heap will contain:
- All currently affordable projects
- Sorted by profit (descending)
Initially empty (no capital yet)
Step 3: Greedy Selection Loop
Repeat k times (or until no affordable projects):
1. Move newly affordable projects to max-heap:
While top of min-heap has capital ≤ current capital:
Pop from min-heap
Push profit to max-heap
2. If max-heap empty:
No affordable projects! Break.
3. Pick best project:
Pop max profit from max-heap
Add profit to capital
Step 4: Return Final Capital
After k projects (or when stuck), return current capital
📝 Implementation - Clean with Priority Queues
import java.util.*;
class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
// Step 1: Create projects list and sort by capital needed
int[][] projects = new int[n][2];
for (int i = 0; i < n; i++) {
projects[i][0] = capital[i]; // capital needed
projects[i][1] = profits[i]; // profit
}
Arrays.sort(projects, (a, b) -> a[0] - b[0]); // Sort by capital
// Step 2: Max-heap for profits (affordable projects)
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
// Step 3: Greedy selection
int currentCapital = w;
int projectIndex = 0; // Track position in sorted projects
for (int i = 0; i < k; i++) {
// Move all newly affordable projects to max-heap
while (projectIndex < n && projects[projectIndex][0] <= currentCapital) {
maxHeap.offer(projects[projectIndex][1]); // Add profit
projectIndex++;
}
// If no affordable projects, we're done
if (maxHeap.isEmpty()) {
break;
}
// Pick project with maximum profit
currentCapital += maxHeap.poll();
}
return currentCapital;
}
}
🔍 Complete Dry Run
Input: k = 2, w = 0, profits = [1,2,3], capital = [0,1,1]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
STEP 1: Sort projects by capital
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Original:
Project 0: (capital=0, profit=1)
Project 1: (capital=1, profit=2)
Project 2: (capital=1, profit=3)
After sorting: [(0,1), (1,2), (1,3)]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
INITIALIZATION
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
currentCapital = 0
projectIndex = 0
maxHeap = []
k = 2 (can do 2 projects)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION 1 (i=0)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Move affordable projects:
Check projects[0]: (0,1)
0 ≤ 0? YES
Add profit 1 to maxHeap
maxHeap = [1]
projectIndex = 1
Check projects[1]: (1,2)
1 ≤ 0? NO
Stop checking
maxHeap empty? NO
Pick best project:
Max profit = 1
currentCapital = 0 + 1 = 1
maxHeap = []
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
ITERATION 2 (i=1)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Move affordable projects:
Check projects[1]: (1,2)
1 ≤ 1? YES
Add profit 2 to maxHeap
maxHeap = [2]
projectIndex = 2
Check projects[2]: (1,3)
1 ≤ 1? YES
Add profit 3 to maxHeap
maxHeap = [3, 2] (3 on top, max-heap)
projectIndex = 3
maxHeap empty? NO
Pick best project:
Max profit = 3
currentCapital = 1 + 3 = 4
maxHeap = [2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
DONE (completed k=2 projects)
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
Return currentCapital = 4 ✓
Projects completed:
Round 1: Project 0 (profit 1)
Round 2: Project 2 (profit 3)
Total profit: 1 + 3 = 4 ✓
Another Example
Input: k = 3, w = 0, profits = [1,2,3], capital = [0,1,2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
After sorting: [(0,1), (1,2), (2,3)]
Round 1:
Capital: 0
Affordable: (0,1)
Pick: profit 1
New capital: 1
Round 2:
Capital: 1
Affordable: (1,2)
Pick: profit 2
New capital: 3
Round 3:
Capital: 3
Affordable: (2,3)
Pick: profit 3
New capital: 6
Return: 6 ✓
📊 Complexity Analysis
Time Complexity: O(n log n + k log n)
Sorting projects: O(n log n)
k iterations:
- Each iteration: move projects to heap O(log n)
- Each iteration: pop from heap O(log n)
- Total: O(k log n)
Overall: O(n log n + k log n)
Since k ≤ n, this is O(n log n) in worst case
Space Complexity: O(n)
Projects array: O(n)
Max-heap: O(n) in worst case (all projects affordable)
Total: O(n)
💡 Why This Works - Deep Intuition
The Greedy Property
Claim: At each step, picking maximum profit is optimal
Proof Sketch:
Suppose at step i, we have capital C.
Available projects: {p1, p2, ..., pm} with profits {r1, r2, ..., rm}
Assume r1 ≥ r2 ≥ ... ≥ rm (sorted by profit)
Strategy A: Pick p1 (max profit r1)
After: capital = C + r1
Strategy B: Pick p2 (profit r2 < r1)
After: capital = C + r2 < C + r1
In future steps:
- All projects affordable with C + r2 are also affordable with C + r1
- But some projects might need C + r1 and not affordable with C + r2!
Therefore: Strategy A is at least as good as Strategy B! ✓
Greedy is optimal! 🎯
Why Two Heaps Specifically?
Alternative 1: Sort all projects by profit
Problem: Don't know which are affordable!
Would need to scan all n projects each round: O(k × n)
Alternative 2: No heaps, just arrays
Problem: Finding max profit requires O(n) scan each time
Total: O(k × n)
Two Heaps:
Min-heap: Efficiently tracks next affordable project
Max-heap: Efficiently gives best affordable project
Both operations: O(log n)
Total: O(k log n)
Much faster! 🚀
🎯 Key Insights Summary
The Three Critical Points:
1. Greedy Strategy
At each step: Pick project with MAXIMUM profit
Why optimal?
- Higher profit → more capital
- More capital → more future options
- Maximizes opportunities! 🔑
2. Two-Heap Data Structure
Min-Heap (by capital):
- Projects sorted by capital needed
- Efficiently find next affordable project
Max-Heap (by profit):
- Currently affordable projects
- Efficiently find best project
Together: O(log n) per operation! ✓
3. Dynamic Affordability
Projects become affordable over time!
- Can't pre-determine order
- Each project affects next round
- Sequential decision-making
Two heaps handle this perfectly! 🎯
⚠️ Common Mistakes
// Mistake 1: Not sorting by capital first
// ❌ Random order won't work
for (int i = 0; i < n; i++) {
if (capital[i] <= currentCapital) {
// Process project
}
}
// ✓ CORRECT: Sort first, use index to track position
Arrays.sort(projects, (a, b) -> a[0] - b[0]);
// Mistake 2: Using min-heap for profits
PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // ❌
// ✓ CORRECT: Max-heap!
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b - a);
// Mistake 3: Checking all projects every round
for (int round = 0; round < k; round++) {
for (int i = 0; i < n; i++) { // ❌ O(k × n)!
// ✓ CORRECT: Use index to track already processed
while (projectIndex < n && projects[projectIndex][0] <= currentCapital) {
// Mistake 4: Not breaking when no affordable projects
if (maxHeap.isEmpty()) {
// ❌ Continue loop anyway
}
// ✓ CORRECT: Break early
if (maxHeap.isEmpty()) break;
📝 Quick Revision Notes
🎯 Core Concept
Problem: Maximize capital by doing at most k projects
Constraints: - Can only do project if capital ≥ capital needed - Each project done once - Want maximum final capital
Key Insight: Greedy + Two Heaps!
Algorithm: 1. Sort projects by capital needed 2. Use max-heap for affordable projects 3. Each round: - Move newly affordable to max-heap - Pick maximum profit - Update capital 4. Repeat k times or until stuck
Why It Works: Greedy is optimal, heaps make it efficient!
⚡ Quick Implementation
import java.util.Arrays;
import java.util.Collections;
import java.util.PriorityQueue;
public class Solution {
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
return greedy(k, w, profits, capital);
}
private int greedy(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
int[][] projects = new int[n][2];
// step 1: consolidate projects and capital to single place.
// why? not to lose track when we sort based on capital.
for (int i = 0; i < n; i++) {
projects[i][0] = capital[i];
projects[i][1] = profits[i];
}
// step 2: sort based capital so that we will take
// projects which are in our budget (currentCapital)
Arrays.sort(projects, (p1, p2) -> p1[0] - p2[0]);
// step 3: stores projects (or capital gains) received
// post project completion
// why max heap?
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
// step 4: lets take projects 1 by 1 and
// see what capital we can gain
int currCapital = w;
int currProject = 0;
for (int i = 0; i < k; i++) {
// step 5: take all affordable projects at ONCE
// and push the PROFIT from that taken project as capital gain.
// GOTCHA: you do need to SUBTRACT it.
while (currProject < n && projects[currProject][0] <= currCapital) {
maxHeap.offer(projects[currProject][1]);
currProject++;
}
// step 6: we do not have capital any more.
// Try to check our maxHeap (like a bank) to add it into currCapital.
if (maxHeap.isEmpty()) {
// not possible any more. Just break and return existing capital gained.
break;
}
// do take 1 profit at a time.
// if current profit also, do not enough, we will still come
// here and add other profit as capital gained.
// By this, understand that its not top k projects that give max profit.
// we can take capital gained (or profits) from those k projects
currCapital = currCapital + maxHeap.poll();
}
return currCapital;
}
public static void main(String[] args) {
Solution s = new Solution();
System.out.println(s.findMaximizedCapital(2, 0, new int[] { 1, 2, 3 }, new int[] { 0, 1, 1 }) == 4);
System.out.println(s.findMaximizedCapital(3, 0, new int[] { 1, 2, 3 }, new int[] { 0, 1, 2 }) == 6);
}
}
🔑 Key Points
✓ Sort projects by capital (ascending)
✓ Max-heap for profits (greedy choice)
✓ Track position in sorted list (avoid reprocessing)
✓ Break if no affordable projects
✓ Time: O(n log n + k log n)
✓ Space: O(n)
✓ Greedy is optimal (proven!)
🎪 Memory Aid
"Two heaps, capital leaps!"
"Min for capital, max for gain!"
"Greedy picks profit, never plain!"
"IPO success, no refrain!" ✨
🎉 Congratulations!
You've mastered IPO - another Hard problem!
What You Learned:
✅ Two-heap strategy - Min and max together
✅ Greedy optimization - Maximum profit each step
✅ Dynamic affordability - Projects become available
✅ Sequential decision-making - Each choice affects next
✅ Proof of optimality - Why greedy works
The Beautiful Insight:
Complex Project Selection → Two-Heap Greedy Solution
The core insight:
"Projects become affordable DYNAMICALLY"
"Need efficient way to track and select"
Solution:
Min-Heap: Next affordable projects (by capital)
Max-Heap: Best available projects (by profit)
Greedy: Always pick maximum profit!
This strategy:
- Handles dynamic affordability elegantly
- Maximizes capital at each step
- Proven to be optimal
- Efficient O(n log n) time! 🎯
This pattern appears in:
- Resource allocation problems
- Scheduling with dependencies
- Any greedy + priority queue problem
Master this pattern = Solve many Hard problems! ✨
Interview Mastery:
When asked about IPO:
1. Understand: "Maximize capital with k projects"
2. Identify challenge: "Projects have capital requirements.
As we earn, more become affordable!"
3. Key insight: "Use two heaps!
Min-heap: Track by capital (what's affordable next)
Max-heap: Track by profit (what's best now)"
4. Why greedy: "Always pick max profit available.
More capital → more future options.
Proven optimal!"
5. Code it: Clean O(n log n) solution
6. Complexity: "O(n log n) for sorting,
O(k log n) for k iterations with heap ops."
7. Space: "O(n) for heaps and projects array."
Shows complete understanding! 💯
You've mastered a Hard problem combining greedy strategy with efficient data structures! 🚀✨🎯