014 — Furthest Building You Can Reach¶

অধ্যায় · সমস্ত অনুশীলন ও উৎস · ধাপে ধাপে শেখা

Problem link ও উৎস

Original source: Classic heap + greedy (ladders on the biggest climbs)
Platform: LeetCode — https://leetcode.com/problems/furthest-building-you-can-reach/
Topic: heap / priority queue
Difficulty: Medium
Pattern: Heap + greedy (সবচেয়ে বড় climb-গুলোয় ladder বাঁচাও)
Basic idea inherited from: 08 top-K twist — সবচেয়ে বড় কয়েকটা climb-এর জন্য একটা size-bounded min-heap

প্রশ্ন ও উদাহরণ¶

সহজ করে প্রশ্ন¶

কতগুলো building-এর height দেওয়া (heights), তুমি বাঁদিক থেকে ডানদিকে এগোও। পরের building যদি নিচু বা সমান হয়, free-তে যাও। উঁচু হলে height-এর পার্থক্যটুকু পার করতে হয় — হয় একটা ladder (এক ব্যবহারে যত উঁচুই হোক পার), নয়তো ততগুলো brick (পার্থক্যের সমান brick খরচ)। তোমার কাছে নির্দিষ্টসংখ্যক bricks আর ladders। সবচেয়ে দূরের কোন building index-এ পৌঁছাতে পারবে সেটা return করো।

উদাহরণ

heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1  ->  index 4

Input ও output¶

উদাহরণ

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

চেনা উদাহরণে বোঝা¶

ভাবো তোমার কাছে কয়েকটা দামি "magic rope" (ladder) আর একগাদা সস্তা "ইট"। প্রতিটা দেয়াল ডিঙাতে হয় rope নয়তো উচ্চতার সমান ইট। তুমি rope তুলে রাখো সবচেয়ে উঁচু দেয়ালগুলোর জন্য; ছোটগুলো ইট দিয়ে। নতুন একটা বিশাল দেয়াল এলে — তোমার rope-লাগানো দেয়ালগুলোর মধ্যে যেটা সবচেয়ে ছোট, তার rope খুলে ইট দিয়ে ঢেকে দাও, rope চলে যাক বড় দেয়ালে। "rope-লাগানোদের মধ্যে সবচেয়ে ছোট কে" — তা চটজলদি দেয় min-heap।

ভিত্তির ধারণা¶

আগের কোন ধারণাটি লাগবে¶

ভিত 08-এর top-K twist। ladder সীমিত — ঠিক ladders-টা। সেগুলো বুদ্ধি করে সবচেয়ে বড় climb-গুলোয় খরচ করা উচিত, কারণ ladder যেকোনো climb এক ধাক্কায় পার করে। তাই "এ পর্যন্ত দেখা সবচেয়ে বড় climb-গুলো" track করতে একটা size-bounded min-heap — top-K largest-এর সেই club-দরজা ধারণা।

ভেতরের যুক্তি¶

লুকানো logic একটা exchange argument: ladder সবসময় তোমার দেখা সবচেয়ে বড় climb-গুলোর জন্য তুলে রাখো; ছোট climb-গুলো brick দিয়ে চালাও। যতবার নতুন climb আসে ততবার "এ পর্যন্ত সবচেয়ে বড় ladders-টা climb-এ ladder, বাকিগুলোয় brick" — এই allocation locally আর globally দুটোই optimal, কারণ একটা ladder একটা বড় climb থেকে যত brick বাঁচায় ছোট climb থেকে তত বাঁচায় না।

কী দিয়ে তথ্য রাখব¶

একটা min-heap যেটা এ পর্যন্ত "ladder দিয়ে cover করা" climb-গুলো ধরে রাখে। heap-এর size বড়জোর ladders। heapq min-heap তাই top = সেই climb-গুলোর মধ্যে সবচেয়ে ছোট — যেটাকে ছাড়িয়ে নতুন বড় climb এলে swap করা যায়।

এটি কেন উপযুক্ত¶

তোমার দরকার বারবার একটা প্রশ্ন: "আমার ladder-cover-করা climb-গুলোর মধ্যে সবচেয়ে ছোটটা কোনটা?" — কারণ নতুন একটা বড় climb এলে সেই ছোটটাকে brick-এ নামিয়ে ladder নতুন বড়টায় দেব। min-heap top O(1)-সম এই উত্তর দেয়, swap O(log L)। পুরো climb-list re-sort করার দরকারই পড়ে না।

ধাপে ধাপে সমাধান¶

প্রথম সরল উপায়¶

প্রথম সরল চিন্তা: প্রতিটা সম্ভাব্য destination index-এর জন্য, সেই পর্যন্ত climb-গুলো বের করো, বড় ladders-টায় ladder আর বাকিগুলোয় brick লাগে কিনা যাচাই করো (প্রতিবার climb-গুলো sort করে)। সবচেয়ে দূর যেটা পার হয় সেটা নাও।

উদাহরণ

প্রতি index পর্যন্ত -> climb গুলো sort -> বড়গুলোয় ladder, বাকিতে brick -> brick fit করে?

কোথায় বেশি কাজ হচ্ছে¶

প্রতিটা index-এ climb-গুলো নতুন করে sort করা মানে index-প্রতি O(n log n), index n-টা — মোট O(n² log n)। অথচ index এগোনোর সাথে সাথে climb-set শুধু বাড়ে; প্রতিবার পুরো জিনিস sort না করে একটা heap incrementally maintain করলেই চলে।

যে বিষয়টি খেয়াল করতে হবে¶

মূল observation: ladder সবসময় এ পর্যন্ত দেখা বড়তম climb-গুলোয় যাওয়া উচিত। তাই প্রতিটা climb-কে "আপাতত ladder দিয়ে cover" ধরে min-heap-এ ঢালো; heap-এ ladders-টার বেশি জমলে, সবচেয়ে ছোট climb-টা heap থেকে বের করে brick দিয়ে cover করো। brick ফুরিয়ে গেলে — ওখানেই থামো।

আরও কম কাজে সমাধান¶

বাঁদিক থেকে 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।

ভাবনার পরিবর্তন¶

মোচড়: "ladder নাকি brick" এই দ্বিধা না ভেবে ভাবো "সব climb-কে আপাতত ladder ধরো, তারপর সবচেয়ে ছোট ladder-allocation-গুলো brick-এ downgrade করো যতক্ষণ ঠিক ladders-টা ladder থাকে।" "সীমিত strong resource বড় cost-গুলোয়, সস্তা resource ছোট cost-গুলোয়" — এমন গন্ধ পেলেই size-bounded heap + greedy-র কথা মাথায় আসা উচিত।

ছবিতে বোঝা¶

heights = [4,2,7,6,9,14,12], bricks=5, ladders=1 — climb (পার্থক্য) এলে heap-এ ঢালি, heap-size > ladders হলে smallest টা brick দিয়ে নামাই:

উদাহরণ

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-এ ধাপে ধাপে¶

Input heights=[1,5,1,2,3,1], bricks=0, ladders=0:

heap empty, bricks=0, ladders=0
index 0→1: 1→5 climb 4 → push heap{4}; size 1 > ladders(0) → pop 4, bricks 0−4 = −4 < 0 → আটকে গেলাম
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।

ঠিক করি: 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-ই চূড়ান্ত সত্য।)

কোড ও ব্যাখ্যা¶

Python¶

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!")

কোডের প্রতিটি অংশ¶

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 মিলিয়ে দেখা¶

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!।

খরচ ও সাধারণ ভুল¶

সময়¶

O(n log L) — n = building সংখ্যা, L = ladders। প্রতিটা climb একবার push, বড়জোর একবার pop; heap-size বড়জোর L, তাই প্রতিটা op O(log L)। তাই overall O(n log L)।

অতিরিক্ত জায়গা¶

O(L) — heap-এ বড়জোর ladders-টা climb। ladder সংখ্যা ছোট হলে কার্যত constant memory।

যে ভুলগুলো এড়াতে হবে¶

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 কখনো খরচই হয় না।

শেখা ও পরের অনুশীলন¶

ভিত্তির সঙ্গে সম্পর্ক¶

ভিত্তি 08-এর patterns.md-র Pattern 1-এর twist (size-bounded heap দিয়ে "বড় K-টা" ধরে রাখা) আর Pattern 6 (Heap + greedy combos)। ভাবনাটা Last Stone Weight-এর greedy-র cousin — locally-best choice বারবার, heap সেটা সস্তায় দেয়।

পরের অনুশীলন¶

IPO — https://leetcode.com/problems/ipo/ (এই tracker-এর #19; সীমিত resource greedy + heap)
Last Stone Weight — https://leetcode.com/problems/last-stone-weight/ (#1; heap + greedy hello-world)
Minimum Number of Refueling Stops — https://leetcode.com/problems/minimum-number-of-refueling-stops/ (max-heap দিয়ে সবচেয়ে বড় fuel বাঁচিয়ে রাখা)

কৌশলটি মনে রাখুন¶

Resource allocation দিয়ে heap + greedy: সীমিত "strong" resource (ladder) সবসময় সবচেয়ে বড় cost-গুলোয়, সস্তা resource (brick) ছোট cost-গুলোয়। সব cost-কে strong-দিয়ে-cover ধরো, তারপর সবচেয়ে ছোটগুলো cheap-এ downgrade করো — min-heap সেই "সবচেয়ে ছোট cover" বারবার দেয়।

নিজেকে যাচাই করুন¶

ভবিষ্যতের আমাকে: "ladder বড় climb-এ, brick ছোট climb-এ, কত দূর যাবে" = প্রতিটা climb min-heap-এ ঢালো, size > ladders হলে smallest টা brick দিয়ে নামাও, brick শূন্যের নিচে গেলে current index return করো। IPO আর Refueling Stops-এর সাথে একই "সীমিত resource greedy + heap" পরিবারে।

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