Community Problem
Furthest Building You Can Reach
Difficulty: Medium
Use bricks for short climbs and ladders for tall ones, swapping greedily to maximize reach.
Furthest Building You Can Reach
Use bricks for short climbs and ladders for tall ones, swapping greedily to maximize reach.
By @davidtoure
April 20, 2026
·
Updated May 18, 2026
470 views
2
4.3 (14)
I had this on a Bloomberg onsite and the interviewer's only hint was "do not commit a ladder until you have to". That hint hides the entire algorithm: a min-heap of the climbs you have spent ladders on, and the moment you exceed your ladder budget you cash in the SMALLEST one for bricks. The catalog covers Min-Heap basics, but it skipped this resource-allocation gem.
Furthest Building You Can Reach
You are given an integer array heights representing the heights of buildings, some bricks, and some ladders. You start at building 0 (the leftmost). At each move, you may proceed from building i to building i + 1. While moving from i to i + 1:
- If
heights[i] >= heights[i + 1], you can jump down for free. - If
heights[i] < heights[i + 1], you climb up byheights[i + 1] - heights[i]. To make this climb you may use either:- A single ladder (handles any height), or
- Bricks equal to the difference.
Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Examples
Example 1:
- Input:
heights = [4, 2, 7, 6, 9, 14, 12],bricks = 5,ladders = 1 - Output:
4 - Explanation: Drop from 4 to 2 (free), climb 2 -> 7 (use 5 bricks), drop 7 -> 6 (free), climb 6 -> 9 (use the ladder). Now we are at index 4. The next climb 9 -> 14 needs 5 bricks but we have none. Stop at index 4.
Example 2:
- Input:
heights = [4, 12, 2, 7, 3, 18, 20, 3, 19],bricks = 10,ladders = 2 - Output:
7 - Explanation: One optimal path uses ladders for
12 -> 18and18 -> 20, and bricks across the smaller climbs.
Example 3:
- Input:
heights = [14, 3, 19, 3],bricks = 17,ladders = 0 - Output:
3 - Explanation: Drop, climb 3 -> 19 with 16 bricks, drop. We end at the last building.
Example 4:
- Input:
heights = [1, 5, 1, 2, 3, 4, 10000],bricks = 7,ladders = 1 - Output:
6 - Explanation: Use 4 bricks for
1 -> 5, three more bricks for1 -> 2 -> 3 -> 4, and save the ladder for the giant4 -> 10000jump.
Constraints
1 <= heights.length <= 10^5.1 <= heights[i] <= 10^6.0 <= bricks <= 10^9.0 <= ladders <= heights.length.
Follow-up
Why is the greedy correct? Sketch: the ladders should always cover the LARGEST climbs. We discover climbs in left-to-right order, so we tentatively spend ladders on every climb (storing the climb height in a min-heap). The moment we have spent more than ladders of them, the smallest one in the heap is converted to bricks. When bricks run out, we are stuck.
Solution
Hints
Solution Walkthrough
Approach: Min-Heap of Ladder Allocations (O(n log L) time, O(L) space)
The core insight: ladders should always cover the largest climbs we will encounter, but we discover climbs left-to-right and cannot "undo" a brick payment. So we tentatively spend a ladder on EVERY climb (push the climb height into a min-heap of size up to ladders + 1). The moment we exceed our ladder budget, we cash in the SMALLEST allocated ladder by paying for that climb in bricks instead. This swap is always non-negative regret: the ladder we keep was used on a strictly larger climb than the one we paid for in bricks.
Algorithm
- Initialize an empty min-heap.
- For
ifrom0ton - 2:- Compute
climb = heights[i + 1] - heights[i]. - If
climb <= 0, the move is free; continue. - Push
climbinto the heap. - If
heap.size() > ladders, pop the smallest climb and decrementbricksby it. - If
bricks < 0, returni(we cannot complete this move).
- If the loop finishes, return
n - 1(we reached the last building).
Why It Works
At every step, the heap contains exactly the min(i + 1, ladders) LARGEST climbs encountered so far. Why? Each time the heap exceeds the budget, we eject its smallest element, which by min-heap property is the SMALLEST climb among the held ones. Inductive invariant: after processing i, the heap contains the largest-L climbs among climbs [0..i] where L = min(climbCount, ladders). Bricks have been spent only on climbs that are NOT in the heap, i.e. the smaller-tail of all climbs.
Thus we are always allocating ladders to the largest climbs we know about, given finite knowledge.
Complexity
Trace for heights = [1, 5, 1, 2, 3, 4, 10000], bricks = 7, ladders = 1
i=0: climb=4 heap=[4] size<=1, no spend
i=1: climb=-4 free
i=2: climb=1 heap=[1,4] pop 1, bricks=6
i=3: climb=1 heap=[1,4] pop 1, bricks=5
i=4: climb=1 heap=[1,4] pop 1, bricks=4
i=5: climb=9996 heap=[4,9996] pop 4, bricks=0
Loop ends, reached index 6Metric Value
Time O(n log L) where L = ladders, since the heap holds at most L + 1 elements
Space O(L) for the heapPitfalls
- Eagerly allocating bricks to the first big climb. This commits resources before you know the future, and the future may have a much bigger climb that REALLY needed the ladder. The min-heap pattern defers commitment.
- Returning wrong index on failure. When
bricks < 0, the failing climb is fromitoi + 1, so we cannot REACHi + 1. Returni, noti + 1. - Ignoring descents. A move where
heights[i + 1] <= heights[i]is free. Do not push it into the heap or you will burn a ladder slot.
Solution Code