Furthest Building You Can Reach

How it works

Instead of tracking brick usages, we can track ladder usages in a min-heap. We greedily assign ladders to each jump, but once we've used more than the allowed number of ladders, we convert the smallest ladder usage back to bricks. This way, ladders always end up covering the largest jumps.

Steps

1. Traverse buildings from left to right.
2. For each positive height difference, push it onto a min-heap (representing a ladder allocation).
3. If the heap size exceeds the number of ladders:
   • Pop the smallest difference (least valuable ladder usage).
   • Subtract it from bricks.
   • If bricks go negative, return the current index.
4. If we complete the traversal, return n - 1.

Complexity

• Time complexity: O(n log n)
• Space complexity: O(n)

Things to watch for

Ignoring Downward or Equal Height Transitions

Not all building transitions require resources. When heights[i+1] <= heights[i], no bricks or ladders are needed. Forgetting to skip these cases leads to wasting resources on non-existent climbs and incorrect answers. Always check if the height difference is positive before consuming any resources.

Using Ladders for Small Gaps Instead of Large Ones

The greedy insight is that ladders should cover the largest height differences since they handle any gap regardless of size. Using ladders greedily for the first gaps encountered (rather than the largest ones) leads to suboptimal resource usage. The heap-based solutions ensure ladders always end up covering the maximum height differences.

Returning the Wrong Index When Resources Run Out

When bricks become negative, the current building cannot be reached, so the answer should be the previous index. A common mistake is returning i instead of i - 1 in the brute force approach, or returning i when we should return i (the last reachable building) in the heap approach. Pay careful attention to what index represents the last successfully reached building.

from typing import List
import heapq

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        minHeap = []

        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
            if diff <= 0:
                continue

            heapq.heappush(minHeap, diff)
            if len(minHeap) > ladders:
                bricks -= heapq.heappop(minHeap)
                if bricks < 0:
                    return i

        return len(heights) - 1

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for (int i = 0; i < int(heights.size()) - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            if (diff <= 0) continue;

            minHeap.push(diff);
            if (minHeap.size() > ladders) {
                bricks -= minHeap.top(); minHeap.pop();
                if (bricks < 0) return i;
            }
        }

        return int(heights.size()) - 1;
    }
};