DSA problem
Furthest Building You Can Reach
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: 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.
The greedy insight is that ladders are the most powerful resource — each one covers an arbitrarily large gap. So we should save ladders for the biggest gaps we encounter and pay for the smaller gaps with bricks. But we cannot know in advance which gaps are "big" until we have walked the whole street.
Use a min-heap of the gaps where a ladder is currently allocated. For every positive gap we encounter, push it onto the heap. Whenever the heap holds more than ladders entries, the smallest of those gaps is no longer worth a ladder — pop it and pay for that gap with bricks instead. If bricks ever go negative, we cannot reach the next building, so return the previous index. Otherwise we walk all the way to the last building. The total work is O(n log L) where L is the number of ladders.
Examples
heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 14heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 27heights = [14,3,19,3], bricks = 17, ladders = 03Constraints
- 1 <= heights.length <= 10^5
- 1 <= heights[i] <= 10^6
- 0 <= bricks <= 10^9
- 0 <= ladders <= heights.length
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.