Furthest Building You Can Reach
Understanding the Problem
We need to travel across buildings from left to right. Going downhill or staying level costs nothing. Going uphill costs either bricks (equal to the height difference) or one ladder (regardless of the height difference). The question is: how far can we get if we allocate bricks and ladders optimally?
The problem is one of resource allocation. A ladder covers any height difference for the cost of one ladder, so a ladder is worth most on the largest climbs, and bricks should cover the smaller climbs. The complication is that we walk left to right and do not know which climbs are the largest until we have seen them all. We have to decide as we go while keeping the option to reassign resources later.
This is a greedy problem where we track past decisions and swap a previous brick allocation for a ladder when a bigger climb appears.
Key Constraints:
1 <= heights.length <= 10^5→ With n up to 100,000, we need O(n log n) or better. An O(n^2) solution would be around 10^10 operations, which is too slow.0 <= bricks <= 10^9→ Bricks fit in a 32-bit signed int (max ~2.1 x 10^9), and we only ever subtract a single climb (at most 10^6) before checking the sign, sobrickscannot underflow far enough to wrap. Bricks can also be zero, meaning we may rely entirely on ladders.0 <= ladders <= heights.length→ We could have a ladder for every climb, or none at all.
Approach 1: Greedy Brute Force (Backtracking)
Intuition
At each climb, try using bricks, then try using a ladder, and take whichever choice reaches further. This is a depth-first search that branches into two paths at every uphill step.
The search explores every possible allocation and returns the maximum building index reached. It is correct but slow, since the number of paths doubles with each climb.
Algorithm
- Start at building 0 with the given bricks and ladders.
- At each building
i, compute the climb to buildingi+1:diff = heights[i+1] - heights[i]. - If
diff <= 0, move toi+1without spending anything. - If
diff > 0, try both options: - Use
diffbricks (if you have enough) and recurse fromi+1. - Use 1 ladder (if you have one) and recurse from
i+1. - Return the maximum building index reached across all branches.
Example Walkthrough
Code
- Time Complexity: O(2^n). At each uphill step, we branch into two choices (bricks or ladder). In the worst case where every step is uphill, this creates 2^n paths to explore.
- Space Complexity: O(n). The recursion stack can go n levels deep (one per building).
This is correct but exponentially slow. Since ladders should go to the largest climbs, we can make greedy decisions in a single pass and use a heap to reassign the smallest ladder-climb back to bricks whenever a bigger climb appears.
Approach 2: Min-Heap (Greedy with Ladder Reassignment)
Intuition
A ladder covers any height difference for a fixed cost of one ladder, while bricks cost is proportional to the climb height. The optimal strategy is to spend ladders on the largest climbs and bricks on the smallest ones. The difficulty is that we walk left to right and do not know which climbs are the biggest until the whole array is seen.
A min-heap of size ladders resolves this. Start as if ladders were unlimited: every time a climb appears, assign a ladder to it by pushing the climb height onto the heap. When the heap size exceeds ladders, more climbs are covered by ladders than we own, so pop the smallest climb from the heap and pay for it with bricks. This converts the cheapest ladder assignment so far into a brick payment.
After each step the heap holds the ladders largest climbs seen so far, and every other climb has been paid with bricks. That allocation minimizes brick spending at every step.
Among the climbs seen so far, total brick spending equals the sum of all climbs minus the climbs covered by ladders. With at most ladders ladders available, that sum is minimized by covering the ladders largest climbs, which is exactly the set the heap retains. Using a ladder on a climb of 100 saves 100 bricks, while using it on a climb of 2 saves only 2, so assigning ladders to the largest climbs maximizes brick savings. Returning the index as soon as bricks goes negative is also safe: brick spending only grows as we advance, so if the minimum spend up to building i+1 already exceeds the budget, no later allocation can recover.
Algorithm
- Create a min-heap to track climbs currently assigned to ladders.
- Iterate through buildings from index
0ton-2. - Compute the height difference
diff = heights[i+1] - heights[i]. - If
diff <= 0, skip (no resources needed). - If
diff > 0, pushdiffonto the min-heap (assign a ladder to this climb). - If the heap size exceeds
ladders, pop the smallest value and subtract it frombricks(convert the smallest ladder-climb to bricks). - If
bricks < 0, returni(we can't afford this step). - If we finish the loop, return
n - 1(we reached the last building).
Example Walkthrough
Code
- Time Complexity: O(n log n). We iterate through n-1 building pairs. Each heap push/pop operation takes O(log k) where k is the heap size, and k is at most ladders. Since ladders <= n, each operation is O(log n). Total: O(n log n).
- Space Complexity: O(n). The heap stores at most ladders elements, which can be up to n in the worst case.