Furthest Building You Can Reach

Medium Heaps Top K / Kth Largest / Smallest Original on LeetCode

Furthest Building You Can Reach is a medium heaps problem solved with the top k / kth largest / smallest pattern. The best approach, optimal (min-heap of ladder climbs), runs in O(n log L) time and O(L) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (binary search on the answer + sorting) up.

Problem

You are standing on building 0 of a row of buildings whose heights are given in heights. You walk from building i to building i + 1.

Stepping onto a building that is the same height or lower is free. Stepping up from height a to height b > a needs either one ladder or exactly b - a bricks. You have bricks bricks and ladders ladders in total, and each brick or ladder can be used only once.

Spend them as cleverly as possible and return the largest building index you can reach.

Examples

Example 1

Input
heights = [3, 7, 5, 6, 10, 2, 12], bricks = 5, ladders = 1
Output
5
Why
The climbs are 4, 1, 4 and then 10 at the end. Ladder on one 4, bricks for 1 + 4 = 5 reaches index 5; the final climb of 10 would need 9 bricks even with the ladder moved to it.

Example 2

Input
heights = [2, 9, 4, 4, 1, 8], bricks = 3, ladders = 1
Output
4
Why
The climb of 7 to index 1 uses the ladder. Moving down or level is free up to index 4. The climb of 7 to index 5 needs 7 bricks but only 3 remain.

Example 3

Input
heights = [5, 3, 2], bricks = 0, ladders = 0
Output
2
Why
Every step goes down, so nothing is needed and the last building is reached.

Constraints

  • 1 <= heights.length <= 10^5
  • 1 <= heights[i] <= 10^6
  • 0 <= bricks <= 10^9
  • 0 <= ladders <= heights.length

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (binary search on the answer + sorting)O(n log² n)O(n)
Optimal (min-heap of ladder climbs)O(n log L)O(L)

1Brute force (binary search on the answer + sorting)

TimeO(n log² n)O(log n) checks, each sorting up to n climbs.
SpaceO(n)The list of climbs for one check.

Reachability is monotonic: if you can reach index k you can reach every index before it. Binary search for the largest reachable k. To test a k, list the upward climbs among the first k steps, sort them, let the ladders cover the largest ones and check that the remaining sum fits in the bricks.

  1. lo = 0, hi = n - 1.
  2. For mid, gather every positive difference heights[i+1] - heights[i] with i < mid.
  3. Sort them descending; skip the first ladders climbs and sum the rest.
  4. If the sum <= bricks, mid is reachable: lo = mid; otherwise hi = mid - 1.
  5. Return lo.
class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        int lo = 0, hi = heights.length - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo + 1) / 2;
            if (canReach(heights, bricks, ladders, mid)) lo = mid;
            else hi = mid - 1;
        }
        return lo;
    }

    private boolean canReach(int[] heights, int bricks, int ladders, int k) {
        List<Integer> climbs = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            int d = heights[i + 1] - heights[i];
            if (d > 0) climbs.add(d);
        }
        climbs.sort(Collections.reverseOrder());
        long need = 0;
        for (int i = ladders; i < climbs.size(); i++) need += climbs.get(i);
        return need <= bricks;
    }
}

2Optimal (min-heap of ladder climbs)

TimeO(n log L)Each climb is pushed and popped at most once; the heap never holds more than L + 1 items (L = ladders).
SpaceO(L)The heap holds at most L + 1 climbs.

Move forward one building at a time and tentatively put a ladder on every climb, pushing the climb onto a min-heap. As soon as the heap holds more climbs than there are ladders, the smallest climb in it should have been paid with bricks: pop it and subtract it from the bricks. If the bricks go negative, the current building cannot be reached.

  1. Create an empty min-heap.
  2. For i from 0 to n - 2, let d = heights[i+1] - heights[i]; skip if d <= 0.
  3. Push d. If the heap size exceeds ladders, pop the smallest and subtract it from bricks.
  4. If bricks < 0, return i.
  5. If the loop finishes, return n - 1.
class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < heights.length - 1; i++) {
            int d = heights[i + 1] - heights[i];
            if (d <= 0) continue;
            heap.offer(d);
            if (heap.size() > ladders) {
                bricks -= heap.poll();
                if (bricks < 0) return i;
            }
        }
        return heights.length - 1;
    }
}

Edge cases to test

  • A single building: the answer is 0
  • Strictly decreasing heights: you always reach the end for free
  • No bricks and no ladders
  • More ladders than climbs
  • Greedy 'use bricks first' fails when a huge climb comes later

Hints

Hint 1

Only upward moves cost anything. A ladder is worth the most when it covers the biggest climb.

Hint 2

To check whether index k is reachable: take all climbs up to k, give ladders to the largest ones and pay the rest with bricks.

Hint 3

Walk left to right and keep the climbs that currently hold a ladder in a min-heap. When there are more climbs than ladders, the smallest of them should be paid with bricks instead.

FAQ

What is the best time complexity for Furthest Building You Can Reach?

Optimal (min-heap of ladder climbs) runs in O(n log L) time and O(L) extra space. Each climb is pushed and popped at most once; the heap never holds more than L + 1 items (L = ladders).

Which pattern does Furthest Building You Can Reach use?

It is a heaps problem that uses the top k / kth largest / smallest pattern. Other problems with the same pattern: Kth Largest Element in an Array, Kth Largest Element in a Stream, Top K Frequent Words.

Is there a brute force solution for Furthest Building You Can Reach?

Yes. Brute force (binary search on the answer + sorting) takes O(n log² n) time and O(n) space. Reachability is monotonic: if you can reach index k you can reach every index before it.

Which edge cases should I test for Furthest Building You Can Reach?

A single building: the answer is 0; Strictly decreasing heights: you always reach the end for free; No bricks and no ladders; More ladders than climbs; Greedy 'use bricks first' fails when a huge climb comes later.