How far bricks and ladders take you
You walk along a row of buildings whose heights are heights[0], heights[1], ..., starting on building 0.
Stepping to a building of the same height or lower is free. Stepping up to a taller one costs either one ladder, whatever the climb, or as many bricks as the climb: heights[i + 1] - heights[i].
You have bricks bricks and ladders ladders. Return the index of the furthest building you can reach when you use them as well as possible.
- Input
heights = [3,8,5,9,10,2,20]
bricks = 4
ladders = 1- Output
3
Climbs of 5, 4 and 1 come first. The ladder covers 5 and the bricks pay for 4, but then the climb of 1 to building 4 cannot be paid.
- Input
heights = [5,4,3]
bricks = 0
ladders = 0- Output
2
Every step goes down, so it costs nothing.
Limits
1 <= heights.length <= 1000001 <= heights[i] <= 10000000 <= bricks <= 10000000000 <= ladders <= heights.length
Hints
Hint 1
Ladders are worth the most on the biggest climbs, but you only see the climbs one at a time.
Hint 2
Put each climb into a min-heap. Whenever the heap holds more climbs than you have ladders, pay for its smallest climb with bricks. Stop when the bricks run out.
Where this was reported
- Flipkart, SDE-1 off-campus interview, 2024 (Hashnode)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.
