Skip to content

014 — Furthest Building You Can Reach

Source

  • 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

1. Problem in simple words

কতগুলো 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

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 করার দরকারই পড়ে না।

6. Real-life analogy

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

7. Visual explanation

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

8. Example input and 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

9. Brute force thinking

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

প্রতি 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-র কথা মাথায় আসা উচিত।

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।

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

15. Python solution

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 পর্যন্ত পৌঁছানো গেছে।

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

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

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

23. Pattern learned

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

24. Final summary

ভবিষ্যতের আমাকে: "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।