Furthest Building You Can Reach
Medium · Heap & Counting · Array · Greedy · Heap (Priority Queue)
Problem
You are given heights, the heights of buildings in a row, plus a number of bricks and ladders. You start on building 0 and move one building at a time to the right.
Moving from building i to i + 1:
- If heights[i + 1] <= heights[i], it costs nothing.
- Otherwise you must use either one ladder or heights[i + 1] - heights[i] bricks.
Using your bricks and ladders as well as possible, return the index of the furthest building you can reach.
Examples
Input: heights = [3,6,4,10,12], bricks = 3, ladders = 1 Output: 3
Pay 3 bricks for the climb to 6 and use the ladder for the climb of 6 to 10. The last climb of 2 cannot be paid.
Input: heights = [1,2,3], bricks = 0, ladders = 0 Output: 0
The first step up already needs a brick or a ladder.
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 Output: 7
Ladders on the climbs of 8 and 15, bricks for 5 and 2 (7 bricks). The climb of 16 to building 8 is too much.
Constraints
- 1 <= len(heights) <= 10^5
- 1 <= heights[i] <= 10^6
- 0 <= bricks <= 10^9
- 0 <= ladders <= len(heights)
Approaches
- Baseline: re-plan every prefix from scratch — time O(n² log n), space O(n)
Follow-up
Answer the same question with a binary search on the answer: can building k be reached? Sort the first k climbs and check. That is O(n log² n). Why is the heap both simpler and faster?
Related problems
Start free on Cariara · Coding problems · System design studio
