Farthest Building You Can Reach

Share

Given heights[], bricks, and ladders, move through buildings using bricks for small climbs and save ladders for the largest climbs. Find the farthest building index you can reach.

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

Greedy with a min-heap: when we need to climb, first use a ladder. Track all ladder-used climbs in a min-heap. If heap size exceeds ladders, replace the smallest ladder-used climb with bricks instead.

  • Min-heap stores climb heights where ladders were used.
  • For each climb diff = heights[i+1] - heights[i] > 0:
  • Push diff into heap.
  • If heap.size() > ladders: pop min from heap (now use bricks for that), bricks -= min.
  • If bricks < 0: cannot proceed, return i.
Java
import java.util.*;

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int i = 0; i < heights.length - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            if (diff <= 0) continue;
            minHeap.offer(diff);
            if (minHeap.size() > ladders) {
                bricks -= minHeap.poll();
                if (bricks < 0) return i;
            }
        }
        return heights.length - 1;
    }
}
  • Time Complexity: O(N log L) where L = ladders
  • Space Complexity: O(L)