Problem link ও উৎস
- **Original source:** Classic heap + greedy (ladders on the biggest climbs)
- **Platform:** LeetCode —
- **Topic:** heap / priority queue
- **Difficulty:** Medium
- **Pattern:** Heap + greedy (সবচেয়ে বড় climb-গুলোয় ladder বাঁচাও)
- **Basic idea inherited from:** `08` top-K twist — সবচেয়ে বড় কয়েকটা climb-এর জন্য একটা size-bounded min-heap
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
কতগুলো building-এর height দেওয়া (`heights`), তুমি বাঁদিক থেকে ডানদিকে এগোও। পরের building যদি **নিচু বা সমান** হয়, free-তে যাও। **উঁচু** হলে height-এর পার্থক্যটুকু পার করতে হয় — হয় একটা **ladder** (এক ব্যবহারে যত উঁচুই হোক পার), নয়তো ততগুলো **brick** (পার্থক্যের সমান brick খরচ)। তোমার কাছে নির্দিষ্টসংখ্যক `bricks` আর `ladders`। সবচেয়ে দূরের কোন building index-এ পৌঁছাতে পারবে সেটা return করো।
```text
heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1 -> index 4
```
### Input ও output {#8-example-input-and-output}
```text
Input : heights=[4,2,7,6,9,14,12], bricks=5, ladders=1 -> Output: 4
Input : heights=[4,12,2,7,3,18,20,3,19], bricks=10, ladders=2 -> Output: 7
Input : heights=[14,3,19,3], bricks=17, ladders=0 -> Output: 3
Input : heights=[1,5,1,2,3,1], bricks=0, ladders=0 -> Output: 1
```
### চেনা উদাহরণে বোঝা {#6-real-life-analogy}
ভাবো তোমার কাছে কয়েকটা দামি "magic rope" (ladder) আর একগাদা সস্তা "ইট"। প্রতিটা দেয়াল ডিঙাতে হয় rope নয়তো উচ্চতার সমান ইট। তুমি rope তুলে রাখো সবচেয়ে উঁচু দেয়ালগুলোর জন্য; ছোটগুলো ইট দিয়ে। নতুন একটা বিশাল দেয়াল এলে — তোমার rope-লাগানো দেয়ালগুলোর মধ্যে যেটা সবচেয়ে ছোট, তার rope খুলে ইট দিয়ে ঢেকে দাও, rope চলে যাক বড় দেয়ালে। "rope-লাগানোদের মধ্যে সবচেয়ে ছোট কে" — তা চটজলদি দেয় min-heap।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#2-which-basic-idea-does-this-inherit-from}
ভিত `08`-এর **top-K twist**। ladder সীমিত — ঠিক `ladders`-টা। সেগুলো বুদ্ধি করে **সবচেয়ে বড় climb-গুলোয়** খরচ করা উচিত, কারণ ladder যেকোনো climb এক ধাক্কায় পার করে। তাই "এ পর্যন্ত দেখা সবচেয়ে বড় climb-গুলো" track করতে একটা **size-bounded min-heap** — top-K largest-এর সেই club-দরজা ধারণা।
### ভেতরের যুক্তি {#3-what-is-the-hidden-math-or-logic}
লুকানো logic একটা **exchange argument**: ladder সবসময় তোমার দেখা সবচেয়ে বড় climb-গুলোর জন্য তুলে রাখো; ছোট climb-গুলো brick দিয়ে চালাও। যতবার নতুন climb আসে ততবার "এ পর্যন্ত সবচেয়ে বড় `ladders`-টা climb-এ ladder, বাকিগুলোয় brick" — এই allocation locally আর globally দুটোই optimal, কারণ একটা ladder একটা বড় climb থেকে যত brick বাঁচায় ছোট climb থেকে তত বাঁচায় না।
### কী দিয়ে তথ্য রাখব {#4-which-data-structure-is-needed}
একটা **min-heap** যেটা এ পর্যন্ত "ladder দিয়ে cover করা" climb-গুলো ধরে রাখে। heap-এর size বড়জোর `ladders`। heapq min-heap তাই top = সেই climb-গুলোর মধ্যে সবচেয়ে ছোট — যেটাকে ছাড়িয়ে নতুন বড় climb এলে swap করা যায়।
### এটি কেন উপযুক্ত {#5-why-this-data-structure-fits}
তোমার দরকার বারবার একটা প্রশ্ন: "আমার ladder-cover-করা climb-গুলোর মধ্যে সবচেয়ে ছোটটা কোনটা?" — কারণ নতুন একটা বড় climb এলে সেই ছোটটাকে brick-এ নামিয়ে ladder নতুন বড়টায় দেব। min-heap top O(1)-সম এই উত্তর দেয়, swap O(log L)। পুরো climb-list re-sort করার দরকারই পড়ে না।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#9-brute-force-thinking}
প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য destination index-এর জন্য, সেই পর্যন্ত climb-গুলো বের করো, বড় `ladders`-টায় ladder আর বাকিগুলোয় brick লাগে কিনা যাচাই করো (প্রতিবার climb-গুলো sort করে)। সবচেয়ে দূর যেটা পার হয় সেটা নাও।
```text
প্রতি index পর্যন্ত -> climb গুলো sort -> বড়গুলোয় ladder, বাকিতে brick -> brick fit করে?
```
### কোথায় বেশি কাজ হচ্ছে {#10-why-brute-force-is-slow}
প্রতিটা index-এ climb-গুলো নতুন করে sort করা মানে index-প্রতি O(n log n), index n-টা — মোট **O(n² log n)**। অথচ index এগোনোর সাথে সাথে climb-set শুধু বাড়ে; প্রতিবার পুরো জিনিস sort না করে একটা heap incrementally maintain করলেই চলে।
### যে বিষয়টি খেয়াল করতে হবে {#11-key-observation}
মূল observation: **ladder সবসময় এ পর্যন্ত দেখা বড়তম climb-গুলোয় যাওয়া উচিত।** তাই প্রতিটা climb-কে "আপাতত ladder দিয়ে cover" ধরে min-heap-এ ঢালো; heap-এ `ladders`-টার বেশি জমলে, সবচেয়ে ছোট climb-টা heap থেকে বের করে brick দিয়ে cover করো। brick ফুরিয়ে গেলে — ওখানেই থামো।
### আরও কম কাজে সমাধান {#12-optimized-intuition}
বাঁদিক থেকে index ধরে এগোও। পরের building নিচু/সমান হলে free। উঁচু হলে climb = পার্থক্য; heap-এ push। heap-size > ladders হলে heap থেকে smallest climb pop করে `bricks` থেকে বিয়োগ করো; bricks < 0 হলে current index-এর আগেই আটকে — তাই last reachable index return করো। শেষ পর্যন্ত পৌঁছালে `len(heights)-1`।
### ভাবনার পরিবর্তন {#13-thinking-tweak}
**মোচড়:** "ladder নাকি brick" এই দ্বিধা না ভেবে ভাবো "সব climb-কে আপাতত ladder ধরো, তারপর সবচেয়ে ছোট ladder-allocation-গুলো brick-এ downgrade করো যতক্ষণ ঠিক `ladders`-টা ladder থাকে।" "সীমিত strong resource বড় cost-গুলোয়, সস্তা resource ছোট cost-গুলোয়" — এমন গন্ধ পেলেই size-bounded heap + greedy-র কথা মাথায় আসা উচিত।
### ছবিতে বোঝা {#7-visual-explanation}
`heights = [4,2,7,6,9,14,12]`, bricks=5, ladders=1 — climb (পার্থক্য) এলে heap-এ ঢালি, heap-size > ladders হলে smallest টা brick দিয়ে নামাই:
```text
4->2 : নিচু, free
2->7 : climb 5, heap{5}, size 1<=1 ঠিক আছে
7->6 : নিচু, free
6->9 : climb 3, heap{3,5}, size 2>1 -> pop smallest 3, brick -=3 -> bricks 5->2
9->14: climb 5, heap{5,5}, size 2>1 -> pop smallest 5, brick -=5 -> 2-5 = -3 < 0!
brick শেষ -> এখানে আটকে গেলে; পৌঁছানো শেষ index = 4
```
### ছোট input-এ ধাপে ধাপে {#14-step-by-step-dry-run}
Input `heights=[1,5,1,2,3,1]`, bricks=0, ladders=0:
1. heap empty, bricks=0, ladders=0
2. index 0→1: 1→5 climb 4 → push heap{4}; size 1 > ladders(0) → pop 4, bricks 0−4 = −4 < 0 → আটকে গেলাম
3. brick শেষ হওয়ার মুহূর্তে current index ছিল 1, তাই last reachable = `1 - 1`... না — আমরা climb টা index 0 থেকে index 1-এ যাওয়ার সময় ফেল করলাম, তাই reachable শেষ index = 1−1 = 0?
সাবধান: আমরা index `i` থেকে `i+1`-এ যেতে ফেল করলে reachable শেষ index = `i`। এখানে i=0, তাই answer 0... কিন্তু example বলে 1।
4. ঠিক করি: loop-এ আমরা index `i` (0-based) ধরে `heights[i+1]` দেখি; ফেল করলে `return i`। i=0-এ ফেল → return 0। তাহলে `[1,5,1,2,3,1]`-এ bricks=0,ladders=0 → 0 (index 0-তেই দাঁড়িয়ে, প্রথম climb-ই পার হয় না)।
(নোট: section 8-এর `[1,5,1,2,3,1]` সারিতে output 1 ধরা হয়েছিল ভুলবশত; নিচের code আর assert-এ সঠিক মান 0 ব্যবহার করা হয়েছে — code-ই চূড়ান্ত সত্য।)
## কোড ও ব্যাখ্যা {#code}
### Python {#15-python-solution}
```python
import heapq
def furthest_building(heights, bricks, ladders):
heap = [] # এ পর্যন্ত ladder দিয়ে cover করা climb-রা (min-heap)
n = len(heights)
for i in range(n - 1):
climb = heights[i + 1] - heights[i]
if climb <= 0: # নিচু বা সমান -> free
continue
heapq.heappush(heap, climb) # আপাতত ladder দিয়ে cover ধরো
if len(heap) > ladders: # ladder-এর চেয়ে বেশি climb জমলে...
bricks -= heapq.heappop(heap) # সবচেয়ে ছোট climb-টা brick-এ নামাও
if bricks < 0: # brick ফুরিয়ে গেছে -> এর আগেই আটকে
return i # index i থেকে i+1-এ যাওয়া যায়নি
return n - 1 # পুরো পথ পার
# ---- tests ----
assert furthest_building([4, 2, 7, 6, 9, 14, 12], 5, 1) == 4
assert furthest_building([4, 12, 2, 7, 3, 18, 20, 3, 19], 10, 2) == 7
assert furthest_building([14, 3, 19, 3], 17, 0) == 3 # সব climb brick-এ কুলায়
assert furthest_building([1, 5, 1, 2, 3, 1], 0, 0) == 0 # প্রথম climb-ই পার হয় না
assert furthest_building([1, 2, 3, 4, 5], 0, 4) == 4 # ৪টা climb, ৪টা ladder
assert furthest_building([5], 100, 100) == 0 # একটাই building
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#16-line-by-line-code-explanation}
- `heap = []` — এ পর্যন্ত ladder দিয়ে cover করা climb-গুলোর min-heap; size বড়জোর `ladders`।
- `for i in range(n - 1):` — প্রতিটা পরপর building-জোড়া দেখি।
- `climb = heights[i+1] - heights[i]` — পরের building কত উঁচু (negative/0 হলে free)।
- `if climb <= 0: continue` — নিচু/সমান হলে কোনো খরচ নেই।
- `heapq.heappush(heap, climb)` — নতুন climb-কে আপাতত ladder দিয়ে cover ধরে heap-এ ঢালি।
- `if len(heap) > ladders: bricks -= heapq.heappop(heap)` — ladder-এর কোটা ছাড়ালে, সবচেয়ে ছোট climb-টা brick দিয়ে cover করি।
- `if bricks < 0: return i` — brick ঋণাত্মক মানে এই climb পার করা গেল না; reachable শেষ index `i`।
- `return n - 1` — কোথাও না আটকালে শেষ building পর্যন্ত পৌঁছানো গেছে।
### Output মিলিয়ে দেখা {#17-output-walkthrough}
`furthest_building([1,5,1,2,3,1], 0, 0)` section 14-এর সংশোধিত dry run মেনে 0 দেয় — প্রথম climb (4) brick=0-তে পার হয় না। main example 4; `[14,3,19,3]` সব brick-এ কুলায় বলে শেষ index 3; `[1,2,3,4,5]`-এ ৪টা climb ৪টা ladder-এ ঢাকা পড়ে শেষ index 4। output নির্দিষ্ট index, তাই সরাসরি সমতা assert। সব pass-এর পরে print হয়: `সব test pass!`।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#18-time-complexity}
**O(n log L)** — n = building সংখ্যা, L = `ladders`। প্রতিটা climb একবার push, বড়জোর একবার pop; heap-size বড়জোর L, তাই প্রতিটা op O(log L)। তাই overall O(n log L)।
### অতিরিক্ত জায়গা {#19-space-complexity}
**O(L)** — heap-এ বড়জোর `ladders`-টা climb। ladder সংখ্যা ছোট হলে কার্যত constant memory।
### যে ভুলগুলো এড়াতে হবে {#20-common-mistakes}
- min-heap-এর বদলে max-heap ব্যবহার করা — তখন তুমি ভুল করে বড় climb-গুলো brick-এ নামিয়ে ফেলবে; উল্টো হবে।
- `bricks < 0` হওয়ার পরে current index নয়, পরের index return করা — off-by-one; ফেল করা মানে index `i`-তেই আটকে।
- নিচু/সমান climb-ও heap-এ ঢালা — শুধু `climb > 0` হলেই resource লাগে।
- heap-size guard ভুলে যাওয়া (`> ladders` চেক না করা) — তখন brick কখনো খরচই হয় না।
## শেখা ও পরের অনুশীলন {#practice}
### ভিত্তির সঙ্গে সম্পর্ক {#21-which-basic-problem-this-inherits-from}
ভিত্তি `08`-এর `patterns.md`-র Pattern 1-এর twist (size-bounded heap দিয়ে "বড় K-টা" ধরে রাখা) আর Pattern 6 (Heap + greedy combos)। ভাবনাটা Last Stone Weight-এর greedy-র cousin — locally-best choice বারবার, heap সেটা সস্তায় দেয়।
### পরের অনুশীলন {#22-similar-harder-problems}
- IPO —