Furthest Building You Can Reach
Problem Statement
You are given an array heights representing building heights, plus bricks and ladders. Moving from building i to i + 1 costs nothing if the next building is not taller. If the next building is taller by climb, you must spend climb bricks or one ladder. Return the index of the furthest building you can reach.
Input
An integer array heights, an integer bricks, and an integer ladders.
Output
An integer: the largest building index reachable from building 0.
Constraints
- •
1 <= heights.length <= 10^5 - •
1 <= heights[i] <= 10^6 - •
0 <= bricks <= 10^9 - •
0 <= ladders <= heights.length
Examples
Example 1
heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
4Example 2
heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
7Example 3
heights = [14,3,19,3], bricks = 17, ladders = 0
3Learning Objectives
- Recognise the premium-resource pattern where ladders should cover the largest costs in every prefix.
- Use a min-heap to remember climbs currently assigned to ladders and downgrade the smallest one to bricks when needed.
- Explain why assigning ladders to the largest climbs minimizes brick usage.
- Return the exact building before the first move that makes bricks negative.
Intuition
Pattern recognition starts with two resources: bricks scale with climb height, while a ladder pays any one climb for a flat cost. That means ladders are the premium resource, and the greedy invariant should be that ladders cover the largest positive climbs seen so far.
Use a min-heap to maintain the climbs currently assigned to ladders. Every positive climb is first treated as a ladder candidate and pushed into the heap. If the heap now contains more climbs than available ladders, one of those climbs must be paid with bricks. Paying bricks for the smallest heap climb is best because it leaves ladders on the largest climbs and minimizes brick spending in the prefix.
The trap is using ladders as soon as possible. Early climbs are not necessarily the biggest. The heap lets the algorithm revise earlier ladder assignments as larger climbs appear later.
Common mistakes
- ×Using a ladder on the first climbs without revisiting whether later climbs are larger.
- ×Adding zero or negative height differences to the heap even though they cost nothing.
- ×Using a max-heap and paying bricks for the largest climb, which is the opposite of the intended exchange.
- ×Returning the next building after bricks go negative instead of the current building index.
Algorithm Explanation
Key idea
Pretend each positive climb gets a ladder, but keep those ladder candidates in a min-heap. Whenever the number of ladder candidates exceeds ladders, convert the smallest ladder candidate to bricks by polling the min-heap. The heap then contains exactly the largest climbs in the processed prefix, so ladders are reserved for the climbs where they save the most bricks.
The exchange argument is simple: if a ladder is used on a smaller climb a while bricks pay a larger climb b, swapping the ladder to b saves b - a bricks and cannot hurt reachability. Repeating this exchange proves that an optimal prefix allocation uses ladders on the largest climbs. Therefore, if bricks become negative after the heap has downgraded the smallest possible ladder climb, no other assignment can reach the next building.
Heap walkthrough
For heights = [4,2,7,6,9,14,12], bricks = 5, and ladders = 1, ignore the drop from 4 to 2. The climb 5 from 2 to 7 enters the heap, so ladder candidates are [5] and bricks stay 5. The climb 3 from 6 to 9 makes the heap [3,5]; there is only one ladder, so poll 3 and spend 3 bricks, leaving heap [5] and bricks 2. The climb 5 from 9 to 14 makes the heap [5,5]; poll 5, bricks become -3, and the journey stops at index 4.
Algorithm
- Create a min-heap of positive climbs currently assigned to ladders.
- Walk from building 0 to building n - 2.
- Compute the climb to the next building and skip it if it is not positive.
- Push every positive climb into the heap.
- If the heap size exceeds ladders, poll the smallest climb and subtract it from bricks.
- If bricks is negative, return the current building index.
- If every move succeeds, return n - 1.
Solutions
Solution: Min-heap of ladder-assigned climbs
Use this when a fixed number of free passes should be assigned to the largest costs seen so far, while the remaining smaller costs consume a limited budget.
The heap stores climbs currently covered by ladders. Each new positive climb becomes a ladder candidate. If there are too many candidates, the smallest one is removed from the heap and paid with bricks, leaving ladders on the largest climbs in the current prefix.
Step-by-step
- Initialise an empty min-heap ladderClimbs.
- For each adjacent pair, compute the positive climb needed to move forward.
- Ignore non-positive climbs because they cost no resource.
- Push a positive climb into ladderClimbs as a ladder candidate.
- If the heap has more entries than ladders, poll the smallest climb and subtract it from bricks.
- If bricks becomes negative, return the current index because the next building is unreachable.
- Return the last index if the loop completes.
O(n log min(n, ladders + 1))
O(min(n, ladders + 1))
The heap stores at most ladders + 1 positive climbs before one is downgraded to bricks.
Java implementation
Dry Run
Sample input
heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1. The heap stores climbs currently reserved for ladders.
| move | positive climb | heap after ladder candidate | brick payment | bricks left | furthest confirmed |
|---|---|---|---|---|---|
| 0 -> 1 | 0 | [] | none | 5 | 1 |
| 1 -> 2 | 5 | [5] | none | 5 | 2 |
| 2 -> 3 | 0 | [5] | none | 5 | 3 |
| 3 -> 4 | 3 | [3,5] | pay 3 | 2 | 4 |
| 4 -> 5 | 5 | [5,5] | pay 5 | -3 | 4 |
The heap keeps the largest one climb for the ladder. When the final climb shown forces a brick payment of 5, bricks drop below zero, so building 4 is the furthest confirmed position.
Interview Tips
Say the invariant out loud: after each processed climb, the heap contains the largest climbs that receive ladders, and bricks have paid the smaller positive climbs. If challenged, use the exchange between a smaller ladder climb and a larger brick-paid climb to prove why ladders belong on the largest climbs.
Likely follow-ups
- How would you solve the same problem by spending bricks first with a max-heap refund strategy?
- How would the solution change if ladders had maximum climb heights?
- Can you return which climbs used ladders, not just the furthest index?
- What if some buildings give extra bricks when reached?
Similar Problems
Key Takeaways
- Ladders should cover the largest climbs because their cost is independent of climb height.
- A min-heap makes the smallest ladder assignment easy to downgrade to bricks.
- When bricks first go negative after the downgrade, no alternate allocation can reach the next building.
- Only positive climbs consume resources.