Furthest Building You Can Reach — Greedy Ladder Allocation with a Min-Heap

Problem Statement#

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start your journey from building 0 and move to the next building by possibly using bricks or ladders.

While moving from building i to building i+1 (0-indexed):

• If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
• If the current building's height is less than the next building's height, you can either use one ladder or (heights[i+1] - heights[i]) bricks.

Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Constraints:

• 1 <= heights.length <= 10^5
• 1 <= heights[i] <= 10^6
• 0 <= bricks <= 10^9
• 0 <= ladders <= heights.length

Examples:

Input:  heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
 
Explanation:
  i=0→1: 4≥2, free
  i=1→2: 2<7, diff=5. Use bricks (5). bricks=0.
  i=2→3: 7≥6, free
  i=3→4: 6<9, diff=3. Use ladder. ladders=0.
  i=4→5: 9<14, diff=5. No bricks, no ladders → STOP at building 4.
  Answer: 4

Input:  heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7

Input:  heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3

Why This Problem Matters#

Furthest Building You Can Reach is a masterclass in forward-looking greedy reasoning under uncertainty. Amazon, Facebook, and Google use this problem because the naive greedy (always use a ladder for the biggest jump you can see right now) is wrong — you don't know what future jumps look like, so you need a smarter approach.

The key insight is that ladders should be assigned to the K largest climbs overall, where K is the number of ladders. Since you process buildings left to right without knowing future climbs, the min-heap approach elegantly maintains the K largest climbs seen so far and adjusts assignments retroactively.

This "retroactive assignment" greedy is powerful: optimistically assign a ladder to every climb, but maintain a min-heap of the K smallest ladder-climbs. When you exceed K ladders, swap the smallest ladder-climb to bricks (since it's the cheapest to convert). If you run out of bricks after swapping, you've found the furthest building.

The problem also teaches an important lesson: greedy algorithms don't always make the locally optimal choice at each step — sometimes you make a tentative choice and correct it later. This "take-and-possibly-revise" pattern (also seen in Course Schedule III and IPO) is more powerful than simple forward greedy.

The Core Insight#

Strategy: Ladders handle any size climb. Bricks handle exact-size climbs. You want ladders on the K largest climbs (minimizing brick usage).

Algorithm: Process each gap between buildings left to right:

1. Push the climb's diff onto a min-heap (tentatively assign a ladder).
2. If the heap size exceeds ladders, we've used too many ladders — convert the smallest ladder-assigned climb to bricks: bricks -= heap.pop().
3. If bricks < 0, we can't afford the conversion → stop at current building.

The min-heap always contains the ladders largest climbs seen so far (those that "deserve" a ladder). Any time a new climb comes in that is smaller than all current ladder-climbs, it gets pushed out and paid with bricks immediately. If it's larger than the current worst ladder-climb, the worst gets demoted to bricks.

heights=[4,2,7,6,9,14,12], bricks=5, ladders=1
 
i=0→1: diff=-2 (descent) → skip
i=1→2: diff=5 → push 5, heap=[5], size=1=ladders, ok
i=2→3: diff=-1 → skip
i=3→4: diff=3 → push 3, heap=[3,5], size=2>ladders=1
  pop min=3, bricks -= 3 → bricks=2, heap=[5]
i=4→5: diff=5 → push 5, heap=[5,5], size=2>1
  pop min=5, bricks -= 5 → bricks=-3 < 0 → STOP at i=4
 
Answer = 4

Visual Dry Run#

Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2

Answer = 7 ✓

Solution (Optimal)#

import heapq
 
def furthestBuilding(heights: list[int], bricks: int, ladders: int) -> int:
    heap = []   # min-heap of ladder-assigned climb sizes
 
    for i in range(len(heights) - 1):
        diff = heights[i + 1] - heights[i]
 
        if diff <= 0:
            continue    # descent or flat — no resource needed
 
        # Tentatively assign a ladder to this climb
        heapq.heappush(heap, diff)
 
        if len(heap) > ladders:
            # Too many ladders used — convert smallest ladder-climb to bricks
            smallest_ladder_climb = heapq.heappop(heap)
            bricks -= smallest_ladder_climb
 
        if bricks < 0:
            # Can't afford the conversion — stop here
            return i
 
    return len(heights) - 1   # reached the last building

function furthestBuilding(heights, bricks, ladders) {
    // Min-heap of ladder-assigned climbs (sorted ascending for easy min access)
    const heap = [];
 
    const heapPush = (val) => {
        let lo = 0, hi = heap.length;
        while (lo < hi) {
            const mid = (lo + hi) >> 1;
            if (heap[mid] < val) lo = mid + 1;
            else hi = mid;
        }
        heap.splice(lo, 0, val);
    };
 
    for (let i = 0; i < heights.length - 1; i++) {
        const diff = heights[i + 1] - heights[i];
        if (diff <= 0) continue;
 
        heapPush(diff);                     // tentative ladder assignment
 
        if (heap.length > ladders) {
            bricks -= heap.shift();         // convert smallest to bricks (heap[0] = min)
        }
 
        if (bricks < 0) return i;          // can't afford → stop here
    }
 
    return heights.length - 1;
}

Complexity Analysis:

The heap never exceeds ladders + 1 elements (we push then immediately pop if over). Each of the n transitions involves one push and at most one pop, both O(log k). Total: O(n log k).

Binary search alternative: Binary search on the answer (building index). For each candidate answer, check if the K largest climbs up to that index can be covered by ladders and the rest by bricks. O(n log n) time. More complex, same asymptotic.

Common Mistakes#

• Returning i + 1 instead of i when stopped. When bricks < 0 at transition i → i+1, you got stuck at building i (you couldn't reach i+1). Return i, not i+1.
• Processing descents. If heights[i+1] <= heights[i] (descent or flat), you don't need any resource. Skip these transitions — don't push to the heap.
• Using a max-heap instead of min-heap. You want to pop the smallest ladder-assigned climb to swap to bricks. This requires a min-heap.
• Checking len(heap) > ladders with >=. Push the new climb first, then check. The heap should contain at most ladders elements after cleanup. Use > ladders (strictly greater) to trigger the eviction.
• Edge case: ladders = 0. Every climb must be paid with bricks. The algorithm handles this: every push immediately triggers an eviction since len(heap) = 1 > 0.

Follow-up Questions#

• What if bricks is 0? Only ladders are available. The furthest building is the one reachable using exactly ladders climbs (greedily use each ladder for the next uphill transition).
• Can binary search solve this? Yes: binary search on the answer index. For each candidate, compute the K largest climbs using a partial sort, check if the sum of the rest fits in bricks. O(n log n) time.
• What if you want to minimize total bricks used? That is exactly what the greedy achieves — by assigning ladders to the K largest climbs, you minimize the bricks needed for the remaining climbs.
• What if ladders could be used for partial climbs (half a ladder per step)? Fractionalization changes the problem; it's no longer a 0/1 assignment. A different greedy (proportional allocation) would apply.
• What if you need to reach a specific target building? Determine the minimum bricks needed: sum of all climb diffs minus the K largest diffs (covered by ladders). If this sum ≤ available bricks, the target is reachable.

Related Problems#

• 1642. Furthest Building You Can Reach — this problem.
• 502. IPO — two-heap greedy with unlocking pattern, related "take and revise" greedy.
• 630. Course Schedule III — "take and evict worst" greedy pattern.
• 1167. Minimum Cost to Connect Sticks — different greedy, min-heap merging.
• 871. Minimum Number of Refueling Stops — greedy with a max-heap of fuel amounts at passed stations.
• 253. Meeting Rooms II — interval scheduling with resource allocation.

Key Takeaways#

• Greedily assign ladders to the K largest climbs by maintaining a min-heap of at most K ladder-assigned climbs
• When the heap exceeds K, evict the smallest ladder-climb and pay for it with bricks instead
• Return the current building index (not i+1) when bricks goes negative — you got stuck at building i
• Skip descents (diff <= 0) — no resources needed for downhill or flat transitions
• The min-heap always stores the K climbs most deserving of a ladder; the rest are paid with bricks
• Time O(n log k) where k = number of ladders; space O(k) for the heap
• This "tentative assignment + retroactive correction" greedy pattern applies to LC 630 and LC 502