Furthest Building You Can Reach: Greedy Heap Pattern

You are given an array of building heights, a number of bricks, and a number of ladders. Starting at building 0, you move to the next building at each step. If the next building is taller, you must use either bricks (equal to the height difference) or one ladder (covers any height difference). If the next building is the same height or shorter, you move for free. Return the index of the furthest building you can reach.

This is LeetCode 1642: Furthest Building You Can Reach, a medium problem that beautifully demonstrates how a min-heap can make greedy resource allocation decisions in a single pass.

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

Why this problem matters

This problem is a clean example of the greedy-with-heap pattern. You have two types of resources (bricks and ladders) and you need to decide how to allocate them optimally. The naive approach of trying every combination of brick and ladder assignments leads to exponential time. The greedy insight, using a min-heap to retroactively assign ladders to the largest jumps, brings it down to O(n log n).

The same pattern of "allocate the best resource to the biggest need" shows up across scheduling problems, task assignment problems, and other optimization questions. If you internalize the heap-based greedy strategy here, you can apply it broadly.

The key insight

Ladders are more valuable than bricks because a ladder covers any height difference, no matter how large, while bricks are consumed proportionally. So you want to use ladders for the largest jumps and bricks for the smallest ones.

The problem is that you do not know which jumps are "the largest" until you have seen them all. You might use a ladder on a jump of 5, only to find a jump of 50 later. The key insight is to defer the decision. Use a min-heap to track the jumps where you have assigned ladders. When you run out of ladders (heap size exceeds the number of ladders), pop the smallest jump from the heap and pay for it with bricks instead. This retroactively reassigns the ladder from the smallest jump to the current one.

At every point, the heap contains exactly the largest jumps you have seen so far, and those are the ones covered by ladders. Everything else is paid for with bricks. This is the optimal allocation.

The solution

import heapq

def furthest_building(heights, bricks, ladders):
    heap = []

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

        if diff <= 0:
            continue

        heapq.heappush(heap, diff)

        if len(heap) > ladders:
            smallest = heapq.heappop(heap)
            bricks -= smallest
            if bricks < 0:
                return i

    return len(heights) - 1

Here is what each part does:

1. Walk through buildings left to right. For each pair of adjacent buildings, compute the height difference.
2. If the next building is shorter or the same height, move for free. Skip it.
3. If the next building is taller, push the difference onto the min-heap. Optimistically assume you will use a ladder.
4. If the heap grows larger than the number of ladders, you have assigned too many. Pop the smallest difference from the heap and pay for that jump with bricks instead.
5. If bricks goes negative, you cannot afford the move. Return the current index.
6. If you make it through all buildings, return the last index.

Visual walkthrough

Let's trace through heights = [4, 2, 7, 6, 9, 14, 12] with bricks = 5 and ladders = 1. At each upward jump, we push the difference onto the min-heap. If the heap exceeds the ladder count, we pop the smallest and spend bricks.

Notice how the ladder always ends up covering the largest jump. When we jumped from 2 to 7 (difference 5), we used the ladder. When we later jumped from 6 to 9 (difference 3), the heap had two entries: [3, 5]. Since we only have one ladder, we popped 3 and spent bricks on it. The ladder stayed assigned to the jump of 5. When the jump of 5 from 9 to 14 came along, it tied for largest and the same logic applied.

Complexity analysis

If the number of ladders is small relative to n, the heap stays small and operations are closer to O(log ladders). In practice, this is very fast.

The building blocks

Min-heap for greedy resource allocation

The core building block here is using a min-heap to track the "best" assignments and retroactively swap out the worst one when resources are tight. The pattern looks like this:

import heapq

heap = []
for cost in costs:
    heapq.heappush(heap, cost)
    if len(heap) > budget:
        cheapest = heapq.heappop(heap)
        spend(cheapest)

The heap always holds the top-k largest values (where k is your budget). When a new value arrives, it competes for a spot. If the new value is larger than the current minimum in the heap, it displaces it. This is the same pattern used in Kth Largest Element in an Array, where the heap maintains the k largest elements and the root is the kth largest.

Greedy forward scan with deferred decisions

Instead of deciding upfront whether to use bricks or a ladder at each jump, you defer the decision. Push every jump onto the heap optimistically, then fix the allocation when the heap overflows. This "decide later" pattern avoids the exponential blowup of trying all combinations.

for i in range(n - 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

The deferred decision approach works whenever you have a limited "premium" resource (ladders) and a limited "basic" resource (bricks), and the optimal strategy is to assign the premium resource to the largest costs.

Edge cases

• All downhill: heights = [5, 4, 3, 2, 1]. Every move is free. Return the last index.
• Zero bricks and zero ladders: You can only move to buildings that are the same height or shorter.
• Enough ladders for everything: If you have as many ladders as there are upward jumps, you never need bricks. Return the last index.
• Single building: heights = [10]. You are already at the only building. Return 0.
• All same height: heights = [5, 5, 5, 5]. Every move is free. Return the last index.
• Ties in height differences: The min-heap handles ties naturally. If two jumps have the same difference, it does not matter which one gets the ladder.

From understanding to recall

The logic behind the greedy heap approach is intuitive once you see it: ladders go to the biggest jumps, bricks go to the smallest ones, and the min-heap handles the bookkeeping. But writing it from memory under interview pressure is a different challenge.

The details that trip people up: pushing the difference (not the height), checking heap size against ladders (not bricks), popping the smallest (not the largest), and returning the current index i (not i + 1) when bricks run out. These are small things, but they matter.

Spaced repetition turns understanding into recall. You write the solution from scratch today, again tomorrow, then in three days. After a few rounds, the heap push, size check, pop, brick subtraction sequence becomes automatic. You do not have to rederive it. You just write it.

CodeBricks breaks this problem into its heap-allocation and greedy-scan building blocks, then drills them independently with spaced repetition. Each piece reinforces a reusable pattern that transfers to other problems.

Related posts

• Jump Game - Another greedy forward-scan problem where you track a running state across an array
• Koko Eating Bananas - A different optimization strategy (binary search on the answer) for resource allocation
• Kth Largest Element in an Array - Uses the same min-heap-of-size-k building block to maintain the top k values

CodeBricks breaks down problems like Furthest Building You Can Reach into their core building blocks and drills them with spaced repetition. Instead of memorizing solutions, you practice the patterns until they are second nature. When a greedy heap problem shows up in your interview, you do not have to think about it. You just write it.