Furthest Building You Can Reach

1. Define the problem

You are given heights, where heights_i is the height of building i, plus a number of bricks and a number of ladders. You start at building 0 and move forward one building at a time. Moving to a shorter or equal building is free. Moving up costs either that exact number of bricks, or one ladder no matter how big the climb is. Return the furthest building index you can reach if you spend bricks and ladders in the best possible way. Pretend every climb uses a ladder, and keep those climbs in a min-heap . The moment you have more ladder climbs than ladders, the smallest of them is the one that should have been bricks instead, so pop it and pay for it with bricks. Ladders end up on the biggest climbs, which is what you want.

Constraints

1 ≤ heights.length ≤ 10⁵
1 ≤ heights_i ≤ 10⁶
0 ≤ bricks ≤ 10⁹
0 ≤ ladders ≤ heights.length

Example

Inputheights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1

Output4

Explanation Going 4 to 2 is free. The climb of 5 up to building 2 takes the single ladder. Going 7 to 6 is free. The climb of 3 up to building 4 takes 3 bricks, leaving 2. The next climb of 5 needs either bricks you do not have or a ladder you already used, so building 4 is as far as you get.

2. Know the words first

In plain terms

Heap: A container that always knows its best item, where best means smallest or largest depending on how you set it up. Adding an item or taking the best item out costs about log n steps, and you never have to sort the whole collection.
Backing array: A heap is stored as one plain list. The item at position i keeps its parent at position (i - 1) / 2 rounded down, and its two children at positions 2i + 1 and 2i + 2. That is why every picture below is a row of numbered boxes.
Min-heap: A heap whose best item is the smallest one. Popping it always hands you the smallest value still inside.
Changing your mind later: The heap lets you provisionally use a ladder and take it back afterwards. You never have to guess ahead of time which climbs deserve a ladder.

3. Visualize the solution

The row of boxes is the backing array of the min-heap holding the climbs currently paid for with ladders

0—

1—

2—

Statusinit

Start at building 0 with 5 bricks and 1 ladder. No climbs have been made yet.

What happens in this step

heights = [4, 2, 7, 6, 9, 14, 12]
bricksLeft = 5, ladders = 1
heap is empty

The step from building 0 (height 4) to building 1 (height 2) goes
downhill, so it is free and nothing is recorded.

Step 1 of 6

Steps to visualize

Each box is one slot of the list that stores the heap. Slot 0 always holds the smallest ladder climb.
A slot showing — is unused. The heap never holds more than ladders + 1 climbs.
Every upward climb goes into the heap first, as if a ladder were free.
If that makes the heap bigger than the number of ladders, pop the smallest climb and pay for it with bricks instead.
When bricks go below zero you have run out, and the answer is the building you were standing on.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

The row of boxes is the backing array of the min-heap holding the climbs currently paid for with ladders

0—

1—

2—

Statusinit

Start at building 0 with 5 bricks and 1 ladder. No climbs have been made yet.

What happens in this step

heights = [4, 2, 7, 6, 9, 14, 12]
bricksLeft = 5, ladders = 1
heap is empty

The step from building 0 (height 4) to building 1 (height 2) goes
downhill, so it is free and nothing is recorded.

Step 1 of 6

5. Solution

Solution

solution.tsTypeScript

function furthestBuilding(heights, bricks, ladders) {
  const ladderJumps = new Heap((a, b) => a - b);
  let bricksLeft = bricks;

  for (let i = 0; i + 1 < heights.length; i++) {
    const climb = heights[i + 1] - heights[i];
    if (climb <= 0) continue;

    ladderJumps.push(climb);

    if (ladderJumps.size() > ladders) {
      bricksLeft -= ladderJumps.pop();
    }

    if (bricksLeft < 0) return i;
  }

  return heights.length - 1;
}

class Heap {
  constructor(compare) {
    this.items = [];
    this.compare = compare;
  }

  size() {
    return this.items.length;
  }

  peek() {
    return this.items[0];
  }

  push(value) {
    this.items.push(value);
    let child = this.items.length - 1;

    while (child > 0) {
      const parent = (child - 1) >> 1;
      if (this.compare(this.items[child], this.items[parent]) >= 0) break;
      const swap = this.items[child];
      this.items[child] = this.items[parent];
      this.items[parent] = swap;
      child = parent;
    }
  }

  pop() {
    const top = this.items[0];
    const last = this.items.pop();

    if (this.items.length > 0) {
      this.items[0] = last;
      let parent = 0;

      while (true) {
        const left = parent * 2 + 1;
        const right = parent * 2 + 2;
        let best = parent;

        if (left < this.items.length && this.compare(this.items[left], this.items[best]) < 0) best = left;
        if (right < this.items.length && this.compare(this.items[right], this.items[best]) < 0) best = right;
        if (best === parent) break;

        const swap = this.items[parent];
        this.items[parent] = this.items[best];
        this.items[best] = swap;
        parent = best;
      }
    }

    return top;
  }
}

Time: O(n log n)
Space: O(n)

6. Test cases

Test cases

Input	Expected	Covers
`heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1`	`4`	example from the docstring
`heights = [4, 12, 2, 7, 3, 18, 20, 3, 19], bricks = 10, ladders = 2`	`7`	larger input where ladders must land on the two biggest climbs
`heights = [14, 3, 19, 3], bricks = 17, ladders = 0`	`3`	no ladders at all, bricks are just enough
`heights = [1, 5, 1, 2, 3, 4, 10000], bricks = 4, ladders = 1`	`5`	the huge final climb cannot be paid for once the ladder is spent
`heights = [1], bricks = 0, ladders = 0`	`0`	smallest input, there is nowhere to move
`heights = [1, 2, 3, 4], bricks = 0, ladders = 0`	`0`	the very first climb is unaffordable

Furthest Building You Can Reach