Furthest Building You Can Reach
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^51 <= heights[i] <= 10^60 <= bricks <= 10^90 <= 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.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
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.
| Approach | Time | Space |
|---|---|---|
| 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)
O(n log² n)O(log n) checks, each sorting up to n climbs.O(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.
- lo = 0, hi = n - 1.
- For mid, gather every positive difference heights[i+1] - heights[i] with i < mid.
- Sort them descending; skip the first
laddersclimbs and sum the rest. - If the sum <= bricks, mid is reachable: lo = mid; otherwise hi = mid - 1.
- 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;
}
}class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
def can_reach(k: int) -> bool:
climbs = [heights[i + 1] - heights[i] for i in range(k) if heights[i + 1] > heights[i]]
climbs.sort(reverse=True)
return sum(climbs[ladders:]) <= bricks
lo, hi = 0, len(heights) - 1
while lo < hi:
mid = (lo + hi + 1) // 2
if can_reach(mid):
lo = mid
else:
hi = mid - 1
return loclass Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
int lo = 0, hi = heights.size() - 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:
bool canReach(vector<int>& heights, int bricks, int ladders, int k) {
vector<int> climbs;
for (int i = 0; i < k; i++) {
int d = heights[i + 1] - heights[i];
if (d > 0) climbs.push_back(d);
}
sort(climbs.rbegin(), climbs.rend());
long long need = 0;
for (int i = ladders; i < (int)climbs.size(); i++) need += climbs[i];
return need <= bricks;
}
};function furthestBuilding(heights, bricks, ladders) {
const canReach = (k) => {
const climbs = [];
for (let i = 0; i < k; i++) {
const d = heights[i + 1] - heights[i];
if (d > 0) climbs.push(d);
}
climbs.sort((a, b) => b - a);
let need = 0;
for (let i = ladders; i < climbs.length; i++) need += climbs[i];
return need <= bricks;
};
let lo = 0, hi = heights.length - 1;
while (lo < hi) {
const mid = lo + Math.floor((hi - lo + 1) / 2);
if (canReach(mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}2Optimal (min-heap of ladder climbs)
O(n log L)Each climb is pushed and popped at most once; the heap never holds more than L + 1 items (L = ladders).O(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.
- Create an empty min-heap.
- For i from 0 to n - 2, let d = heights[i+1] - heights[i]; skip if d <= 0.
- Push d. If the heap size exceeds ladders, pop the smallest and subtract it from bricks.
- If bricks < 0, return i.
- 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;
}
}class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
heap = []
for i in range(len(heights) - 1):
d = heights[i + 1] - heights[i]
if d <= 0:
continue
heapq.heappush(heap, d)
if len(heap) > ladders:
bricks -= heapq.heappop(heap)
if bricks < 0:
return i
return len(heights) - 1class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
priority_queue<int, vector<int>, greater<int>> heap;
for (int i = 0; i + 1 < (int)heights.size(); i++) {
int d = heights[i + 1] - heights[i];
if (d <= 0) continue;
heap.push(d);
if ((int)heap.size() > ladders) {
bricks -= heap.top();
heap.pop();
if (bricks < 0) return i;
}
}
return heights.size() - 1;
}
};function furthestBuilding(heights, bricks, ladders) {
// small binary min-heap
const heap = [];
const push = (x) => {
heap.push(x);
let i = heap.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (heap[p] <= heap[i]) break;
[heap[p], heap[i]] = [heap[i], heap[p]];
i = p;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length > 0) {
heap[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < heap.length && heap[l] < heap[m]) m = l;
if (r < heap.length && heap[r] < heap[m]) m = r;
if (m === i) break;
[heap[m], heap[i]] = [heap[i], heap[m]];
i = m;
}
}
return top;
};
for (let i = 0; i < heights.length - 1; i++) {
const d = heights[i + 1] - heights[i];
if (d <= 0) continue;
push(d);
if (heap.length > ladders) {
bricks -= pop();
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.