Furthest Building You Can Reach

MediumHeapheap

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You are walking along a row of buildings with heights heights[0..n-1], starting on building 0, and you move from building i to building i + 1 one step at a time. If the next building is no taller than the current one, the step is free. Otherwise you must cover the climb d = heights[i+1] - heights[i] either with exactly d bricks or with one ladder. You have bricks bricks and ladders ladders in total, and each can be used only once. Return the largest building index you can reach if you spend your resources optimally.

Examples

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Step to 2 for free, use 5 bricks to reach 7, step down to 6, and use the ladder for 6 -> 9. The climb to 14 needs 5 more bricks, so index 4 is the limit.
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
The climbs before index 7 are 8, 5, 15 and 2: ladders take 8 and 15, and 7 bricks pay for 5 and 2. Adding the last climb of 16 would leave at least 15 bricks of climbing without a ladder, more than 10.
Input: heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
The only climb, 3 -> 19, costs 16 bricks, which you have.

Constraints

  • 1 <= heights.length <= 10^5
  • 1 <= heights[i] <= 10^6
  • 0 <= bricks <= 10^9
  • 0 <= ladders <= heights.length

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More heap problems