MediumArrayGreedyHeapUpdated Sep 2026

1642. Furthest Building You Can Reach

Asked at DE Shaw

Difficulty

Medium

Time

O(n log L)

Space

O(L)

Pattern

Array

Companies

1

Problem

You are given an array heights, where heights[i] is the height of building i. You start on building 0 and want to walk as far right as possible. You also have bricks bricks and ladders ladders.

Moving from building i to building i+1 is free when the next building is not taller than the current one. When the next building is taller, you must pay for the climb: either spend heights[i+1] - heights[i] bricks, or spend one ladder (a ladder covers a climb of any size).

Return the index of the furthest building you can reach. You may choose how to spend bricks and ladders in any way that helps you. If you can reach the last building, return len(heights) - 1.

Free drops, paid climbs

heightsfreefree4276914120123456Orange buildings are taller than the one before them, sothose steps cost bricks or a ladder.
Going down costs nothing. Each upward step must be paid with bricks equal to the height gap, or with one ladder.

Constraints

  • ●1 <= heights.length <= 10^5
  • ●1 <= heights[i] <= 10^6
  • ●0 <= bricks <= 10^9
  • ●0 <= ladders <= heights.length

Examples

Example 1
Inputheights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output4
WhyThe climbs are 2→7 (cost 5), 6→9 (cost 3) and 9→14 (cost 5). You have only 5 bricks and 1 ladder. Pay 5 bricks for the first climb, use the ladder on the 6→9 climb, and you have nothing left for 9→14. So building 4 is the last one you reach.
Example 2
Inputheights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output7
WhyWith 2 ladders you can cover two big climbs for free, and 10 bricks are enough for the rest up to building 7. The climb from 3 to 19 after that is too expensive, so you stop at index 7.
Example 3
Inputheights = [14,3,19,3], bricks = 17, ladders = 0
Output3
WhyWith no ladders every climb must be paid in bricks. The only climb is 3→19, which costs 16 bricks — you have 17, so you reach the last building.

Asked At

1 companies
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).

Ladders go to the biggest climbs

climbs535012iThe three climbs in order: 2→7 costs 5, 6→9 costs 3,9→14 costs 5.min-heap35frontbackAfter the second climb the heap holds [3,5], which ismore climbs than the 1 ladder we own.pop 3 → bricks = 5 − 3 = 2next climb 5 → pop 5 → bricks = −3 < 0return index 4
Give every climb a ladder first, then push the smallest climb out of the heap and pay it with bricks.
ComplexityTime O(n log L)Space O(L)n is the number of buildings and L is the number of ladders; each climb costs one heap push/pop, and the heap never holds more than L+1 climbs.

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

O(n log L) time
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 runs in O(n log L) time and O(L) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

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.