⚡Flashcard Drill➔
NeetCode #536LC-1642MediumHeap / Priority Queue
← Back to All Problems

#536 · #1642 · Furthest Building You Can Reach(可以到达的最远建筑)

📌 Problem Statement & Constraints

You are given heights of buildings, bricks and ladders. Moving from building i to i + 1 requires the height difference in bricks, or one ladder (usable regardless of the difference). Return the furthest building index reachable. Constraints: 1 <= heights.length <= 10^5, 0 <= bricks <= 10^9, 0 <= ladders <= heights.length.

💡 Core Algorithmic Approaches

  1. Ladders should be spent on the largest climbs, so track the climbs currently assigned to ladders in a min-heap.
  2. For each upward move, tentatively assign a ladder; if more than ladders are assigned, convert the smallest assigned climb to bricks.
  3. If the brick budget goes negative, the current index cannot be reached.
  4. Downward or flat moves cost nothing and need no decision.

💻 Benchmark Python3 Implementation

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        import heapq
        h = []                             # climbs currently covered by ladders
        for i in range(len(heights) - 1):
            d = heights[i + 1] - heights[i]
            if d <= 0:
                continue                   # downward or flat -> free
            heapq.heappush(h, d)
            if len(h) > ladders:
                # too many ladder assignments -> pay bricks for the smallest
                bricks -= heapq.heappop(h)
            if bricks < 0:
                return i                   # cannot reach i + 1
        return len(heights) - 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): each upward move costs one heap operation.
💾 Space Complexity
O(min(n, ladders)) for the heap.

⚠️ Interview Pitfalls & Follow-ups

  • Assigning ladders greedily to the first climbs: the ladders must go to the largest climbs, which the heap-based exchange handles.
  • Forgetting the d <= 0 case: downward moves cost nothing and must not consume resources.
  • Returning i + 1 on failure: the loop index i is the last reachable building.
  • Using bricks for a climb that a ladder could cover: the exchange step converts the smallest ladder climb to bricks only when needed.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Heap / Priority Queue Problems