Problem 18.9 · Heaps and Priority QueuesMedium

Furthest Building You Can Reach

What it teaches: Deciding in hindsight: give ladders to the largest climbs so far by keeping them in a min-heap, and pay bricks for the smallest.

Practise it on judges as “Furthest Building You Can Reach”.

The problem

Walking from building 0, climbing up from height h[i] to h[i+1] needs either h[i+1] − h[i] bricks or one ladder; going down or level is free. 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

Constraints

1 ≤ n ≤ 10⁵
0 ≤ bricks ≤ 10⁹
0 ≤ ladders ≤ n

Pattern clues in the wording

→ Limited resources to allocate
→ Best to use the strongest resource on the biggest costs

These clues point to Top K with a Heap: Keep a heap of size k: a min-heap for the k largest, a max-heap for the k smallest.

Stuck? Take one hint at a time

Solution.java · starter

import java.util.*;

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        return 0;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	heights = [4,2,7,6,9,14,12] bricks = 5 ladders = 1	4
2	heights = [4,12,2,7,3,18,20,3,19] bricks = 10 ladders = 2	7
3	heights = [14,3,19,3] bricks = 17 ladders = 0	3

From slow to fast

Approaches

1. Min-heap of ladder climbs · O(n log L)

Min-heap of ladder climbs

Time O(n log L) Space O(L)

For each climb d > 0: push d. If the heap holds more than ladders climbs, pop the smallest and pay with bricks. If bricks go negative, return i.

Approach 1

import java.util.PriorityQueue;

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

Verdict: One pass, greedy with a heap.

Before you submit

Edge cases and common mistakes

Test these inputs

No climbs at all
Zero ladders
Enough bricks for everything

Mistakes people make

Using ladders greedily on the first climbs you see.

Interview

Follow-up questions

Why is it safe to move a ladder from one climb to another after the fact?

Command Palette

The problem

Approaches

Min-heap of ladder climbs

Edge cases and common mistakes

Follow-up questions