LeetCode 1642 - Furthest Building You Can Reach

LeetCode Problem 1642

Difficulty: 🟡 Medium
Topics: Array, Greedy, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us an array heights, where each value represents the height of a building. You start at building 0 and attempt to move sequentially to the right, one building at a time.

When moving from building i to building i+1, there are two possibilities:

• If the next building is shorter or the same height, you can move for free.

• If the next building is taller, you must compensate for the height difference using either:

• bricks equal to the difference in height, or

• exactly one ladder.

The goal is to determine the furthest building index you can reach if you use your resources optimally.

The important detail is that ladders can cover climbs of any size, while bricks are consumed proportionally to the climb height. Because of this, ladders are usually more valuable on large climbs, while bricks are better spent on smaller climbs.

The constraints are large:

• heights.length can be up to 100000
• heights can be as large as 10^6
• bricks can be as large as 10^9

These constraints immediately rule out exponential or quadratic exploration approaches. We need an algorithm that is close to linear time.

Several edge cases are important:

• All buildings may already be descending, meaning no resources are needed.
• There may be zero ladders.
• There may be zero bricks.
• A single climb may exceed the available bricks.
• Ladders may need to be reassigned dynamically to larger climbs encountered later.
• The optimal decision at one step may depend on future climbs.

A naive greedy strategy such as “always use bricks first” or “always use ladders first” does not always work.

Approaches

Brute Force Approach

A brute force solution would explore every possible choice whenever we encounter an upward climb. For each positive height difference, we could either:

• spend bricks, if enough are available, or
• spend a ladder, if one remains.

This creates a branching decision tree. At each climb, there can be up to two choices, so the total number of possibilities grows exponentially.

For example, if there are k upward climbs, the number of possible resource allocation combinations can approach 2^k.

This approach is correct because it explores every valid allocation strategy and chooses the furthest reachable building among them. However, it is far too slow for 100000 buildings.

Key Insight

The critical observation is that ladders should be reserved for the largest climbs.

Suppose we used bricks on a very large climb and later used a ladder on a smaller climb. Swapping those choices would always save bricks or keep the same total cost.

This means the optimal strategy is:

• use bricks for smaller climbs,
• use ladders for larger climbs.

The challenge is that we do not know future climbs ahead of time.

To solve this, we process buildings from left to right while maintaining all upward climbs encountered so far in a min-heap.

The idea is:

• temporarily assume every upward climb uses a ladder,
• if the number of climbs exceeds the number of ladders available, remove the smallest climb from the heap and pay for it using bricks instead.

This guarantees that ladders are always assigned to the largest climbs seen so far.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Explores every possible resource allocation
Optimal Heap Greedy	O(n log n)	O(l)	Uses ladders on largest climbs dynamically

Algorithm Walkthrough

1. Initialize a min-heap to store all positive climbs encountered so far.

The heap helps us efficiently track the smallest climb currently assigned a ladder. 2. Iterate through the buildings from left to right.

For each pair of adjacent buildings, compute:

climb = heights[i+1] - heights[i]

3. If climb <= 0, continue to the next building.

No resources are needed because the next building is not taller. 4. If climb > 0, push the climb value into the min-heap.

Conceptually, we are temporarily assigning a ladder to this climb. 5. After inserting the climb, check whether the heap size exceeds the number of ladders.

If it does, we have assigned more climbs to ladders than allowed. 6. Remove the smallest climb from the heap.

This smallest climb is the cheapest one to pay with bricks instead of a ladder. 7. Subtract that smallest climb from the available bricks.

This step reallocates ladders toward larger climbs. 8. If bricks become negative, return the current building index.

This means we cannot complete the jump to the next building. 9. If we finish the loop successfully, return the last building index.

Why it works

The algorithm maintains the invariant that the heap always contains the climbs currently assigned ladders, and these are the largest climbs encountered so far.

Whenever the number of climbs exceeds the number of ladders, the smallest climb is converted from ladder usage to brick usage. Since ladders provide the greatest benefit on large climbs, this greedy reassignment is always optimal.

Because every decision preserves the best possible ladder allocation among all previously seen climbs, the algorithm correctly computes the furthest reachable building.

Python Solution

from typing import List
import heapq

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        min_heap = []

        for i in range(len(heights) - 1):
            climb = heights[i + 1] - heights[i]

            if climb <= 0:
                continue

            heapq.heappush(min_heap, climb)

            if len(min_heap) > ladders:
                bricks -= heapq.heappop(min_heap)

            if bricks < 0:
                return i

        return len(heights) - 1

The implementation follows the greedy heap strategy directly.

The min_heap stores every positive climb encountered so far. Each insertion represents temporarily assigning a ladder to that climb.

When the heap size exceeds the available number of ladders, we remove the smallest climb and pay for it using bricks. This ensures ladders remain reserved for larger climbs.

The condition bricks < 0 indicates that we do not have enough bricks to complete the current transition, so the current index is returned immediately.

If the loop finishes, every transition was successful, meaning we can reach the final building.

Go Solution

package main

import (
	"container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i] < h[j]
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	value := old[n-1]
	*h = old[:n-1]
	return value
}

func furthestBuilding(heights []int, bricks int, ladders int) int {
	minHeap := &MinHeap{}
	heap.Init(minHeap)

	for i := 0; i < len(heights)-1; i++ {
		climb := heights[i+1] - heights[i]

		if climb <= 0 {
			continue
		}

		heap.Push(minHeap, climb)

		if minHeap.Len() > ladders {
			bricks -= heap.Pop(minHeap).(int)
		}

		if bricks < 0 {
			return i
		}
	}

	return len(heights) - 1
}

The Go version uses the container/heap package to implement a min-heap.

Unlike Python, Go does not provide a built-in priority queue abstraction, so we define a custom MinHeap type implementing the required heap interface methods.

The algorithm itself is identical to the Python version. Integer overflow is not a concern because the constraints fit safely within Go's int range on LeetCode environments.

Worked Examples

Example 1

Input:

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

Step	Transition	Climb	Heap	Bricks	Action
0	4 → 2	-2	[]	5	Free move
1	2 → 7	5	[5]	5	Assign ladder
2	7 → 6	-1	[5]	5	Free move
3	6 → 9	3	[3,5]	5	Too many ladder assignments
3	Rebalance	-	[5]	2	Use bricks for climb 3
4	9 → 14	5	[5,5]	2	Too many ladder assignments
4	Rebalance	-	[5]	-3	Use bricks for climb 5

At this point bricks become negative, so we return index 4.

Output:

4

Example 2

Input:

heights = [4,12,2,7,3,18,20,3,19]
bricks = 10
ladders = 2

Step	Transition	Climb	Heap	Bricks
0	4 → 12	8	[8]	10
1	12 → 2	-10	[8]	10
2	2 → 7	5	[5,8]	10
3	7 → 3	-4	[5,8]	10
4	3 → 18	15	[5,8,15]	10
4	Rebalance	-	[8,15]	5
5	18 → 20	2	[2,15,8]	5
5	Rebalance	-	[8,15]	3
6	20 → 3	-17	[8,15]	3
7	3 → 19	16	[8,15,16]	3
7	Rebalance	-	[15,16]	-5

Bricks become negative while trying to leave building 7, so the answer is 7.

Example 3

Input:

heights = [14,3,19,3]
bricks = 17
ladders = 0

Step	Transition	Climb	Heap	Bricks
0	14 → 3	-11	[]	17
1	3 → 19	16	[16]	17
1	Rebalance	-	[]	1
2	19 → 3	-16	[]	1

All buildings are reachable.

Output:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each climb may be inserted and removed from the heap
Space	O(l)	Heap stores at most ladders + 1 climbs

The loop processes each building transition exactly once. Each positive climb is pushed into the heap, and occasionally popped out. Heap operations cost O(log n) in the worst case.

The heap never grows much larger than the number of ladders, so the practical space usage is small.

Test Cases

from typing import List
import heapq

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        min_heap = []

        for i in range(len(heights) - 1):
            climb = heights[i + 1] - heights[i]

            if climb > 0:
                heapq.heappush(min_heap, climb)

                if len(min_heap) > ladders:
                    bricks -= heapq.heappop(min_heap)

                if bricks < 0:
                    return i

        return len(heights) - 1

sol = Solution()

assert sol.furthestBuilding([4,2,7,6,9,14,12], 5, 1) == 4  # Example 1
assert sol.furthestBuilding([4,12,2,7,3,18,20,3,19], 10, 2) == 7  # Example 2
assert sol.furthestBuilding([14,3,19,3], 17, 0) == 3  # Example 3

assert sol.furthestBuilding([1,2,3,4], 0, 3) == 3  # Ladders cover all climbs
assert sol.furthestBuilding([4,3,2,1], 0, 0) == 3  # Descending only
assert sol.furthestBuilding([1,5], 3, 0) == 0  # Not enough bricks
assert sol.furthestBuilding([1,5], 4, 0) == 1  # Exact brick usage
assert sol.furthestBuilding([1,10,20], 5, 1) == 1  # Ladder used optimally
assert sol.furthestBuilding([1], 0, 0) == 0  # Single building
assert sol.furthestBuilding([1,2,1000], 1, 1) == 2  # Ladder saved for large climb
assert sol.furthestBuilding([1,3,6,10], 3, 1) == 2  # Heap reassignment needed

Test Summary

Test	Why
[4,2,7,6,9,14,12]	Validates sample behavior
[4,12,2,7,3,18,20,3,19]	Tests multiple reallocations
[14,3,19,3]	Tests no ladders
[1,2,3,4]	Tests ladders covering all climbs
[4,3,2,1]	Tests descending sequence
[1,5] with insufficient bricks	Tests early failure
[1,5] with exact bricks	Tests exact resource exhaustion
[1,10,20]	Tests ladder allocation decisions
[1]	Tests minimum input size
[1,2,1000]	Tests optimal ladder reservation
[1,3,6,10]	Tests heap rebalancing

Edge Cases

One important edge case occurs when all buildings are descending or equal in height. In this situation, no bricks or ladders are ever needed. A buggy implementation might unnecessarily consume resources or mishandle zero climbs. This implementation correctly skips all non-positive climbs with the condition climb <= 0.

Another critical edge case is when there are zero ladders. In that case, every upward climb must be paid entirely with bricks. The heap still works correctly because every insertion immediately causes a pop, converting all climbs into brick usage.

A subtle edge case involves dynamically reassigning ladders. Suppose we initially use bricks on a medium climb and later encounter a much larger climb. A naive implementation that commits permanently to earlier choices may fail. This solution avoids that problem by always storing climbs in the heap and retroactively converting the smallest ladder-assigned climb into brick usage when necessary.

A final edge case occurs when bricks become exactly zero after a climb. The algorithm should still allow progress because resources were sufficient. The implementation only stops when bricks < 0, which correctly distinguishes exhaustion from insufficiency.