InternDoor

How far bricks and ladders take you

Mediumheap · greedy

Reported in interviews at (where)

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.

Example 1
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.

Example 2
Input
heights = [5,4,3]
bricks = 0
ladders = 0
Output
2

Every step goes down, so it costs nothing.

Limits

  • 1 <= heights.length <= 100000
  • 1 <= heights[i] <= 1000000
  • 0 <= bricks <= 1000000000
  • 0 <= 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

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.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.