Skip to main content

1642 - Furthest Building You Can Reach

Difficulty: Medium | Pattern: Greedy + Min-Heap | Company tags: Amazon, Google

Problem Statement​

You are given an integer array heights representing the heights of buildings, some bricks, and some ladders.

You start at building 0 and move to the next building by possibly using bricks or ladders. When moving from building i to building i+1 (0-indexed):

  • If the current building is taller or the same, you can move without resources.
  • If the current building is shorter, you must use either bricks equal to the height difference, or one ladder.

Return the furthest building index you can reach if you use the given ladders and bricks optimally.

Example 1:

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

Example 2:

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

Algorithm Flow​

Approach: Greedy + Min-Heap — O(n log L)​

Key insight: Use ladders on the largest climbs (greedy). Maintain a min-heap of the climbs where we used ladders. When we've used all ladders for a new climb, pop the smallest ladder climb and use bricks for it instead.

import heapq

def furthestBuilding(heights: list[int], bricks: int, ladders: int) -> int:
    heap = []  # min-heap of climbs where we used ladders
    
    for i in range(len(heights) - 1):
        diff = heights[i+1] - heights[i]
        
        if diff <= 0:
            continue  # going down or level: free
        
        # Use a ladder for this climb
        heapq.heappush(heap, diff)
        
        if len(heap) > ladders:
            # We've used too many ladders; take back the smallest ladder use
            smallest = heapq.heappop(heap)
            bricks -= smallest
            if bricks < 0:
                return i  # can't proceed
    
    return len(heights) - 1

Dry Run​

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

idiffheap (ladder climbs)bricks
0-2skip5
15[5]5
2-1skip5
33[3,5] → too many (2>1)pop 3 → bricks=5-3=2
45[5,5] → too manypop 5 → bricks=2-5=-3 → return 4

Output: 4 ✓

Edge Cases​

  • No climbs → return last index
  • ladders = 0 → use only bricks; return when bricks run out
  • All descending → return last index

Complexity​

  • Time: O(n log L) where L = ladders (heap at most L+1 elements)
  • Space: O(L) for heap

Key Terms​

TermDefinition
Min-heapA priority queue that pops the smallest element first; used here to track the smallest ladder-assigned climb.
Greedy exchange argumentJustifies always assigning ladders to the largest climbs, since swapping a ladder from a smaller climb to a larger one never hurts.
Climb (diff)The positive height difference heights[i+1] - heights[i]; the "cost" of moving forward when the next building is taller.
Amortized resource allocationDeciding, at each step, which of two limited resources (bricks vs. ladders) to spend on the current cost.

FAQ​

Q: Why use a min-heap instead of a max-heap? A: We push every climb onto the heap assuming we used a ladder. Once the heap exceeds ladders in size, we must "give back" a ladder and pay bricks instead — we want to give back the cheapest ladder use, which is the minimum, hence a min-heap.

Q: Can this be solved without a heap? A: Yes, using binary search on the answer plus a sliding-window/heap check, but that's O(n log n) with a more complex check — the direct greedy heap approach is simpler and equally optimal.

Q: What if ladders >= n? A: Every climb can use a ladder, bricks are never touched, and the answer is always len(heights) - 1.

Q: What happens if bricks go negative mid-loop? A: We return the current index i immediately, since building i was the last one reached before running out of resources.

Q: How would the approach change if ladders had varying "reach" (fixed height limits)? A: The problem becomes an assignment/matching problem — you'd need to match ladders to specific climbs they can cover, likely via binary search + greedy matching instead of a plain heap.

Quick Revision​

  • Pattern: greedy + min-heap for resource allocation over a sequence of costs.
  • Only positive height differences ("climbs") consume resources; descents and flat moves are free.
  • Assume every climb uses a ladder first; push the climb size onto a min-heap.
  • When heap size exceeds ladders, pop the smallest climb and pay for it with bricks instead.
  • If bricks go negative, the previous index is the furthest reachable building.
  • Time complexity: O(n log L) where L = ladders; space O(L) for the heap.
  • The exchange argument guarantees optimality: swapping a ladder to a bigger climb is never worse.
  • Edge cases: no climbs (return last index), zero ladders (bricks-only), all descending heights.
  • 871 - Minimum Number of Refueling Stops — same greedy + max-heap resource pattern (fuel stops instead of ladders).
  • 215 - Kth Largest Element in an Array — core heap mechanics reused here for tracking extreme values.
  • Pattern match: any "spend limited resource on largest costs" problem (e.g., task scheduling with limited cooldowns) follows the same greedy-heap exchange argument.