Free lesson · DSA Mastery - Interview Prep, End to End

Furthest Building You Can Reach

Medium9 min readdsaheaps

Furthest Building You Can Reach

Furthest Building You Can Reach is a greedy heap problem: you have a fixed number of ladders and a budget of bricks, and as you climb between buildings each upward gap must be covered by either bricks (equal to the gap) or one ladder (any gap). To travel as far as possible, you want to spend your scarce ladders on the largest gaps and bricks on the rest. A min-heap of the gaps where ladders are currently committed lets you, whenever you run short, reclaim the smallest ladder-covered gap and pay for it with bricks instead - a classic "commit greedily, then downgrade the cheapest commitment" use of a heap. We present the binary-search-on-answer baseline and the greedy min-heap (canonical).

The insight: a ladder covers any gap for free, so ladders are most valuable on the biggest gaps. But you don't know a gap is "big" until you've seen later ones. So tentatively assign a ladder to every gap as you encounter it; once all ladders are committed and a new gap appears, look at the smallest gap currently holding a ladder - if the new gap is larger, the ladder is better spent here, so reclaim that smallest ladder-gap and pay for it with bricks. A min-heap of ladder-committed gaps makes "smallest committed gap" an O(log n) query.

The Problem

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

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

If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
If the current building's height is less than the next building's height, you can either use one ladder or (h[i+1] - h[i]) bricks.

Return the furthest building index (0-indexed) 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

Explanation: Gaps going up: 4->7 (need 5), 7->9 (need 2... wait order). Use bricks for small gaps,
the ladder for a large one. Optimal play reaches index 4.

Example 2:

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

Constraints:

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

Approaches Overview

#	Approach	Time	Space	Verdict
1	Binary search the furthest index + greedy check	O(n log² n)	O(n)	Works
2	Min-heap of ladder-committed gaps	O(n log n)	O(ladders)	Canonical

The binary-search approach guesses the furthest reachable index and checks feasibility by greedily assigning ladders to the largest gaps up to that index - monotonic, so binary-searchable. The min-heap approach walks forward once: assign a ladder to each up-gap, and when ladders run out, reclaim the smallest ladder-committed gap to pay with bricks; stop when bricks can't cover it. The heap is the cleaner single-pass solution and the canonical one.

Approach 1: Binary Search on the Answer - Works

The Idea

The set of reachable indices is a prefix: if you can reach index k, you can reach any smaller index. So binary-search the furthest index k. To check reachability of k, collect all up-gaps in [0, k), assign ladders to the ladders largest gaps (free), and sum the remaining gaps as bricks needed; feasible iff that sum <= bricks. Each check sorts or selects the largest gaps.

Logic Flowchart

graph TD
    A["lo=0, hi=n-1"] --> B{"lo < hi?"}
    B -->|Yes| C["mid = (lo+hi+1)/2"]
    C --> D["gaps in [0,mid): ladders cover largest, bricks cover rest"]
    D --> E{"bricks needed <= bricks?"}
    E -->|Yes| F["lo = mid"]
    E -->|No| G["hi = mid - 1"]
    F --> B
    G --> B
    B -->|No| H["return lo"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style G fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows binary search on the furthest index. Each candidate index is checked by assigning ladders to the largest gaps and bricks to the rest, narrowing the range based on whether the brick budget suffices.

Complexity

Time: O(n log² n) - log n binary-search steps, each an O(n log n) feasibility check. Space: O(n).

Approach 2: Min-Heap of Ladder-Committed Gaps - Canonical

The Idea

Walk from building 0 forward. For each up-gap d = h[i+1] - h[i], tentatively cover it with a ladder by pushing d onto a min-heap. If the heap now holds more gaps than you have ladders, the cheapest ladder commitment is wasteful - poll the smallest gap and pay for it with bricks (bricks -= smallest). If bricks ever go negative, you cannot proceed past the previous building - return that index. If you finish the walk, return the last index.

Logic Flowchart

graph TD
    A["minHeap empty; for i in 0..n-2"] --> B["d = h[i+1] - h[i]"]
    B --> C{"d > 0?"}
    C -->|No| A
    C -->|Yes| D["push d onto minHeap (tentatively use a ladder)"]
    D --> E{"heap size > ladders?"}
    E -->|Yes| F["bricks -= minHeap.poll() (pay smallest gap with bricks)"]
    E -->|No| A
    F --> G{"bricks < 0?"}
    G -->|Yes| H["return i (cannot reach i+1)"]
    G -->|No| A
    A --> I["return n - 1"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows the greedy min-heap. Each upward gap tentatively takes a ladder via the heap; when ladders are exceeded, the smallest committed gap is paid with bricks, and the walk stops if bricks go negative.

Code

public static int furthestBuilding(int[] heights, int bricks, int ladders) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>();   // gaps currently using a ladder
    for (int i = 0; i < heights.length - 1; i++) {
        int d = heights[i + 1] - heights[i];
        if (d <= 0) continue;                                 // going down or level: free
        minHeap.offer(d);                                     // tentatively cover with a ladder
        if (minHeap.size() > ladders) {                       // out of ladders
            bricks -= minHeap.poll();                         // downgrade smallest gap to bricks
        }
        if (bricks < 0) return i;                             // can't afford this step
    }
    return heights.length - 1;
}

// Usage:
// furthestBuilding([4,2,7,6,9,14,12], 5, 1) -> 4

This Java code walks the buildings, pushing each upward gap onto a min-heap as a tentative ladder use. When the heap exceeds the ladder count, it pays the smallest gap with bricks, returning the current index if bricks run out.

Step-by-Step Walkthrough

A frame-by-frame trace on heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1:

graph LR
    F0["4→2 down: free. 2→7 gap 5: heap[5], size 1 = ladders, ok"]
    F1["7→6 down: free. 6→9 gap 3: heap[5,3], size 2 > 1 → poll 3, bricks 5-3=2"]
    F2["9→14 gap 5: heap[5,5], size 2 > 1 → poll 5, bricks 2-5 = -3 < 0"]
    F3["bricks negative at i=4 → return 4"]
    F0 --> F1 --> F2 --> F3

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F2 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F3 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough climbs the buildings. The ladder is tentatively used on each gap; the smallest committed gap is paid with bricks when ladders are exceeded, and the brick budget runs out at index four, which is returned.

Result: 4.

Complexity

Time: O(n log n) - each gap costs one heap push/poll. Space: O(ladders) for the heap.

Complexity Comparison

Approach	Time	Space	Key Idea	When to Use
Binary search on answer	O(n log² n)	O(n)	Feasibility is monotonic in index	Alternative framing
Min-heap of ladder-gaps	O(n log n)	O(ladders)	Downgrade the smallest ladder-gap to bricks	Canonical

The heap solves it in a single forward pass, never needing to know the answer in advance: it greedily uses ladders on whatever gaps appear, then retroactively reassigns the smallest ladder-gap to bricks when a better use for the ladder emerges. This "commit, then downgrade the cheapest commitment" pattern is cleaner and faster than the binary-search-plus-recheck framing.

Variations & Follow-ups

Why does committing a ladder to every gap and downgrading the smallest work?

Ladders are most valuable on the largest gaps (a ladder saves you exactly gap bricks), but you can't tell a gap is among the largest until you've seen the later ones. So you optimistically place a ladder on each up-gap as it arrives. Once you've placed more ladders than you own, exactly one commitment must be undone - and you should undo the smallest committed gap, because covering a small gap with bricks is cheaper than covering a large one. The min-heap's top is precisely that smallest committed gap. After downgrading it to bricks, the ladders remain on the largest gaps seen so far. This stays optimal at every step because each downgrade spends the fewest possible bricks.

Why does bricks going negative pinpoint exactly where you get stuck?

When you downgrade the smallest committed gap to bricks and the brick balance drops below zero, it means even after using all ladders on the largest gaps so far, the remaining gaps cost more bricks than you have. Since the algorithm has already made the optimal ladder assignment for everything up to the current step, no better arrangement exists - you genuinely cannot cross the current gap. The last building you successfully reached is index i (the gap was from i to i+1), so returning i is correct. The negative balance is the precise signal that the optimal allocation has been exhausted.

Why is a min-heap correct here rather than a max-heap?

You push gaps that are currently covered by ladders, and when you must give one back, you want to relinquish the least valuable ladder use - the smallest gap, since a ladder on a small gap saves the fewest bricks. A min-heap keeps that smallest committed gap at the top for O(1) peek and O(log n) removal. A max-heap would surface the largest committed gap, which is exactly the one you want to keep on a ladder - the opposite of what you need. The orientation follows directly from "downgrade the cheapest commitment": cheapest = smallest = min-heap top.

How does this "commit then downgrade" pattern generalize?

This is a broadly reusable greedy template: when a scarce premium resource (ladders) can be applied to items of varying benefit, and you process items online without future knowledge, tentatively apply the premium resource to each item, then when the resource is over-subscribed, reclaim it from the item where it helps least (heap top) and fall back to the cheaper resource. It appears in task scheduling (keep the highest-value jobs, drop the lowest), bandwidth or budget allocation, and "maximize coverage with K free passes" problems. The heap maintains the current set of premium-resource commitments so the least valuable one is always instantly available to reclaim.

What about edge cases?

All buildings non-increasing: No up-gaps; you always reach the last index for free.
Ladders ≥ number of up-gaps: Every gap gets a ladder; bricks never spent; reach the end.
Zero ladders: Every up-gap is paid in bricks; the heap immediately overflows (size > 0) and downgrades each gap.
Zero bricks and zero ladders: Stuck at the first up-gap.

Common Interview Pitfalls

Using a max-heap. You must reclaim the smallest ladder-gap; a max-heap gives the largest.
Checking the heap-size condition wrong. Downgrade only when committed gaps exceed ladders (size > ladders).
Returning the wrong index on failure. The gap from i to i+1 failing means you reached i - return i, not i+1.
Counting non-positive gaps. Down or level moves are free; skip them entirely.

Why This Topic Matters

Furthest Building introduces the greedy "commit, then downgrade the cheapest commitment" heap pattern: a min-heap tracks where a scarce resource is currently spent so the least valuable use can be reclaimed online. It teaches that a heap can retroactively optimize earlier choices in a single forward pass, a technique that recurs in scheduling and resource-allocation problems throughout the greedy and interval sections.

The next topic, Single-Threaded CPU, simulates a CPU choosing which queued task to run next: among all tasks that have arrived by the current time, it picks the one with the shortest processing time (ties broken by index). This needs two ordered views - tasks sorted by arrival time to know what has become available, and a min-heap of available tasks ordered by processing time (then index) to pick the next to run. It is a step up from a single heap: a sort feeds availability into a heap that orders by a different key, the standard structure for event-driven scheduling simulations.

Back to DSA Mastery - Interview Prep, End to End