IPO
Mahabharata — Arjuna's Investment Strategy — Choose k Projects to Maximize Capital
w पूंजी से शुरू — k बार निवेश। पहुंच योग्य सबसे लाभदायक — अगली बार चुनो॥
*Start with w capital — invest k times. Of all affordable projects — pick the most profitable next.*
The Story
Given k projects to select, starting with capital w. Project i requires at least capital[i] to start and yields profit[i]. Maximize total capital after k projects.
For `k=2`, `w=0`, `profits=[1,2,3]`, `capital=[0,1,1]`: answer=4 (pick project 0 for +1 → w=1, then pick project 2 for +3 → w=4).
**Two-Heap Strategy:** 1. Min-heap by capital: contains all projects not yet affordable (sorted by required capital) 2. Max-heap by profit: contains all currently affordable projects
**Algorithm:** - Sort projects by capital (min-heap by capital) - For k rounds: - Move all projects with capital ≤ current_w from min-heap to max-heap (now affordable) - Pick the most profitable available project (poll max-heap) - Add its profit to w
```java int n=profits.length; int[][] arr=new int[n][2]; for (int i=0;i<n;i++) arr[i]=new int[]{capital[i],profits[i]}; PriorityQueue<int[]> minCap=new PriorityQueue<>((a,b)->a[0]-b[0]); // by capital PriorityQueue<Integer> maxProfit=new PriorityQueue<>((a,b)->b-a); // by profit for (int[] a:arr) minCap.offer(a); for (int i=0;i<k;i++) { while (!minCap.isEmpty() && minCap.peek()[0]<=w) maxProfit.offer(minCap.poll()[1]); if (maxProfit.isEmpty()) break; // No affordable project w += maxProfit.poll(); } return w; ```
Trace k=2, w=0, [[0,1],[1,2],[1,3]]: - Round1: move [0,1] to maxProfit. maxProfit=[1]. Poll 1: w=1 - Round2: move [1,2],[1,3] to maxProfit. maxProfit=[3,2]. Poll 3: w=4 - return 4 ✓
The All-Subsets Approach
Try all C(n,k) project selections satisfying capital constraints. Exponential.
// Greedy is always optimal here (provable by exchange argument)
// Brute force: try all sequences of k projects; O(n^k)
public int findMaximizedCapitalBruteForce(int k, int w, int[] profits, int[] capital) {
if (k == 0) return w;
int best = w;
for (int i = 0; i < profits.length; i++)
if (capital[i] <= w)
best = Math.max(best, findMaximizedCapitalBruteForce(k-1, w+profits[i], profits, capital));
return best;
}The Two-Heap Capital-Then-Profit Strategy
public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
int n = profits.length;
PriorityQueue<int[]> minCap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
PriorityQueue<Integer> maxProfit = new PriorityQueue<>((a, b) -> b - a);
for (int i = 0; i < n; i++) minCap.offer(new int[]{capital[i], profits[i]});
for (int i = 0; i < k; i++) {
while (!minCap.isEmpty() && minCap.peek()[0] <= w)
maxProfit.offer(minCap.poll()[1]);
if (maxProfit.isEmpty()) break;
w += maxProfit.poll();
}
return w;
}Step-by-Step Walkthrough
k=1,w=0,profits=[1],capital=[1] Round1: minCap.peek()[0]=1>0 → nothing unlocked. maxProfit empty → break. Return 0 ✅ (can't afford any project)
Deep Insight
**Two-heap interplay:** The two heaps play different roles: - minCap: a sorted 'waiting room' of projects not yet affordable - maxProfit: an 'opportunity pool' of currently affordable projects
As capital grows with each selected project, more projects become affordable (transferred from minCap to maxProfit). Greedy: always pick the most profitable affordable option.
**Exchange argument proof:** If we ever skip a more profitable affordable project in favor of a less profitable one, we can swap them and never do worse. Hence greedy is optimal.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n^k) | O(1) | Exponential |
| Optimal | O(n log n) | O(n) | n projects each in/out of heaps once; k polls from maxProfit |
Pattern Recognition
✅ Min-heap by capital (affordability gate) + max-heap by profit (opportunity pool) ✅ Each round: unlock affordable, pick most profitable ✅ Two-heap coordination for constrained optimization ✅ Greedy is provably optimal **LeetCode Trigger Phrases:** → "IPO" / maximize capital with k projects → Two-heap: unlock by one criterion, pick by another → Constrained greedy optimization
Bhagavad Gita 5.23
इह चेदशकद्बोद्धुं प्राक्शरीरस्य विसर्जनात्। ततः सर्गेषु लोकेषु शरीरत्वाय कल्पते॥
If one can realize the divine here, before the body is cast off, then one is liberated in all worlds.
Connection: Arjuna's IPO strategy mirrors disciplined spiritual progression: start with what you have, invest in what's accessible, grow your capacity, and unlock greater opportunities. Each project chosen with current capital opens doors to the next. The two-heap strategy embodies this progressive unlocking — the min-heap holds future opportunities waiting for sufficient capital, while the max-heap offers the best currently accessible choice. Each wise selection expands what becomes possible.