Problem Description

You are given an array heights where heights[i] represents the height of the i-th building. Starting from building 0, you want to reach as far as possible to the right (i.e., a higher index).

You are also given bricks (an integer) and ladders (an integer). To move from building i to i+1:

• If heights[i+1] <= heights[i], you can move freely.
• If heights[i+1] > heights[i], you must climb up. You can:
  • Use bricks equal to heights[i+1] - heights[i].
  • Use one ladder (regardless of the difference in height).

Thought Process

At first glance, it seems we could try every possible combination of using bricks and ladders for each climb. However, this brute-force approach quickly becomes impractical as the number of buildings increases.

Instead, we realize that ladders are "stronger" than bricks because they can cover any height difference at no brick cost. Therefore, we should try to use ladders for the largest jumps and bricks for smaller ones.

This leads to the idea of keeping track of all upward jumps and always assigning ladders to the biggest ones. If we run out of ladders, we use bricks for the smaller jumps. If we run out of bricks, we stop.

Solution Approach

We can efficiently solve this problem using a min-heap (priority queue):

1. Iterate through each pair of consecutive buildings.
2. For each upward climb (where heights[i+1] > heights[i]), record the climb height difference in a min-heap.
3. If the number of climbs exceeds the available ladders, use bricks for the smallest climbs (by popping from the min-heap).
4. If at any point the total bricks used exceeds the available bricks, return the current building index as the furthest reachable.
5. If we finish the loop, we can reach the last building.

• We use a min-heap because we want to always use bricks for the smallest climbs, saving ladders for the biggest jumps.
• This approach ensures we use our limited resources in the most optimal way possible.

Example Walkthrough

Example:
heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1

• Building 0 → 1: Drop (4→2), no resources needed.
• Building 1 → 2: Up (2→7), diff = 5. Add 5 to min-heap.
• Building 2 → 3: Drop (7→6), no resources.
• Building 3 → 4: Up (6→9), diff = 3. Add 3 to min-heap.
• Building 4 → 5: Up (9→14), diff = 5. Add 5 to min-heap.
• Building 5 → 6: Drop (14→12), no resources.

• After 2→3, heap=[5]
• After 3→4, heap=[3,5]. Heap size > ladders, so use bricks for 3 (bricks left: 2).
• After 4→5, heap=[5,5]. Heap size > ladders, so use bricks for 5 (bricks left: -3).

Time and Space Complexity

Brute-force: Would try all possible ways to assign bricks/ladders, leading to exponential time complexity, which is infeasible.

Optimized Approach:

• Time Complexity: O(N log N), where N is the number of buildings. Each upward climb is pushed to the heap, and popping from the heap is log N.
• Space Complexity: O(N) for the heap, in the worst case where all climbs are upward.

Summary

The key insight is to use ladders for the largest climbs and bricks for the smallest. By maintaining a min-heap of upward climbs, we can always assign resources optimally. This approach ensures we reach the furthest building possible with the given bricks and ladders, and does so efficiently.

Code Implementation

import heapq

class Solution:
    def furthestBuilding(self, heights, bricks, ladders):
        heap = []
        for i in range(len(heights) - 1):
            diff = heights[i+1] - heights[i]
            if diff > 0:
                heapq.heappush(heap, diff)
            if len(heap) > ladders:
                bricks -= heapq.heappop(heap)
            if bricks < 0:
                return i
        return len(heights) - 1
      

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (int i = 0; i < heights.size() - 1; ++i) {
            int diff = heights[i+1] - heights[i];
            if (diff > 0) {
                minHeap.push(diff);
            }
            if (minHeap.size() > ladders) {
                bricks -= minHeap.top();
                minHeap.pop();
            }
            if (bricks < 0) {
                return i;
            }
        }
        return heights.size() - 1;
    }
};
      

import java.util.PriorityQueue;

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

class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(val) {
        this.heap.push(val);
        this._siftUp();
    }
    pop() {
        if (this.heap.length === 1) return this.heap.pop();
        const top = this.heap[0];
        this.heap[0] = this.heap.pop();
        this._siftDown();
        return top;
    }
    size() {
        return this.heap.length;
    }
    _siftUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            let parent = Math.floor((idx - 1) / 2);
            if (this.heap[parent] <= this.heap[idx]) break;
            [this.heap[parent], this.heap[idx]] = [this.heap[idx], this.heap[parent]];
            idx = parent;
        }
    }
    _siftDown() {
        let idx = 0;
        const length = this.heap.length;
        while (true) {
            let left = 2 * idx + 1;
            let right = 2 * idx + 2;
            let smallest = idx;
            if (left < length && this.heap[left] < this.heap[smallest]) smallest = left;
            if (right < length && this.heap[right] < this.heap[smallest]) smallest = right;
            if (smallest === idx) break;
            [this.heap[smallest], this.heap[idx]] = [this.heap[idx], this.heap[smallest]];
            idx = smallest;
        }
    }
}

var furthestBuilding = function(heights, bricks, ladders) {
    const heap = new MinHeap();
    for (let i = 0; i < heights.length - 1; i++) {
        let diff = heights[i+1] - heights[i];
        if (diff > 0) heap.push(diff);
        if (heap.size() > ladders) bricks -= heap.pop();
        if (bricks < 0) return i;
    }
    return heights.length - 1;
};