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 crux of the problem is resource allocation. Ladders are best used for the largest climbs (since a ladder covers any height difference for free), and bricks should cover the smaller climbs. But here's the catch: we don't know which climbs are "the largest" until we've seen them all. So the real challenge is making decisions as we go, while keeping the option to retroactively reassign resources.

This is a greedy problem where we need to keep track of past decisions and potentially 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. O(n^2) would be 10^10 operations, which is too slow.
1 <= heights[i] <= 10^6 → Heights can be large, so height differences can be up to 10^6. Combined with up to 10^5 buildings, total brick usage could overflow 32-bit integers, but bricks is capped at 10^9 which fits in a 32-bit int.
0 <= bricks <= 10^9 → Bricks can be zero, meaning we might rely entirely on ladders.
0 <= ladders <= heights.length → We could have enough ladders for every single climb, or zero ladders.

Approach 1: Greedy Brute Force (Backtracking)

Intuition

The most natural first thought: at each climb, try using bricks, then try using a ladder, and take whichever choice lets you get further. This is essentially a depth-first search where at each uphill step, you branch into two paths.

This approach explores all possible allocations and returns the maximum building index reached. It's correct but extremely slow because 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 building i+1: diff = heights[i+1] - heights[i].
If diff <= 0, move to i+1 for free.
If diff > 0, try both options:

Use diff bricks (if you have enough) and recurse from i+1.
Use 1 ladder (if you have one) and recurse from i+1.

Return the maximum building index reached across all branches.

Example Walkthrough

1Start at building 0. bricks=5, ladders=1

1/6

Code

Complexity Analysis

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 approach is correct but exponentially slow. The key observation is that ladders should always go to the largest climbs. What if we made greedy decisions and used a heap to retroactively reassign the smallest ladder-climb to bricks?

Approach 2: Min-Heap (Greedy with Ladder Reassignment)

Intuition

Here's the key insight that makes this problem elegant. Ladders are most valuable for big climbs because a ladder covers any height difference at a fixed cost of one ladder. Bricks, on the other hand, are proportional to the climb height. So the optimal strategy is: use ladders for the largest climbs and bricks for the smallest ones.

But we're walking left to right. We don't know which climbs will be the biggest until we've seen them all. So how do we make optimal decisions on the fly?

The trick is to use a min-heap of size ladders. Think of it this way: assume you have unlimited ladders at first. Every time you hit a climb, throw a ladder at it (push the climb height onto the heap). When the heap size exceeds ladders, it means you've used more ladders than you actually have. Pop the smallest climb from the heap and pay for it with bricks instead. This retroactively converts your worst ladder usage into a brick payment.

This way, the heap always contains the ladders largest climbs you've seen so far, and everything else gets paid with bricks. That's the optimal allocation at every step.

Why does this work?

The min-heap maintains an invariant: it always contains the ladders largest climbs encountered so far. Every time a new climb is added, the heap might overflow. When it does, the smallest climb gets evicted and paid with bricks. This means ladders are always assigned to the biggest climbs, which is provably optimal.

Why? Because ladders have a fixed cost (one ladder per climb, regardless of height), while bricks have a variable cost proportional to the climb. Using a ladder on a climb of 100 saves 100 bricks, while using it on a climb of 2 saves only 2. So maximizing the "brick savings" from ladders means assigning them to the largest climbs.

Algorithm

Create a min-heap to track climbs currently assigned to ladders.
Iterate through buildings from index 0 to n-2.
Compute the height difference diff = heights[i+1] - heights[i].
If diff <= 0, skip (no resources needed).
If diff > 0, push diff onto the min-heap (assign a ladder to this climb).
If the heap size exceeds ladders, pop the smallest value and subtract it from bricks (convert the smallest ladder-climb to bricks).
If bricks < 0, return i (we can't afford this step).
If we finish the loop, return n - 1 (we reached the last building).

Example Walkthrough

1Start at building 0. bricks=5, ladders=1, heap=[]

1/7

Code

Complexity Analysis

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.

Furthest Building You Can Reach

Understanding the Problem

Key Constraints:

Approach 1: Greedy Brute Force (Backtracking)

Intuition

Algorithm

Example Walkthrough

Code

Approach 2: Min-Heap (Greedy with Ladder Reassignment)

Intuition

Algorithm

Example Walkthrough

Code

Get Premium