Furthest Building You Can Reach

Problem

You have bricks and ladders. Moving from building i to i+1 if heights[i+1] > heights[i]: use bricks or a ladder. Ladders handle any climb; bricks handle exact diff. Return furthest reachable building.

Key insight (Greedy): Assign ladders to the largest climbs. Use min-heap to track the k largest climbs used for ladders. If we've used more than k ladders, swap the smallest ladder-climb with bricks.

Solutions

// C++
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
    priority_queue<int, vector<int>, greater<int>> minH; // ladder-assigned climbs
    for (int i = 0; i < (int)heights.size()-1; i++) {
        int diff = heights[i+1] - heights[i];
        if (diff <= 0) continue;
        minH.push(diff);
        if ((int)minH.size() > ladders) {
            bricks -= minH.top(); minH.pop();
        }
        if (bricks < 0) return i;
    }
    return heights.size()-1;
}

// Java
public int furthestBuilding(int[] heights, int bricks, int ladders) {
    PriorityQueue<Integer> minH = new PriorityQueue<>();
    for (int i = 0; i < heights.length - 1; i++) {
        int diff = heights[i+1] - heights[i];
        if (diff <= 0) continue;
        minH.offer(diff);
        if (minH.size() > ladders) bricks -= minH.poll();
        if (bricks < 0) return i;
    }
    return heights.length - 1;
}

// JavaScript
function furthestBuilding(heights, bricks, ladders) {
    const heap = []; // sorted ascending (ladder-assigned climbs)
    for (let i = 0; i < heights.length - 1; i++) {
        const diff = heights[i+1] - heights[i];
        if (diff <= 0) continue;
        let pos = heap.findIndex(x => x >= diff);
        if (pos === -1) heap.push(diff); else heap.splice(pos, 0, diff);
        if (heap.length > ladders) bricks -= heap.shift();
        if (bricks < 0) return i;
    }
    return heights.length - 1;
}

# Python
import heapq

def furthestBuilding(heights, bricks, ladders):
    heap = []  # min-heap of ladder-assigned climbs
    for i in range(len(heights) - 1):
        diff = heights[i + 1] - heights[i]
        if diff <= 0:
            continue
        heapq.heappush(heap, diff)
        if len(heap) > ladders:
            bricks -= heapq.heappop(heap)
        if bricks < 0:
            return i
    return len(heights) - 1

Complexity

Time: O(n log k) where k = ladders
Space: O(k)

Key Insight

Allocate ladders to k largest climbs. The min-heap lets us efficiently determine when to swap a ladder for bricks on the smallest ladder-climb (freeing the ladder for a bigger future climb isn't possible here, but it correctly identifies when to use bricks).