Farthest Building You Can Reach

Share

Use bricks and ladders to jump between buildings. Ladders used for tallest jumps. Find farthest building reachable.

Example 1
Input: heights=[4,2,7,6,9,14,12], bricks=5, ladders=1 → Output: 4
Example 2
Input: heights=[4,12,2,7,3,18,20,3,19], bricks=10, ladders=2 → Output: 7

Solution Approach

Use a min-heap of size ladders. For each upward jump, add to heap. When heap exceeds ladders size, use bricks for smallest jump in heap.

  • For each gap heights[i+1]-heights[i] > 0
  • Add gap to min-heap
  • If heap size > ladders, use bricks for heap.poll() (smallest jump)
  • If not enough bricks, return i
  • Return last index
Java
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) continue;
        pq.offer(diff);
        if (pq.size() > ladders) {
            bricks -= pq.poll();
        }
        if (bricks < 0) return i;
    }
    return heights.length - 1;
}
  • Time Complexity: O(n log L)
  • Space Complexity: O(L)