Medium
ArrayGreedyHeap (Priority Queue)
Updated Sep 2026

Furthest Building You Can Reach

Asked at DE Shaw

Problem

Furthest Building You Can Reach walks you along buildings of varying height. Going down is free; each climb costs either that many bricks or one ladder. How far can you get? The greedy insight: ladders are most valuable on the biggest climbs, so use a heap to decide retroactively which climbs get ladders.

Asked At

CompanyDifficulty
DE ShawMediumView all DE Shaw questions →

How to Think About It

1.

A ladder covers any climb, so it should be spent on the largest climbs; bricks should cover the smaller ones.

2.

You do not know the largest climbs in advance — but you can decide retroactively. Tentatively give every climb a ladder, keeping the climbs in a min-heap.

3.

Key insight: once the heap holds more climbs than you have ladders, the smallest climb in the heap should be paid with bricks instead. Pop it and subtract from bricks.

4.

If bricks go negative, you cannot reach the current building — return the previous index.

5.

Walkthrough: heights [4,2,7,6,9,14,12], bricks 5, ladders 1. Climbs: 2->7 (5), 6->9 (3), 9->14 (5). After the second climb the heap [3,5] exceeds 1 ladder -> pay 3 bricks (2 left). At 9->14 the heap [5,5] -> pay 5, bricks -3 -> stop at index 4.

Optimal Approach

Step 1: heap = [].
Step 2: For i from 0 to n - 2:
climb = heights[i+1] - heights[i]; if climb <= 0, continue.
Push climb.
If len(heap) > ladders: bricks -= pop().
If bricks < 0: return i.
Step 3: Return n - 1.

Time: O(n log L) where L is the number of ladders. Space: O(L).

What Trips People Up in Real Interviews

1.

Using bricks first and ladders only when bricks run out. That wastes bricks on big climbs.

2.

Trying all combinations with DP — the state space is too large.

3.

Returning i + 1 when bricks go negative. You are stuck at building i.

4.

Pushing descents or flat steps onto the heap. They cost nothing.

Solution Code

import heapq

def furthestBuilding(heights, bricks, ladders):
    heap = []
    for i in range(len(heights) - 1):
        climb = heights[i + 1] - heights[i]
        if climb <= 0:
            continue
        heapq.heappush(heap, climb)
        if len(heap) > ladders:
            bricks -= heapq.heappop(heap)
        if bricks < 0:
            return i
    return len(heights) - 1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Furthest Building You Can Reach problem?

Furthest Building You Can Reach walks you along buildings of varying height. Going down is free; each climb costs either that many bricks or one ladder. How far can you get? The greedy insight: ladders are most valuable on the biggest climbs, so use a heap to decide retroactively which climbs get ladders.

How do you solve Furthest Building You Can Reach?

The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.

What companies ask Furthest Building You Can Reach?

Furthest Building You Can Reach is asked at DE Shaw. It is a medium difficulty problem.

What are common mistakes on Furthest Building You Can Reach?
  • Using bricks first and ladders only when bricks run out. That wastes bricks on big climbs.
  • Trying all combinations with DP — the state space is too large.
  • Returning `i + 1` when bricks go negative. You are stuck at building `i`.
  • Pushing descents or flat steps onto the heap. They cost nothing.