Furthest Building You Can Reach
MediumUpdated: Aug 2, 2025
Practice on:
Problem
You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.
You start your journey from building 0 and move to the next building by possibly using bricks or ladders.
While moving from building i to building i+1 (0-indexed),
- If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
- If the current building's height is less than the next building's height, you can either use one ladder or
(h[i+1] - h[i])bricks.
Return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.
Examples
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Example 3:
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
Solution
This problem is hard such that, we think it is DP related, but even greedy can be applied.
Method 1 - Greedy Using MaxHeap
Ladders should be saved for the largest jumps since they can cover any height difference, making them more valuable. It's best to use bricks first and only switch to ladders when bricks run out.
If bricks are used on a large jump, we can later swap that usage for a ladder to recover bricks for future steps.
Note that we are looping till n-2, because we are using index i+1 for heights array.
Code
C++
class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
priority_queue<int> maxHeap;
int bricksUsed = 0;
int n = heights.size();
for (int i = 0; i < n - 1; ++i) {
int diff = heights[i + 1] - heights[i];
if (diff <= 0) continue;
if (bricksUsed + diff <= bricks) {
bricksUsed += diff;
maxHeap.push(diff);
} else if (ladders > 0) {
maxHeap.push(diff);
int maxUsedBricks = maxHeap.top();
maxHeap.pop();
bricksUsed += diff - maxUsedBricks;
ladders--;
} else {
return i;
}
}
return n - 1;
}
};
Go
type MaxHeap []int
func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func furthestBuilding(heights []int, bricks int, ladders int) int {
h := &MaxHeap{}
heap.Init(h)
bricksUsed := 0
n := len(heights)
for i := 0; i < n-1; i++ {
diff := heights[i+1] - heights[i]
if diff <= 0 {
continue
}
if bricksUsed+diff <= bricks {
bricksUsed += diff
heap.Push(h, diff)
} else if ladders > 0 {
heap.Push(h, diff)
maxUsedBricks := heap.Pop(h).(int)
bricksUsed += diff - maxUsedBricks
ladders--
} else {
return i
}
}
return n - 1
}
Java
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
var pq = new PriorityQueue<Integer>(Collections.reverseOrder());
int bricksUsed = 0;
int n = heights.length;
for(int i = 0 ; i < n-1 ; i++){
int diff = heights[i+1] - heights[i];
// If current height is higher, we don't have to use
// bricks or ladder.
if(diff <= 0){
continue;
}
// We have to use either brick or ladder.
if(diff + bricksUsed <= bricks){
// Prefer bricks because we can later change from
// bricks to ladder as we will see below.
bricksUsed += diff;
pq.add(diff);
} else if(ladders > 0){
// If even bricks are insufficient, check ladders.
// if peek of heap is more than current diff
// then remove peek heap, and get back some bricks
pq.offer(diff);
int maxUsedBricks = pq.peek();
bricksUsed += maxUsedBricks - diff;
ladders--;
}
// Unfortunately, it's not possible to go ahead any further.
else return i;
}
// This is the max we can go ahead.
return n-1;
}
}
Kotlin
class Solution {
fun furthestBuilding(heights: IntArray, bricks: Int, ladders: Int): Int {
val maxHeap = PriorityQueue<Int>(compareByDescending { it })
var bricksUsed = 0
var laddersLeft = ladders
for (i in 0 until heights.size - 1) {
val diff = heights[i + 1] - heights[i]
if (diff <= 0) continue
if (bricksUsed + diff <= bricks) {
bricksUsed += diff
maxHeap.add(diff)
} else if (laddersLeft > 0) {
maxHeap.add(diff)
val maxUsedBricks = maxHeap.poll()
bricksUsed += diff - maxUsedBricks
laddersLeft--
} else {
return i
}
}
return heights.size - 1
}
}
Python
class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
max_heap = []
bricks_used = 0
n = len(heights)
for i in range(n - 1):
diff = heights[i + 1] - heights[i]
if diff <= 0:
continue
if bricks_used + diff <= bricks:
bricks_used += diff
heapq.heappush(max_heap, -diff)
elif ladders > 0:
heapq.heappush(max_heap, -diff)
max_used_bricks = -heapq.heappop(max_heap)
bricks_used += diff - max_used_bricks
ladders -= 1
else:
return i
return n - 1
Rust
impl Solution {
pub fn furthest_building(heights: Vec<i32>, bricks: i32, ladders: i32) -> i32 {
let mut max_heap = BinaryHeap::new();
let mut bricks_used = 0;
let mut ladders_left = ladders;
let n = heights.len();
for i in 0..n - 1 {
let diff = heights[i + 1] - heights[i];
if diff <= 0 {
continue;
}
if bricks_used + diff <= bricks {
bricks_used += diff;
max_heap.push(diff);
} else if ladders_left > 0 {
max_heap.push(diff);
if let Some(max_used_bricks) = max_heap.pop() {
bricks_used += diff - max_used_bricks;
}
ladders_left -= 1;
} else {
return i as i32;
}
}
(n - 1) as i32
}
}
Complexity
- ⏰ Time complexity:
O(n log n). For each of the n-1 building jumps, you may push or pop from the max-heap, each operation taking O(log n) time. - 🧺 Space complexity:
O(n). In the worst case, the max-heap can store up to O(n) jump differences.
Method 2 - Greedy Using MinHeap
Let diff be the difference between consecutive building heights.
Instead of using a max-heap to reclaim bricks, we can use a min-heap to keep track of the largest k jumps where ladders are used.
For each positive diff, add it to the min-heap; if the heap size exceeds the number of ladders, use bricks for the smallest jump by removing it from the heap and subtracting from bricks.
If bricks run out (bricks < 0), return the current index; otherwise, if all buildings are reachable, return the last index.
Code
C++
class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
priority_queue<int, vector<int>, greater<int>> minHeap;
int n = heights.size();
for (int i = 0; i < n - 1; ++i) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
minHeap.push(diff);
}
if (minHeap.size() > ladders) {
bricks -= minHeap.top();
minHeap.pop();
}
if (bricks < 0) {
return i;
}
}
return n - 1;
}
};
Go
type MinHeap []int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[:n-1]
return x
}
func furthestBuilding(heights []int, bricks int, ladders int) int {
h := &MinHeap{}
heap.Init(h)
for i := 0; i < len(heights)-1; i++ {
diff := heights[i+1] - heights[i]
if diff > 0 {
heap.Push(h, diff)
}
if h.Len() > ladders {
bricks -= heap.Pop(h).(int)
}
if bricks < 0 {
return i
}
}
return len(heights) - 1
}
Java
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < heights.length - 1; i++) {
int diff = heights[i + 1] - heights[i];
if (diff > 0) {
pq.add(d);
}
if (pq.size() > ladders) {
bricks -= pq.poll();
}
if (bricks<0) {
return i;
}
}
return heights.length - 1;
}
}
Kotlin
class Solution {
fun furthestBuilding(heights: IntArray, bricks: Int, ladders: Int): Int {
val minHeap = PriorityQueue<Int>()
var bricksLeft = bricks
for (i in 0 until heights.size - 1) {
val diff = heights[i + 1] - heights[i]
if (diff > 0) {
minHeap.add(diff)
}
if (minHeap.size > ladders) {
bricksLeft -= minHeap.poll()
}
if (bricksLeft < 0) {
return i
}
}
return heights.size - 1
}
}
Python
class Solution:
def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
min_heap = []
for i in range(len(heights) - 1):
diff = heights[i + 1] - heights[i]
if diff > 0:
heapq.heappush(min_heap, diff)
if len(min_heap) > ladders:
bricks -= heapq.heappop(min_heap)
if bricks < 0:
return i
return len(heights) - 1
Rust
impl Solution {
pub fn furthest_building(heights: Vec<i32>, mut bricks: i32, ladders: i32) -> i32 {
let mut min_heap = BinaryHeap::new();
let n = heights.len();
for i in 0..n - 1 {
let diff = heights[i + 1] - heights[i];
if diff > 0 {
min_heap.push(Reverse(diff));
}
if min_heap.len() > ladders as usize {
if let Some(Reverse(smallest)) = min_heap.pop() {
bricks -= smallest;
}
}
if bricks < 0 {
return i as i32;
}
}
(n - 1) as i32
}
}
Complexity
- ⏰ Time complexity:
O(n log n). For each of the n-1 jumps, you may push to and pop from the min-heap, each operation taking O(log n) time. - 🧺 Space complexity:
O(n). The min-heap can also store up to O(n) jump differences in the worst case.