Problem statement

You move from building i to i+1. Going down or level is free; climbing up needs either one ladder (any height) or heights[i+1] - heights[i] bricks.

Starting at building 0 with the given bricks and ladders, return the furthest building index you can reach.

Example 1

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Bricks on +5, ladder on +3, cannot afford +5 again.

Example 2

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

Example 3

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

Constraints

• 2 <= heights.length <= 30
• 1 <= heights[i] <= 100
• 0 <= bricks <= 300
• 0 <= ladders <= 5

Hints for Furthest Building You Can Reach

1. Hint 1

   Use ladders for the LARGEST climbs; a min-heap of climbs taken so far tells you which to downgrade to bricks.

2. Hint 2

   When the heap exceeds the ladder count, pay the smallest climb with bricks.

How to solve Furthest Building You Can Reach

Ladders are unconditional but scarce, so they should be spent on the largest climbs. The catch is that you cannot know which climbs are largest until you have seen them. The fix is to be optimistic: give every climb a ladder as you meet it, and when you have handed out more ladders than you own, take the ladder back from the smallest climb so far and pay for that one with bricks instead.

Approach

1. Walk the buildings in order and compute each climb heights[i+1] - heights[i]; a non-positive climb is free, so skip it.
2. Push the climb into a min-heap — provisionally, it gets a ladder.
3. If the heap now holds more climbs than you have ladders, pop the smallest and pay it with bricks.
4. If the bricks spent ever exceed your supply, you could not make that step: return i, the last building you reached.
5. Surviving the whole walk means you reach the final building, index n - 1.

Why it works

At every point the heap contains exactly the ladders largest climbs seen so far, and every other positive climb has been paid with bricks. That is optimal for the prefix: any other assignment either uses a ladder on a smaller climb — which can be swapped for a bigger one without spending more bricks — or wastes bricks on a climb a spare ladder could cover. Since the assignment is optimal at every prefix, the first step where bricks run out is genuinely the first unreachable one.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Downgrade the smallest climb in the heap to bricks, never the current one — the current climb may well be the biggest you have seen.
• Skip climbs that go down or stay level; charging for them wastes the whole budget.
• Return i (the building you are standing on), not i + 1, when the bricks run out.
• The test is usedBricks > bricks — spending exactly all your bricks is still a success.

Reference solution

Python

from typing import List
import heapq

def furthestBuilding(heights: List[int], bricks: int, ladders: int) -> int:
    heap = []
    used = 0
    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:
            used += heapq.heappop(heap)
            if used > bricks:
                return i
    return len(heights) - 1

Java

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

C++

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

JavaScript

var furthestBuilding = function(heights, bricks, ladders) {
    const laddered = [];
    let usedBricks = 0;
    for (let i = 0; i + 1 < heights.length; i++) {
        const diff = heights[i + 1] - heights[i];
        if (diff <= 0) continue;
        laddered.push(diff);
        laddered.sort(function(a, b) { return a - b; });
        if (laddered.length > ladders) {
            usedBricks += laddered.shift();
            if (usedBricks > bricks) return i;
        }
    }
    return heights.length - 1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium