Furthest building you can reach

Array Greedy Heap (Priority Queue)

50.7% acceptance

Feb 25, 2026

6202

150

There are n buildings in a row. You are given an integer array heights where heights[i] is the height of the ith building. 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. Given the integers bricks and ladders, return the furthest building index (0-indexed) you can reach if you use the given ladders and bricks optimally.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

use std::collections::BinaryHeap;
use std::cmp::Reverse;

impl Solution {
  pub fn furthest_building(heights: Vec<i32>, mut bricks: i32, ladders: i32) -> i32 {
    // min-heap of diffs where we used a ladder
    let mut heap: BinaryHeap<Reverse<i32>> = BinaryHeap::new();
    for i in 0..heights.len() - 1 {
      let diff = heights[i + 1] - heights[i];
      if diff <= 0 {
        continue;
      }
      // Use a ladder for this diff
      heap.push(Reverse(diff));
      // If we've used more ladders than available, swap smallest ladder use for bricks
      if heap.len() > ladders as usize {
        let Reverse(smallest) = heap.pop().unwrap();
        bricks -= smallest;
        if bricks < 0 {
          return i as i32;
        }
      }
    }
    (heights.len() - 1) as i32
  }
}