Time Complexity: $O(2^N)$, where $N$ is the number of buildings. In the worst case, every step is a climb, and we branch twice. Why it fails: With heights.length up to $10^5$, an exponential solution will immediately trigger a Time Limit Exceeded (TLE). We need a solution that is close to linear time.

Core Insight for Furthest Building You Can Reach

The key intuition for LeetCode 1642 is understanding the relative value of the resources. A ladder is infinitely valuable in terms of height capacity; it costs the same (1 unit) to climb a difference of 1 or a difference of 1,000. Bricks, however, are consumed linearly based on height.

To maximize distance, ladders should always be used for the largest climbs encountered, while bricks should be used for the smaller climbs.

However, as we iterate through the array, we do not know if a future climb will be larger than the current one. We cannot make a perfect permanent decision immediately. Instead, we can use a "tentative" greedy approach:

1. Assume we use a ladder for every climb initially.
2. Store the height differences of these climbs in a Min-Heap.
3. The Min-Heap maintains the set of climbs currently "sponsored" by ladders.
4. If we run out of ladders (i.e., the number of climbs exceeds the number of ladders), we must revoke the ladder from the smallest climb in our set (the root of the Min-Heap).
5. We then pay for that smallest climb using bricks.

This strategy enforces the invariant that at any point $i$, the ladders are covering the $L$ largest jumps seen so far, and bricks have paid for the rest.

Visual Description: Imagine a container (the Min-Heap) that can hold exactly $L$ items. As we walk through the buildings, every time we face a climb, we toss the height difference into this container. If the container overflows (size becomes $L+1$), the smallest item "spills out." The item that spills out represents the climb that is no longer worthy of a ladder compared to the others. We must then pay the cost of that spilled item using our bricks. If we cannot afford the bricks, we stop.

Execution Flow

Let's trace heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1.

1. Start at index 0 (height 4). Move to index 1 (height 2).

   • diff = 2 - 4 = -2. No cost.
   • Current Index: 1. Heap: []. Bricks: 5.

2. At index 1 (height 2). Move to index 2 (height 7).

   • diff = 7 - 2 = 5. Climb.
   • Push 5 to Heap. Heap: [5].
   • Heap size (1) is not greater than ladders (1). Continue.
   • Current Index: 2.

3. At index 2 (height 7). Move to index 3 (height 6).

   • diff = 6 - 7 = -1. No cost.
   • Current Index: 3.

4. At index 3 (height 6). Move to index 4 (height 9).

   • diff = 9 - 6 = 3. Climb.
   • Push 3 to Heap. Heap: [3, 5] (conceptually).
   • Heap size (2) > ladders (1).
   • Pop min element 3 from Heap. Heap is now [5]. Ladder stays with the 5-jump.
   • Pay bricks for the popped element: bricks = 5 - 3 = 2.
   • Bricks $\ge 0$, so we proceed.
   • Current Index: 4.

5. At index 4 (height 9). Move to index 5 (height 14).

   • diff = 14 - 9 = 5. Climb.
   • Push 5 to Heap. Heap: [5, 5].
   • Heap size (2) > ladders (1).
   • Pop min element 5.
   • Pay bricks: bricks = 2 - 5 = -3.
   • Bricks < 0. We cannot make this move.

6. Return current index 4.

Proof of Correctness

The correctness relies on the "exchange argument" common in greedy proofs. Suppose there is an optimal solution that reaches index $k$. In this solution, suppose a ladder is used for a climb of height $x$ and bricks are used for a climb of height $y$, where $x < y$.

We could swap these resources: use bricks for $x$ and a ladder for $y$.

• Original cost: 1 ladder + $y$ bricks.
• New cost: 1 ladder + $x$ bricks.

Since $x < y$, the new cost uses fewer bricks to reach the same point. Therefore, to maximize the distance (or minimize brick usage for a fixed distance), ladders must always be assigned to the largest set of climbs. Our Min-Heap approach guarantees that for any set of $K$ climbs encountered, the largest $L$ climbs are covered by ladders and the smallest $K-L$ climbs are covered by bricks.

Reference Implementation

C++ Solution for LeetCode 1642

cpp
#include <vector>
#include <queue>
#include <functional>

using namespace std;

class Solution {
public:
    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
        // Min-heap to store the height differences covered by 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 the next building is taller, we need to use a resource
            if (diff > 0) {
                // Tentatively use a ladder for this climb
                minHeap.push(diff);
                
                // If we have used more ladders than available
                if (minHeap.size() > ladders) {
                    // Remove the ladder from the smallest climb in the heap
                    // and use bricks for that climb instead
                    bricks -= minHeap.top();
                    minHeap.pop();
                }
                
                // If bricks become negative, we can't proceed
                if (bricks < 0) {
                    return i;
                }
            }
        }
        
        // If we complete the loop, we reached the last building
        return heights.size() - 1;
    }
};

Java Solution for LeetCode 1642

java
import java.util.PriorityQueue;

class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        // Min-heap to keep track of the largest jumps encountered so far
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int i = 0; i < heights.length - 1; i++) {
            int diff = heights[i + 1] - heights[i];
            
            if (diff > 0) {
                // Add the current climb to the heap (simulating ladder usage)
                minHeap.add(diff);
                
                // If we exceed the number of ladders, we must pay for the
                // smallest climb in the heap using bricks.
                if (minHeap.size() > ladders) {
                    bricks -= minHeap.poll();
                }
                
                // If we run out of bricks, we cannot move to i + 1
                if (bricks < 0) {
                    return i;
                }
            }
        }
        
        return heights.length - 1;
    }
}

Python Solution for LeetCode 1642

python
import heapq

class Solution:
    def furthestBuilding(self, heights: list[int], bricks: int, ladders: int) -> int:
        min_heap = []  # Stores the climbs we are currently using ladders for
        
        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
            
            if diff > 0:
                # Push current climb to heap
                heapq.heappush(min_heap, diff)
                
                # If we have more climbs in heap than ladders available
                if len(min_heap) > ladders:
                    # Pop the smallest climb; this one must be paid with bricks
                    smallest_climb = heapq.heappop(min_heap)
                    bricks -= smallest_climb
                
                # If bricks drop below zero, we can't reach i + 1
                if bricks < 0:
                    return i
                    
        return len(heights) - 1