[Leetcode/Heap] 1642. Furthest Building You Can Reach

🌷 Looking into Example  -> Key is to return the furthest building index

Example 1:

• heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1
  • 4 -> 2 (X)
  • 2 -> 7 (5) (Ladder)
  • 7 -> 6 (X)
  • 6 -> 9 (3) (Bricks 3)
  • 9 -> 14 (5) (Bricks 2; shortage of bricks)
  • 14 -> 12 (X)
  • Thus, you can move by [4, 2, 7, 6, 9]
  • (Index)                              0  1  2  3  4

Example 2:

• heights = [4, 12, 2, 7, 3, 18, 20, 3, 19], bricks = 10, ladders = 2
  • 4 -> 12 (8) (Ladder)
  • 12 -> 2 (X)
  • 2 -> 7 (5) (Bricks 3)
  • 7 -> 3 (X)
  • 3 -> 18 (15) (Ladder)
  • 18 -> 20 (2) (Bricks 2)
  • 20 -> 3 (X)
  • 3 -> 19 (Bricks 16;  shortage of bricks)
  • Thus, you can move by [4, 12, 2, 7, 3, 18, 20, 3]
  • (Index)                              0   1   2  3  4   5   6   7

---

Key Idea:

• Each time we encounter an upward climb, we push the height difference into a min-heap.
• If we’ve used more climbs than we have ladders, we substitute the smallest climb with bricks.
• If at any point, we don’t have enough bricks to cover even that smallest climb, we return the current building index.
• If we make it through the loop, return the last building index.

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        min_heap = []  # min-heap to keep track of the largest climbs

        for i in range(len(heights) - 1): # we're moving from building i to building i+1.
            diff = heights[i + 1] - heights[i]
            
            if diff > 0:
                heapq.heappush(min_heap, diff)

                # If we've used more ladders than we have, use bricks for the smallest climb
                if len(min_heap) > ladders:
                    bricks -= heapq.heappop(min_heap)
                    
                # If bricks go negative, we can't go further
                if bricks < 0:
                    return i
        
        return len(heights) - 1

---

Code Analysis:

for i in range(len(heights) - 1):
# heights = [4, 2, 7, 6]

 

• At each step, we're moving from building i to building i+1.
• len(heights) = 4
• You can only move from index 0 to 1, 1 to 2, and 2 to 3 → That’s a total of len(heights) - 1 moves.
• There is no building after the last one, so you don’t need to check from index 3 to 4 (doesn’t exist).

---

if len(min_heap) > ladders:
	bricks -= heapq.heappop(min_heap)

 

• It is the core of the greedy strategy.
• 🎯 Goal: Use bricks for smaller jumps, and ladders for the biggest jumps, so you can go as far as possible.
• Why do we use a ladder only for the largest climbs?
  • Because ladders are "free" — they work regardless of height. Bricks, however, cost more the higher the climb is. So if we have more climbs than ladders, we:
    1. Use ladders for the largest climbs (keep those in the heap),
    2. And use bricks for the smallest one among the climbs so far.
  • heapq.heappop(min_heap) gives us the smallest height difference we've encountered.
  • We use bricks to cover that one, because it's the most brick-efficient.

## Example:
heights = [4, 2, 7, 6, 9]
bricks = 5, ladders = 1

Climbs we encounter:

• 2 ➡️ 7 → diff = 5
• 6 ➡️ 9 → diff = 3

So min_heap = [5, 3].
We only have 1 ladder → one of these needs bricks.

We pop the smallest one (3) and do:

bricks -= 3  # bricks = bricks - 3 = 5 - 3 = 2

This way, we saved the ladder for the bigger jump (5), which is more expensive.