Furthest Building You Can Reach

Use bricks for short climbs and ladders for tall ones, swapping greedily to maximize reach.

MEDIUM

Free

heap

priority-queue

greedy

By @davidtoure

April 20, 2026

Updated May 18, 2026

470 views

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 by heights[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 -> 18 and 18 -> 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 for 1 -> 2 -> 3 -> 4, and save the ladder for the giant 4 -> 10000 jump.

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

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

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 i from 0 to n - 2:
- Compute climb = heights[i + 1] - heights[i].
- If climb <= 0, the move is free; continue.
- Push climb into the heap.
- If heap.size() > ladders, pop the smallest climb and decrement bricks by it.
- If bricks < 0, return i (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

Text

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 6

Text

Metric  Value
Time    O(n log L) where L = ladders, since the heap holds at most L + 1 elements
Space   O(L) for the heap

Pitfalls

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 from i to i + 1, so we cannot REACH i + 1. Return i, not i + 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

All Problems