Skip to content

019 — IPO

Source

  • Original source: Classic capital-bounded greedy with two heaps
  • Platform: LeetCode — https://leetcode.com/problems/ipo/
  • Topic: heap / priority queue
  • Difficulty: Hard
  • Pattern: Two heaps + greedy (affordable min-heap by capital → max-heap by profit)
  • Basic idea inherited from: 08 two heaps + greedy — unlock-by-threshold, তারপর সবচেয়ে লাভজনকটা নাও

1. Problem in simple words

তোমার হাতে শুরুতে w পরিমাণ capital আছে, আর কতগুলো project আছে। প্রতিটা project-এর দুটো সংখ্যা: শুরু করতে যত capital লাগবে (capital[i]), আর শেষ হলে যত profit যোগ হবে (profits[i])। তুমি বড়জোর k-টা project করতে পারবে, একটার পর একটা। কোনো project শুরু করতে হলে এই মুহূর্তে তোমার capital তার capital[i]-এর সমান বা বেশি হতে হবে; শেষ হলে profit তোমার capital-এ যোগ হয়। k-টা project শেষে সর্বোচ্চ কত capital হতে পারে, সেটা return করো।

w = 0, k = 2, profits = [1, 2, 3], capital = [0, 1, 1]  ->  4

2. Which basic idea does this inherit from?

ভিত 08-এর two heaps + greedy। একটা min-heap সব project-কে capital অনুযায়ী সাজিয়ে রাখে — যাতে "এখনকার টাকায় কোনগুলো affordable" সেটা সস্তায় বের করা যায়। আরেকটা max-heap সেই affordable project-গুলোর profit ধরে রাখে — যাতে তাদের মধ্যে সবচেয়ে লাভজনকটা চট করে নেওয়া যায়। এটা ঠিক 001-এর negate-for-max trick আর greedy "locally-best choice"-এরই বড় ভাই।

3. What is the hidden math or logic?

লুকানো logic একটা greedy exchange argument: প্রতি round-এ এই মুহূর্তে যেটা afford করতে পারো তাদের মধ্যে সবচেয়ে বেশি profit-দেওয়া project নেওয়া কখনো ভুল না। কারণ profit শুধু capital বাড়ায়, কমায় না — তাই বেশি profit আগে নিলে পরের round-এ affordable project-এর set কেবল বড় হয় (বা সমান থাকে), কখনো ছোট হয় না। তাই প্রতি step-এ সবচেয়ে লাভজনকটা নিলে শেষে capital maximize হয়।

4. Which data structure is needed?

দুটো heap। (1) by_capital — সব (এখনো না-করা) project-এর min-heap, key = required capital। (2) affordable — যেগুলোর capital বর্তমান w-এর নিচে নেমে এসেছে তাদের profit-এর max-heap (heapq min-heap বলে profit negate করে রাখা)।

5. Why this data structure fits

প্রতি round-এ তোমার দুটো প্রশ্ন: "এই capital-এ কোন project গুলো খুলে গেল?" আর "তাদের মধ্যে সবচেয়ে লাভজনক কে?"। min-heap (capital দিয়ে sorted) প্রথমটার উত্তর দেয় — top সস্তা হলেই pop করে affordable-এ সরাও। max-heap (profit) দ্বিতীয়টার উত্তর O(log n)-এ দেয়। পুরো list বারবার scan বা re-sort করার দরকারই পড়ে না।

6. Real-life analogy

ভাবো তুমি একজন investor। সামনে অনেক startup, প্রত্যেকের একটা "ঢোকার টিকিট দাম" (capital) আর একটা প্রত্যাশিত "return" (profit)। যেগুলোর টিকিট তোমার এখনকার টাকায় কেনা যায়, সেগুলো একটা টেবিলে রাখো — আর সেই টেবিল থেকে সবসময় সবচেয়ে বেশি return-এর টা আগে বেছে নাও। একটা ভালো deal শেষ হলে পকেট ভারী হয়, তখন আরও দামি টিকিটও নাগালে আসে। "সস্তা গুলো খোলো, লাভজনকটা নাও" — সেই দুই টেবিলই দুই heap।

7. Visual explanation

w = 0, k = 2, profits = [1, 2, 3], capital = [0, 1, 1]:

by_capital (min-heap, key=capital):  (0,p1) (1,p2) (1,p3)
affordable (max-heap, key=profit):   খালি

round 1: w=0 -> capital<=0 খোলো -> (0,p1) সরাও
   affordable: [profit 1]
   সবচেয়ে লাভজনক pop -> +1 -> w = 1

round 2: w=1 -> capital<=1 খোলো -> (1,p2),(1,p3) সরাও
   affordable: [profit 3, profit 2]
   সবচেয়ে লাভজনক pop -> +3 -> w = 4

k=2 শেষ  ->  উত্তর 4

8. Example input and output

Input : w=0, k=2, profits=[1,2,3], capital=[0,1,1]   -> Output: 4
Input : w=0, k=3, profits=[1,2,3], capital=[0,1,2]   -> Output: 6   (তিনটেই করা যায়)
Input : w=2, k=1, profits=[5],     capital=[5]        -> Output: 2   (afford হয় না)
Input : w=0, k=0, profits=[1,2],   capital=[0,0]      -> Output: 0   (k=0, কিছুই না)

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতি round-এ পুরো project list scan করো, এখন afford করা যায় এমন সবগুলোর মধ্যে সবচেয়ে বেশি profit-এর টা খুঁজে নাও, করো, capital update করো, project-টা mark করে বাদ দাও। k বার এটা চালাও।

round-প্রতি: পুরো list scan -> affordable-দের মধ্যে max profit -> নাও
k round x n project = O(k * n) scan

10. Why brute force is slow

প্রতি round-এ পুরো list scan মানে O(n), আর round হয় k-টা — মোট O(k·n), যেখানে n বড় হলে এটা ভারী। অথচ আমাদের প্রতিবার সবগুলো দেখার দরকার নেই: একবার capital-sorted করে রাখলে নতুন কোন project খুলেছে সেটা incremental-ভাবে জানা যায়, আর max profit heap O(log n)-এ দেয়।

11. Key observation

মূল observation: capital শুধু বাড়ে। তাই কোনো project একবার affordable হলে চিরকাল affordable থাকে — কখনো আবার "দামি" হয়ে যায় না। মানে capital-sorted list-এর ওপর একটা pointer শুধু সামনে এগোয়, পিছায় না। আর affordable হয়ে যাওয়া project-গুলোর মধ্যে শুধু সবচেয়ে লাভজনকটাই দরকার — পুরো order না।

12. Optimized intuition

সব project-কে capital দিয়ে একটা min-heap-এ ঢালো (বা শুধু sort করো)। k বার loop: বর্তমান w-এর <= capital-ওয়ালা সব project min-heap থেকে pop করে profit max-heap-এ ঢালো। max-heap খালি হলে আর কিছু afford হয় না — থামো। নাহলে সবচেয়ে বড় profit pop করে w-তে যোগ করো। প্রতিটা push/pop O(log n), মোট O(n log n)।

13. Thinking tweak

মোচড়: "project বাছাই" না ভেবে ভাবো "একটা unlock gate + একটা reward chest।" Capital-min-heap হলো gate — capital বাড়ার সাথে সাথে নতুন project খুলে দেয়; profit-max-heap হলো chest — খোলা জিনিসগুলোর মধ্যে সেরাটা দেয়। "একটা threshold পেরোলে নতুন option খোলে, খোলা option-দের মধ্যে best নাও" — এমন গন্ধ পেলেই এই two-heaps pattern মনে করবে।

14. Step-by-step dry run

Input w=0, k=2, profits=[1,2,3], capital=[0,1,1]:

  1. by_capital min-heap: (0,1), (1,2), (1,3); affordable max-heap: খালি; w = 0
  2. round 1: top capital 0 ≤ 0 → pop (0,1), affordable-এ profit 1 ঢালো; পরের top capital 1 > 0 → থামো। affordable = {1}
  3. সবচেয়ে বড় profit pop → 1 → w = 0 + 1 = 1
  4. round 2: top capital 1 ≤ 1 → pop (1,2) ঢালো; আবার top 1 ≤ 1 → pop (1,3) ঢালো; by_capital খালি। affordable = {3, 2}
  5. সবচেয়ে বড় profit pop → 3 → w = 1 + 3 = 4
  6. k = 2 শেষ → return 4

15. Python solution

import heapq

def find_maximized_capital(k, w, profits, capital):
    # সব project capital দিয়ে min-heap-এ: (required_capital, profit)
    by_capital = list(zip(capital, profits))
    heapq.heapify(by_capital)
    affordable = []                      # profit-এর max-heap (negate করা)

    for _ in range(k):
        # বর্তমান w-তে যা যা afford হয়, সব affordable-এ সরাও
        while by_capital and by_capital[0][0] <= w:
            cap, prof = heapq.heappop(by_capital)
            heapq.heappush(affordable, -prof)   # negate: max-heap
        if not affordable:               # কিছুই afford হয় না -> থামো
            break
        w += -heapq.heappop(affordable)  # সবচেয়ে লাভজনকটা নাও
    return w

# ---- tests ----
assert find_maximized_capital(2, 0, [1, 2, 3], [0, 1, 1]) == 4
assert find_maximized_capital(3, 0, [1, 2, 3], [0, 1, 2]) == 6   # তিনটেই
assert find_maximized_capital(1, 2, [5], [5]) == 2               # afford হয় না
assert find_maximized_capital(0, 0, [1, 2], [0, 0]) == 0         # k=0
assert find_maximized_capital(10, 0, [1, 2, 3], [0, 1, 1]) == 6  # k > project সংখ্যা
print("সব test pass!")

16. Line-by-line code explanation

  • by_capital = list(zip(capital, profits)) — প্রতিটা project-কে (capital, profit) জোড়ায় বাঁধি; tuple বলে heap capital দিয়ে sort করবে।
  • heapq.heapify(by_capital) — O(n)-এ min-heap; top সবসময় সবচেয়ে সস্তা (কম capital) project।
  • affordable = [] — যেগুলো খুলে গেছে তাদের profit-এর max-heap (negate করে রাখা)।
  • while by_capital and by_capital[0][0] <= w: — top-এর required capital বর্তমান w-এর নিচে থাকলেই সেটা affordable; pop করে সরাও।
  • heapq.heappush(affordable, -prof) — profit negate করে push; এতে min-heap max-heap-এর মতো আচরণ করে।
  • if not affordable: break — হাতে capital দিয়ে কোনো project-ই শুরু করা যায় না → আর এগোনো অর্থহীন, থামো।
  • w += -heapq.heappop(affordable) — সবচেয়ে বড় profit pop করে (negate ফিরিয়ে) w-তে যোগ।

17. Output walkthrough

find_maximized_capital(2, 0, [1,2,3], [0,1,1]) section 14-এর dry run মেনে 4 দেয় — assert pass। k=3, capital=[0,1,2]-এ তিনটেই ধাপে ধাপে খুলে যায় → 1+2+3 = 6। w=2, capital=[5]-এ একমাত্র project-এর টিকিট 5, afford হয় না → affordable খালি → 2-ই ফেরে। k=0-তে loop চলে না → 0। k=10 কিন্তু project 3-টা → শেষে by_capital ও affordable খালি হয়ে break → 6। সব assert pass-এর পরে print হয়: সব test pass!।

18. Time complexity

O(n log n) — প্রতিটা project বড়জোর একবার by_capital থেকে pop হয়ে affordable-এ push হয় (n-টা move, প্রতিটা O(log n)), আর বড়জোর k বার max profit pop। k ≤ n ধরলে মোট O(n log n)।

19. Space complexity

O(n) — দুই heap মিলে সব project ধরে রাখে। প্রতিটা project ঠিক একবার এক heap থেকে অন্যটায় যায়, একসাথে duplicate থাকে না, তাই memory project-সংখ্যার সমানুপাতিক।

20. Common mistakes

  • profit-কে max-heap না বানিয়ে সরাসরি heapq ব্যবহার — তখন তুমি সবচেয়ে কম profit-এর project নিচ্ছ, ভুল উত্তর।
  • প্রতি round-এ পুরো list আবার scan/sort করা — capital শুধু বাড়ে বলে pointer শুধু সামনে এগোয়; বারবার scan নিখাদ অপচয় (O(k·n))।
  • affordable খালি হলে break না দেওয়া — তখন খালি heap-এ pop করে IndexError, বা ভুলভাবে loop চালিয়ে যাওয়া।
  • capital আর profit-এর order tuple-এ উল্টে ফেলা — heap তখন profit দিয়ে sort করবে, unlock logic ভেঙে যাবে।

21. Which basic problem this inherits from

ভিত্তি 08-এর concept.md-র max-heap-via-negation আর patterns.md-র Pattern 6 (Heap + greedy combos) — "একটা greedy নিয়ম ঠিক করে কী নেবে, heap সেটা সস্তায় দেয়"। এখানে twist হলো দুটো heap: একটা unlock-এর জন্য (capital), একটা selection-এর জন্য (profit)। 001-এর single-heap greedy এর সরল রূপ।

22. Similar harder problems

23. Pattern learned

Two heaps + greedy (unlock + select): একটা min-heap একটা threshold (এখানে capital) দিয়ে option গুলো ধীরে ধীরে খুলে দেয়; খোলা option-গুলো একটা max-heap-এ যায়, যেখান থেকে greedy সবসময় best-টা তোলে। "threshold পেরোলে নতুন option খোলে, খোলাদের মধ্যে সেরা নাও" — এই pattern scheduling, IPO, resource problem-এ বারবার ফিরে আসে।

24. Final summary

ভবিষ্যতের আমাকে: IPO = দুই heap। min-heap project-গুলোকে capital দিয়ে সাজিয়ে রাখে (unlock gate), max-heap খোলা project-গুলোর profit ধরে (reward chest)। k বার: যা যা afford হয় সব gate থেকে chest-এ সরাও, তারপর chest থেকে সবচেয়ে লাভজনকটা নাও। capital শুধু বাড়ে — তাই একটা greedy "সেরাটা আগে" নিরাপদ, আর pointer পিছায় না।

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।