Furthest Building You Can Reach

LeetCode 1642: Furthest Building You Can Reach Solution & Explanation

Problem Overview

TL;DR: The optimal solution uses a Min-Heap to track the largest height differences encountered so far, ensuring that limited ladders are allocated to the steepest climbs while bricks cover the smaller remaining jumps.

In the LeetCode 1642 problem, "Furthest Building You Can Reach," you are tasked with navigating an array of building heights. Moving from a taller building to a shorter one is free. However, moving from a shorter building to a taller one requires resources: either one ladder (which covers any height difference) or a number of bricks equal to the height difference. Given a finite supply of bricks and ladders, the goal is to determine the maximum index (furthest building) reachable starting from index 0.

This is a popular interview question that tests your ability to make optimal resource allocation decisions using greedy strategies and priority queues.

Brute Force Approach for Furthest Building You Can Reach

The naive approach involves exploring every possible decision at each step. When encountering a climb (where the next building is taller), we branch into two possibilities: using a ladder or using bricks. This effectively creates a decision tree where we traverse every valid path until resources are exhausted, returning the maximum depth reached.

Pseudo-code:

function solve(index, bricks, ladders):
    if index is last building: return index
    diff = heights[index+1] - heights[index]
    if diff <= 0:
        return solve(index + 1, bricks, ladders)
    
    res = index
    if ladders > 0:
        res = max(res, solve(index + 1, bricks, ladders - 1))
    if bricks >= diff:
        res = max(res, solve(index + 1, bricks - diff, ladders))
        
    return res

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.

Algorithm Strategy: Heap (Priority Queue) Patterns

1. Initialize a Min-Heap: This will store the height differences of the climbs we have conceptually allocated ladders to.
2. Iterate through heights: Traverse from index 0 to $N-1$.
3. Calculate Difference: For each step $i$ to $i+1$, calculate diff = heights[i+1] - heights[i].
4. Handle Descent: If diff <= 0, proceed to the next building without cost.
5. Handle Climb:
   • Push diff onto the Min-Heap.
   • If the size of the Min-Heap exceeds the number of available ladders:
     • Pop the smallest element from the heap. This is the smallest climb among the ones we tried to use ladders for.
     • Subtract this popped value from bricks.
     • Check if bricks < 0. If true, we cannot proceed further; return the current index $i$.
6. Completion: If the loop finishes, we have reached the end of the array. Return $N-1$.

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.

Pattern Reuse Notes

The Heap - Scheduling / Minimum Cost pattern is versatile. Understanding how to maintain a "Top K" set or dynamically retrieve the minimum/maximum element is crucial for these problems:

• LeetCode 253: Meeting Rooms II: Uses a Min-Heap to track the end times of meetings. The heap size represents the number of rooms required.
• LeetCode 767: Reorganize String: Uses a Max-Heap (based on character frequency) to greedily place the most frequent characters first, ensuring no two adjacent characters are the same.
• LeetCode 857: Minimum Cost to Hire K Workers: Uses a Max-Heap to maintain the $K$ workers with the smallest quality values to minimize the total wage bill.
• LeetCode 1792: Maximum Average Pass Ratio: Uses a Max-Heap to greedily assign extra students to the class that yields the highest increase in pass ratio.

Reference Implementation

C++ Solution for LeetCode 1642

1#include <vector>
2#include <queue>
3#include <functional>
4
5using namespace std;
6
7class Solution {
8public:
9    int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
10        // Min-heap to store the height differences covered by ladders
11        priority_queue<int, vector<int>, greater<int>> minHeap;
12        
13        for (int i = 0; i < heights.size() - 1; ++i) {
14            int diff = heights[i + 1] - heights[i];
15            
16            // If the next building is taller, we need to use a resource
17            if (diff > 0) {
18                // Tentatively use a ladder for this climb
19                minHeap.push(diff);
20                
21                // If we have used more ladders than available
22                if (minHeap.size() > ladders) {
23                    // Remove the ladder from the smallest climb in the heap
24                    // and use bricks for that climb instead
25                    bricks -= minHeap.top();
26                    minHeap.pop();
27                }
28                
29                // If bricks become negative, we can't proceed
30                if (bricks < 0) {
31                    return i;
32                }
33            }
34        }
35        
36        // If we complete the loop, we reached the last building
37        return heights.size() - 1;
38    }
39};

Java Solution for LeetCode 1642

1import java.util.PriorityQueue;
2
3class Solution {
4    public int furthestBuilding(int[] heights, int bricks, int ladders) {
5        // Min-heap to keep track of the largest jumps encountered so far
6        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
7        
8        for (int i = 0; i < heights.length - 1; i++) {
9            int diff = heights[i + 1] - heights[i];
10            
11            if (diff > 0) {
12                // Add the current climb to the heap (simulating ladder usage)
13                minHeap.add(diff);
14                
15                // If we exceed the number of ladders, we must pay for the
16                // smallest climb in the heap using bricks.
17                if (minHeap.size() > ladders) {
18                    bricks -= minHeap.poll();
19                }
20                
21                // If we run out of bricks, we cannot move to i + 1
22                if (bricks < 0) {
23                    return i;
24                }
25            }
26        }
27        
28        return heights.length - 1;
29    }
30}

Python Solution for LeetCode 1642

1import heapq
2
3class Solution:
4    def furthestBuilding(self, heights: list[int], bricks: int, ladders: int) -> int:
5        min_heap = []  # Stores the climbs we are currently using ladders for
6        
7        for i in range(len(heights) - 1):
8            diff = heights[i + 1] - heights[i]
9            
10            if diff > 0:
11                # Push current climb to heap
12                heapq.heappush(min_heap, diff)
13                
14                # If we have more climbs in heap than ladders available
15                if len(min_heap) > ladders:
16                    # Pop the smallest climb; this one must be paid with bricks
17                    smallest_climb = heapq.heappop(min_heap)
18                    bricks -= smallest_climb
19                
20                # If bricks drop below zero, we can't reach i + 1
21                if bricks < 0:
22                    return i
23                    
24        return len(heights) - 1