Furthest Building You Can Reach

medium array greedy heap

Problem

You have an array of building heights, plus bricks and ladders. Moving forward you can step down freely, but stepping up by d uses either d bricks or one ladder. Return the furthest index reachable.

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

Output4

Use bricks for jumps of 2 and 3; save ladder for the jump of 5.

heights

bricks

ladders

import heapq

def furthest_building(h, bricks, ladders):
    heap = []
    for i in range(len(h) - 1):
        d = h[i + 1] - h[i]
        if d > 0:
            heapq.heappush(heap, d)
            if len(heap) > ladders:
                bricks -= heapq.heappop(heap)
                if bricks < 0: return i
    return len(h) - 1

function furthestBuilding(h, bricks, ladders) {
  const heap = []; // min-heap of jump sizes
  const push = x => { heap.push(x); heap.sort((a, b) => a - b); };
  for (let i = 0; i < h.length - 1; i++) {
    const d = h[i + 1] - h[i];
    if (d > 0) {
      push(d);
      if (heap.length > ladders) {
        bricks -= heap.shift();
        if (bricks < 0) return i;
      }
    }
  }
  return h.length - 1;
}

class Solution {
    public int furthestBuilding(int[] h, int bricks, int ladders) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int i = 0; i < h.length - 1; i++) {
            int d = h[i + 1] - h[i];
            if (d > 0) {
                pq.offer(d);
                if (pq.size() > ladders) {
                    bricks -= pq.poll();
                    if (bricks < 0) return i;
                }
            }
        }
        return h.length - 1;
    }
}

int furthestBuilding(vector<int>& h, int bricks, int ladders) {
    priority_queue<int, vector<int>, greater<>> pq;
    for (int i = 0; i < (int)h.size() - 1; i++) {
        int d = h[i + 1] - h[i];
        if (d > 0) {
            pq.push(d);
            if ((int)pq.size() > ladders) {
                bricks -= pq.top(); pq.pop();
                if (bricks < 0) return i;
            }
        }
    }
    return h.size() - 1;
}

Explanation

The key realization is that ladders should be saved for the biggest jumps, because a ladder covers any climb for free while bricks are limited. So as we walk forward, we tentatively treat each climb as a ladder, then downgrade the smallest climbs to bricks. A min-heap makes finding that smallest climb easy.

Stepping down or staying level costs nothing, so we only care about positive climbs d = h[i+1] - h[i]. Each positive d goes into the heap as a ladder candidate.

Whenever the heap holds more climbs than we have ladders, one of them can't get a ladder. We pop the smallest climb and pay for it with bricks: bricks -= heappop(heap). Popping the smallest means the remaining (bigger) climbs keep the ladders, which is optimal.

If bricks ever goes negative, we couldn't afford that climb, so the furthest reachable building is the current index i. If we get through the whole loop, we reached the last building, len(h) - 1.

Example: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1. The climbs are 5, 3, and 5. The ladder is held for one of the 5s; bricks pay for the 3 and the other 5 (total 8) which exceeds 5, so we get stuck and the answer is index 4.

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