Furthest Building You Can Reach
Medium Min-heap of climbs given ladders
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Walk past buildings left to right. Climbing up costs bricks equal to the height difference, or one ladder. Return the furthest building index you can reach.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: climb as far as possible with limited bricks and ladders.
Why this works: ladders should go on the biggest climbs. Keep the climbs on ladders in a min-heap; when there are too many, pay bricks for the smallest.
Example: heights [4, 2, 7, 6, 9, 14, 12], bricks 5, ladders 1
climb 5 (2→7): ladderclimb 3 (6→9): heap {3, 5} → bricks pay 3 → 2 leftclimb 5 (9→14): pay 5? only 2 → stop at index 4
✦Hints open one at a time
↗Approach
For each positive climb, push it into a min-heap. If the heap has more entries than ladders, poll the smallest and spend bricks on it. If bricks go negative, you can't reach this building — return i.
</>Solution (Java)
import java.util.*;
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> ladderClimbs = new PriorityQueue<>(); // min-heap
for (int i = 0; i < heights.length - 1; i++) {
int climb = heights[i + 1] - heights[i];
if (climb <= 0) continue;
ladderClimbs.offer(climb);
if (ladderClimbs.size() > ladders) {
bricks -= ladderClimbs.poll(); // smallest climb gets bricks instead
if (bricks < 0) return i;
}
}
return heights.length - 1;
}
}!Common mistake
Greedily using bricks first and ladders when bricks run out — that wastes ladders on small climbs.
- Time: O(n log L), L = ladders.
- Space: O(L).