Furthest Building You Can Reach
Problem
0 towards the right through heights.
Stepping down or to an equal height is free. Climbing up by d costs either
d bricks or exactly one ladder (any height). Spend your
bricks and ladders optimally and return the furthest index
you can reach.[4,2,7,6,9,14,12], b=5, l=1Output4[4,12,2,7,3,18,20,3,19], b=10, l=2Output7[14,3,19,3], b=17, l=0Output31 ≤ n ≤ 105 · 1 ≤ heights[i] ≤ 106 · 0 ≤ bricks ≤ 109 · 0 ≤ ladders ≤ n
Try it yourself
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
}
}
ladders tracks exactly that.Instinct "K largest / smallest / closest / most frequent", or "always take the best available next"? Keep a heap - size k for top-K, or a ready-queue for scheduling.
Memory hack Guard the top-K club with a bouncer - a min-heap of size k whose root is the weakest member; anyone stronger kicks them out.
Open the Heap & Top-K guide →Approaches
Brute ForceTry Bricks or Ladder at Every Climb
O(2n)Space O(n)At each upward step branch two ways: pay with bricks (if enough) or use a ladder (if any left); steps down are free. Return the furthest index over all branches. Exhaustive, so it is correct — unlike “bricks first, ladder when short”, which wastes bricks on a big early climb.
public int furthestBuilding(int[] heights, int bricks, int ladders) { return go(heights, 0, bricks, ladders); } private int go(int[] h, int i, int bricks, int ladders) { if (i == h.length - 1) return i; int diff = h[i + 1] - h[i]; if (diff <= 0) return go(h, i + 1, bricks, ladders); int best = i; // stuck here if neither option works if (bricks >= diff) best = Math.max(best, go(h, i + 1, bricks - diff, ladders)); if (ladders > 0) best = Math.max(best, go(h, i + 1, bricks, ladders - 1)); return best; }
Correct by exhaustion, but doubles with every climb.
BetterBinary Search on the Answer
O(n log2 n)Space O(n)If index t is reachable, so is every index before it —
monotone, so binary-search t. To test t, sort the climbs
in [0, t], give ladders to the ladders largest and check
the rest sum to ≤ bricks.
public int furthestBuilding(int[] heights, int bricks, int ladders) { int lo = 0, hi = heights.length - 1; while (lo < hi) { int mid = lo + (hi - lo + 1) / 2; if (canReach(heights, mid, bricks, ladders)) lo = mid; else hi = mid - 1; } return lo; } private boolean canReach(int[] h, int target, int bricks, int ladders) { List<Integer> climbs = new ArrayList<>(); for (int i = 0; i < target; i++) if (h[i + 1] > h[i]) climbs.add(h[i + 1] - h[i]); Collections.sort(climbs); long need = 0; // can exceed int range for (int i = 0; i < climbs.size() - ladders; i++) need += climbs.get(i); return need <= bricks; }
Polynomial and clean, but re-sorts the climbs for each of the log n checks.
OptimalMin-Heap of Ladder Climbs
O(n log L)Space O(L)Walk left to right and push each climb into a min-heap (the climbs currently
“on ladders”). When the heap exceeds L = ladders, the
smallest climb is moved to bricks. The first time bricks < 0, the
current step is impossible even with the best assignment, so stop at i.
public int furthestBuilding(int[] heights, int bricks, int ladders) { PriorityQueue<Integer> pq = new PriorityQueue<>(); // climbs using ladders for (int i = 0; i < heights.length - 1; i++) { int diff = heights[i + 1] - heights[i]; if (diff <= 0) continue; pq.offer(diff); if (pq.size() > ladders) bricks -= pq.poll(); // smallest climb -> bricks if (bricks < 0) return i; } return heights.length - 1; }
Dry run[4,2,7,6,9,14,12], b=5, l=1
- i=04i27691412down → free
- i=142i7691412+5: pq=[5]
- i=2427i691412down → free
- i=34276i91412+3: poll 3, bricks=2
- i=442769i1412+5: poll 5, bricks=-3 → 4
One pass, greedy exchange argument, heap never larger than ladders + 1.
At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Try Bricks or Ladder at Every Climb | O(2n) | O(n) |
| Better | Binary Search on the Answer | O(n log2 n) | O(n) |
| Optimal | Min-Heap of Ladder Climbs | O(n log L) | O(L) |
- Greedy “bricks first, ladder when short” — wastes bricks on a big climb.
- Using a max-heap of ladder climbs — you must evict the smallest one to bricks.
- Summing brick costs in an
int— up to 1011, needslong.
- Show a counter-example for the naive greedy before proposing the heap.
- Justify with an exchange argument: swapping a ladder onto a larger climb never hurts.
- Mention the symmetric variant: max-heap of brick climbs, swap the largest for a ladder.