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
- Ladders should be spent on the largest climbs, so track the climbs currently assigned to ladders in a min-heap.
- For each upward move, tentatively assign a ladder; if more than
laddersare assigned, convert the smallest assigned climb to bricks. - If the brick budget goes negative, the current index cannot be reached.
- 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 <= 0case: downward moves cost nothing and must not consume resources. - Returning
i + 1on failure: the loop indexiis 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.