#1642
Furthest Building You Can Reach
specialist · 855 · lc medium +31 · verified · 50.7% accepted · 6,204 likes · top 39%
Description
You are given building heights, some bricks, and some ladders. Moving from building i to i+1 requires nothing if heights are non-increasing, but if the next building is taller you must spend bricks equal to the height difference or use one ladder. Starting at building 0, use resources optimally and return the index of the furthest building you can reach.
Example 1:
Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Starting at building 0, you can follow these steps:
- Go to building 1 without using ladders nor bricks since 4 >= 2.
- Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7.
- Go to building 3 without using ladders nor bricks since 7 >= 6.
- Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9.
It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
Code
1
2
3