Furthest Building You Can Reach

MediumProblemExternal linkUpdated Oct 31, 2026

Description

You get an integer array heights, the heights of buildings in a row, and two integers, bricks and ladders. You start on building 0 and move to the next building, one at a time.

Moving from building i to building i + 1:

If heights[i + 1] <= heights[i], the move is free.
Otherwise it's a climb of heights[i + 1] - heights[i]. Pay for it with that many bricks, or with one ladder.

Return the index of the furthest building you can reach if you use the bricks and ladders as well as possible.

Examples

Example 1

Input: heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1

Output: 4

Explanation: The climbs are 5 (2 to 7), 3 (6 to 9) and 5 (9 to 14). The ladder covers a 5 and the bricks the 3, which leaves 2 bricks for the last climb of 5, so the walk stops at building 4.

Example 2

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

Output: 7

Explanation: Up to building 7 the climbs are 8, 5, 15 and 2: ladders on 15 and 8, bricks for 5 + 2 = 7. The climb of 16 after it would leave 8 + 5 + 2 = 15 for the bricks, more than 10.

Example 3

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

Output: 3

Explanation: No ladders. The drop from 14 to 3 is free, the climb of 16 takes 16 of the 17 bricks, and the drop after it is free too.

Constraints

1 ≤ heights.length ≤ 10^5
1 ≤ heights[i] ≤ 10^6
0 ≤ bricks ≤ 10^9
0 ≤ ladders ≤ heights.length

Editorial

Brute Force

Intuition

If you can reach a building, you can reach every building before it. So the answer is the last building you can reach, and you can test the buildings one at a time.

To reach building j, every climb on the way has to be paid for. A ladder saves as many bricks as the climb it covers, so the ladders should go on the biggest climbs and the bricks on the rest. Sort the climbs before j, biggest first, and add up all but the first ladders of them. If that's at most bricks, j can be reached.

Step-by-Step Explanation

Let's trace heights = [4, 12, 2, 7, 3, 18, 20, 3, 19], bricks = 10, ladders = 2:

Goal 1: the climbs are [8]; the ladders cover them all, so it costs 0 bricks.
Goal 2: 12 to 2 is a drop, free; it still costs 0 bricks.
Goal 3: the climbs are [8, 5]; the ladders cover them all, so it costs 0 bricks.
Goal 4: 7 to 3 is a drop, free; it still costs 0 bricks.
Goal 5: the climbs are [15, 8, 5]; ladders on 15 and 8, bricks for 5, within 10.
Goal 6: the climbs are [15, 8, 5, 2]; ladders on 15 and 8, bricks for 5 + 2 = 7, within 10.
Goal 7: 20 to 3 is a drop, free; it still costs 7 bricks.
Goal 8: the climbs are [16, 15, 8, 5, 2]; ladders on 16 and 15, bricks for 8 + 5 + 2 = 15, more than 10: building 8 can't be reached.

So the answer is 7.

Every Building as the Goal — The outlined buildings are the way to the goal. Below them, the climbs on the way, biggest first: green ones take the ladders, amber ones are paid in bricks.

Algorithm

Keep a list of the climbs so far, empty at the start.
For each building j from 1: if it's taller than building j - 1, add the climb to the list.
Sort the list biggest first. If the climbs after the first ladders add up to more than bricks, return j - 1.
If every building passed, return the last index.

Code

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        vector<int> climbs;                                   // every climb so far
        for (int j = 1; j < (int)heights.size(); j++) {
            if (heights[j] > heights[j - 1]) climbs.push_back(heights[j] - heights[j - 1]);
            vector<int> biggestFirst = climbs;
            sort(biggestFirst.rbegin(), biggestFirst.rend());
            long long cost = 0;                               // the ladders take the biggest, bricks pay the rest
            for (int k = ladders; k < (int)biggestFirst.size(); k++) cost += biggestFirst[k];
            if (cost > bricks) return j - 1;
        }
        return heights.size() - 1;
    }
};

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        climbs = []                                       # every climb so far
        for j in range(1, len(heights)):
            if heights[j] > heights[j - 1]:
                climbs.append(heights[j] - heights[j - 1])
            biggest_first = sorted(climbs, reverse=True)
            if sum(biggest_first[ladders:]) > bricks:     # the ladders take the biggest, bricks pay the rest
                return j - 1
        return len(heights) - 1

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        List<Integer> climbs = new ArrayList<>();                 // every climb so far
        for (int j = 1; j < heights.length; j++) {
            if (heights[j] > heights[j - 1]) climbs.add(heights[j] - heights[j - 1]);
            List<Integer> biggestFirst = new ArrayList<>(climbs);
            biggestFirst.sort(Collections.reverseOrder());
            long cost = 0;                                        // the ladders take the biggest, bricks pay the rest
            for (int k = ladders; k < biggestFirst.size(); k++) cost += biggestFirst.get(k);
            if (cost > bricks) return j - 1;
        }
        return heights.length - 1;
    }
}

var furthestBuilding = function(heights, bricks, ladders) {
    const climbs = [];                                        // every climb so far
    for (let j = 1; j < heights.length; j++) {
        if (heights[j] > heights[j - 1]) climbs.push(heights[j] - heights[j - 1]);
        const biggestFirst = [...climbs].sort((a, b) => b - a);
        let cost = 0;                                         // the ladders take the biggest, bricks pay the rest
        for (let k = ladders; k < biggestFirst.length; k++) cost += biggestFirst[k];
        if (cost > bricks) return j - 1;
    }
    return heights.length - 1;
};

Complexity Analysis

Time Complexity: O(n² log n)

Each of the n buildings sorts up to n climbs.

Space Complexity: O(n)

The list of climbs and its sorted copy.

Why This Approach Is Not Efficient

Each goal sorts every climb again. On random buildings that are all reachable, it took 89.1 ms for 2,000 buildings and 1,866 ms for 8,000 in Python: four times the buildings, 21 times the time. The heap version below took 0.7 ms and 3.0 ms. At 10^5 buildings the sorting alone is tens of billions of steps, over the time limit in C++, Python, Java and JavaScript.

Look at what changes from one goal to the next: one climb is added. Once every ladder is in use, either the new climb is bigger than the smallest ladder climb, which then moves to bricks, or it's paid in bricks itself. Both come to the same move: add the new climb to the ladder climbs, then pay the smallest of them in bricks. A min-heap keeps that smallest on top.

Optimal Approach - A Min-Heap of the Ladder Climbs

Intuition

Walk left to right and give every climb a ladder for now, by pushing it onto a min-heap. The heap holds the climbs the ladders cover.

When the heap holds more climbs than you have ladders, one of them has to be paid in bricks. The cheapest choice is the smallest, the heap's top: pop it and take it from bricks. This can undo an earlier choice: a climb that had a ladder gives it up to a bigger one that came later.

If bricks drops below zero, the climb from building i can't be paid for, so return i. If the walk ends, every building was reached.

Step-by-Step Explanation

Let's trace the same input, heights = [4, 12, 2, 7, 3, 18, 20, 3, 19], bricks = 10, ladders = 2:

4 → 12: climb 8, pushed; the heap [8] fits the 2 ladders.
12 → 2: a drop, free.
2 → 7: climb 5, pushed; the heap [5, 8] fits the 2 ladders.
7 → 3: a drop, free.
3 → 18: climb 15, pushed; the heap's smallest, 5, is popped and paid in bricks, 5 left, and the ladders move to [8, 15].
18 → 20: climb 2, pushed; the heap's smallest, 2, is popped and paid in bricks, 3 left.
20 → 3: a drop, free.
3 → 19: climb 16; the heap's smallest, 8, needs 8 bricks but only 3 are left, so return 7.

The Smallest Ladder Climb Pays in Bricks — The tree is the min-heap of the climbs the ladders cover, smallest on top. Below it, the buildings, with the move being paid for, and the climbs paid in bricks.

Algorithm

Start with an empty min-heap.
For each i from 0 to n - 2: let d = heights[i + 1] - heights[i]. If d <= 0, move on.
Push d. If the heap now holds more than ladders climbs, pop the smallest and subtract it from bricks.
If bricks < 0, return i.
If the loop ends, return n - 1.

Code

JavaScript has no heap built in, so its version carries the MinHeap class from Introduction to Heaps.

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, vector<int>, greater<int>> climbs;   // the climbs the ladders cover, smallest on top
        for (int i = 0; i + 1 < (int)heights.size(); i++) {
            int d = heights[i + 1] - heights[i];
            if (d <= 0) continue;                                 // going down or level is free
            climbs.push(d);
            if ((int)climbs.size() > ladders) {
                bricks -= climbs.top();                           // the smallest of them pays in bricks instead
                climbs.pop();
                if (bricks < 0) return i;
            }
        }
        return heights.size() - 1;
    }
};

import heapq


class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        climbs = []                               # a min-heap of the climbs the ladders cover
        for i in range(len(heights) - 1):
            d = heights[i + 1] - heights[i]
            if d <= 0:
                continue                          # going down or level is free
            heapq.heappush(climbs, d)
            if len(climbs) > ladders:
                bricks -= heapq.heappop(climbs)   # the smallest of them pays in bricks instead
                if bricks < 0:
                    return i
        return len(heights) - 1

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> climbs = new PriorityQueue<>();   // the climbs the ladders cover, smallest on top
        for (int i = 0; i + 1 < heights.length; i++) {
            int d = heights[i + 1] - heights[i];
            if (d <= 0) continue;                                 // going down or level is free
            climbs.offer(d);
            if (climbs.size() > ladders) {
                bricks -= climbs.poll();                          // the smallest of them pays in bricks instead
                if (bricks < 0) return i;
            }
        }
        return heights.length - 1;
    }
}

// A min-heap in an array: the children of i are at 2i + 1 and 2i + 2, its parent at (i - 1) >> 1.
// less(x, y) says x goes above y: smallest on top unless you pass another.
class MinHeap {
    constructor(less = (x, y) => x < y) { this.a = []; this.less = less; }

    push(x) {
        const a = this.a;
        a.push(x);
        let i = a.length - 1;
        while (i > 0 && this.less(a[i], a[(i - 1) >> 1])) {   // sift up while the parent is bigger
            const p = (i - 1) >> 1;
            [a[i], a[p]] = [a[p], a[i]];
            i = p;
        }
    }

    pop() {
        const a = this.a;
        const top = a[0], last = a.pop();
        if (a.length) {
            a[0] = last;                             // the last value takes the root, then sifts down
            let i = 0;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let m = i;
                if (l < a.length && this.less(a[l], a[m])) m = l;
                if (r < a.length && this.less(a[r], a[m])) m = r;   // the smaller child, or the bigger ends up above it
                if (m === i) break;
                [a[i], a[m]] = [a[m], a[i]];
                i = m;
            }
        }
        return top;
    }
}

var furthestBuilding = function(heights, bricks, ladders) {
    const climbs = new MinHeap();                 // the climbs the ladders cover, smallest on top
    for (let i = 0; i + 1 < heights.length; i++) {
        const d = heights[i + 1] - heights[i];
        if (d <= 0) continue;                     // going down or level is free
        climbs.push(d);
        if (climbs.a.length > ladders) {
            bricks -= climbs.pop();               // the smallest of them pays in bricks instead
            if (bricks < 0) return i;
        }
    }
    return heights.length - 1;
};

Complexity Analysis

Time Complexity: O(n log L), where L is ladders

The heap never holds more than L + 1 climbs, and each building costs at most one push and one pop.

Space Complexity: O(L)

The heap. A plain list would need a scan to find its smallest, O(L) per building instead of O(log L).

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Spending the ladders on the first climbs. if ladders > 0:

On heights = [1, 2, 12], bricks = 5, ladders = 1 it returns 1; the answer is 2. A ladder is worth most on the biggest climb, and you can't know which that is when you meet a climb. Here the ladder goes on the climb of 1, which leaves 5 bricks for a climb of 10. Keep the ladder climbs in a heap and give back the smallest when a bigger one comes.

Paying in bricks while they last. if bricks >= d:

On heights = [1, 6, 9, 12], bricks = 6, ladders = 1 it returns 2; the answer is 3. Bricks spent on a big early climb are gone for the small ones after it. Here 5 bricks go on the first climb, which leaves 1 brick for two climbs of 3, so the walk stops at building 2. The ladder belongs on the 5, and the 6 bricks then pay 3 + 3.

Using a max-heap. heapq.heappush(climbs, -d)

On heights = [1, 2, 12, 13], bricks = 2, ladders = 1 it returns 1; the answer is 3. The heap has to hand back the climb that's cheapest in bricks, so it's a min-heap. A max-heap pays the biggest climb in bricks and keeps the ladder on a small one: here it tries to pay the climb of 10 with 2 bricks and stops at building 1.

Counting a drop as a climb. d = abs(heights[i + 1] - heights[i])

On heights = [5, 1, 2], bricks = 0, ladders = 1 it returns 1; the answer is 2. Going down costs nothing. Taking the absolute difference charges for every drop: here the ladder goes on the drop from 5 to 1, and the climb of 1 after it can't be paid.

Stopping when the bricks reach zero. if bricks <= 0:

On heights = [1, 2, 3], bricks = 2, ladders = 0 it returns 1; the answer is 2. Spending your last brick still pays for the climb. Testing bricks <= 0 after paying stops one building early whenever the bricks come out exact, as the 2 bricks do here.

Returning the next building. return i + 1

On heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1 it returns 5; the answer is 4. The check runs on the climb from building i to building i + 1. When it can't be paid, you're still standing on i, so return i, not i + 1.

Where This Pattern Is Taught

This problem practises a heap that lets a greedy choice be taken back. It's taught in Merging and Scheduling with a Heap, next to IPO, with the bug of spending a ladder whenever one is left.