566. Bricks and Ladders
A hiker walks along a row of platforms from left to right. heights[i] is the height of platform i, and she starts on platform 0. From platform i she may step to platform i+1 only. If the next platform is not higher, the step is free. If it is higher, she must either lay down a number of bricks equal to the height difference, or use one of her ladders, which covers any height difference at all.
She has bricks bricks and ladders ladders in total, and neither can be reused. Return the largest index of a platform she can reach (platforms are numbered from 0).
Aim for O(n log n) time and O(n) space.
Example 1
- Input:
- heights = [2,5,3,9,4], bricks = 3, ladders = 1
- Output:
- 4
- Explanation:
Climbs are 3 and 6; the ladder covers the 6 and the 3 bricks cover the 3, so the last platform (index 4) is reachable.
Example 2
- Input:
- heights = [1,4,8,12], bricks = 5, ladders = 0
- Output:
- 1
- Explanation:
Bricks pay for the first climb of 3 (2 left), but the next climb of 4 cannot be paid, so she stops at index 1.
Example 3
- Input:
- heights = [5,4,3], bricks = 0, ladders = 0
- Output:
- 2
- Explanation:
Every step goes downhill and is free, so she reaches index 2.
Constraints
1 ≤ heights.length ≤ 1000001 ≤ heights[i] ≤ 1090 ≤ bricks ≤ 1090 ≤ ladders ≤ heights.length
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 2,000 msC++ 500 msJava 1,000 msJavaScript 1,000 msTypeScript 1,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)