Furthest Building You Can Reach Solution

Problem

You start at building 0 in a row of buildings. Moving to the next building is free when it is the same height or shorter. When the next building is taller, you must either spend bricks equal to the height difference or use one ladder (which covers any height difference). Given a fixed number of bricks and ladders, find the index of the furthest building you can reach.

Input: heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1
Output: 4
Explanation: Building 0→1 is a descent (free). Building 1→2 climbs 5 — use the ladder. Building 3→4 climbs 3 — use 3 bricks (2 left). Building 4→5 would need 5 bricks but only 2 remain, so we stop at building 4.

Intuition

Ladders should cover the largest gaps, since a ladder costs the same regardless of height difference while bricks are spent proportionally. The challenge is that future gaps are unknown, so we can't assign ladders upfront. The key insight is to greedily commit ladders as we go, then retroactively swap the cheapest ladder use for bricks whenever we exceed the ladder budget — a min-heap makes that swap O(log k) at each step.

Approach 1 — Binary Search + Greedy Check

Binary search on the answer: for a candidate target building, check whether our resources are sufficient to reach it. The check is monotone — if we can reach building t, we can certainly reach any building before it — so binary search is valid.

Binary search left = 0, right = n - 1; bias mid toward right to find the furthest reachable building.
For a given target, collect all positive gaps in heights[0..target].
Sort gaps in descending order and assign ladders to the largest ladders gaps.
Sum the remaining gaps (those not covered by ladders); if the sum fits in bricks, target is reachable.
Narrow the search window: if reachable, move left = mid; otherwise right = mid - 1.

1def furthestBuilding(heights: list[int], bricks: int, ladders: int) -> int:
2    def can_reach(target: int) -> bool:
3        gaps = sorted(
4            (heights[i + 1] - heights[i] for i in range(target) if heights[i + 1] > heights[i]),
5            reverse=True,
6        )
7        # ladders absorb the largest gaps; everything beyond the ladder budget needs bricks
8        brick_cost = sum(gaps[ladders:])
9        return brick_cost <= bricks
10
11    left, right = 0, len(heights) - 1
12    while left < right:
13        mid = left + (right - left + 1) // 2  # ceiling bias so left = mid makes progress
14        if can_reach(mid):
15            left = mid
16        else:
17            right = mid - 1
18
19    return left

Time: O(n log n log n) — the binary search runs O(log n) iterations; each can_reach call sorts up to n gaps in O(n log n). Space: O(n) — temporary gap array holds at most n entries per can_reach call.

Approach 2 — Greedy with Min-Heap (Single Pass)

Greedily assign a ladder to every climb as we walk forward. When we've used more ladders than allowed, pull the smallest-ladder gap from the heap and pay bricks for it instead — that swap costs the least bricks. If bricks go negative, we cannot reach the next building.

Initialize a min-heap to track gap sizes where ladders are tentatively placed.
For each building, compute the height difference to the next one.
If the difference is ≤ 0, move freely — no resources needed.
Otherwise, push the gap onto the heap (tentatively use a ladder there).
If heap size exceeds ladders, pop the minimum — convert that cheapest ladder assignment to bricks.
If bricks go negative after the swap, return the current index; we can't proceed.
If we finish the loop without running out, return the last building index.

1import heapq
2
3def furthestBuilding(heights: list[int], bricks: int, ladders: int) -> int:
4    ladder_heap = []  # min-heap: tracks gap sizes where ladders are currently assigned
5
6    for i in range(len(heights) - 1):
7        diff = heights[i + 1] - heights[i]
8        if diff <= 0:
9            continue  # descending or flat — free to cross
10
11        heapq.heappush(ladder_heap, diff)  # tentatively place a ladder on this gap
12
13        if len(ladder_heap) > ladders:
14            # we've overdrawn our ladder budget; swap the cheapest ladder gap to bricks
15            smallest_gap = heapq.heappop(ladder_heap)
16            bricks -= smallest_gap
17            if bricks < 0:
18                return i  # can't afford even the cheapest swap — stuck at building i
19
20    return len(heights) - 1  # survived every climb

Time: O(n log k) — each of the n buildings triggers at most one push and one pop on a heap bounded to size k (the number of ladders). Space: O(k) — the heap holds at most k gap values simultaneously.

Complexity Summary

Approach	Time	Space	When to use
Binary Search + Sort	O(n log n log n)	O(n)	When a simpler, verifiable check function is more important than raw speed
Greedy Min-Heap	O(n log k)	O(k)	Default — single pass, optimal when k (ladders) is small relative to n

Common Mistakes

Ignoring descents: Subtracting heights[i+1] - heights[i] without checking the sign will treat downhill moves as negative brick costs, corrupting the running total. Always skip when diff <= 0.
Returning i + 1 instead of i on failure: When the swap at step i (the move from building i to i + 1) drains bricks below zero, the furthest reachable building is i — not i + 1, which is where we failed to arrive.
Using a max-heap instead of a min-heap: The swap should replace the cheapest ladder assignment with bricks, because that minimizes brick expenditure. A max-heap pops the most expensive gap, which is exactly backwards.
Ceiling-bias omission in binary search: Using mid = (left + right) // 2 (floor) combined with left = mid causes an infinite loop when left + 1 == right. The correct pattern for "find rightmost True" is mid = left + (right - left + 1) // 2.
Integer overflow in the binary search check: The total brick cost across all gaps can reach 10^5 × 10^6 = 10^11, which overflows a 32-bit integer. Use long in Java and long long in C++ for the accumulator.

Furthest Building You Can Reach — Solution