Compile Ready
Module 6 · Heap + Greedy

Furthest Building You Can Reach

MediumProblem 17 of 21 9 min read ~25 min to solve LeetCode
GreedyHeapPriority QueueArrayResource Allocation
Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

You are given building heights in an array heights, plus bricks and ladders. Moving from building i to i + 1 costs nothing if the next building is not taller. If it is taller by climb, you must cover that climb using either climb bricks or one ladder. Return the index of the furthest building you can reach.

Input

An integer array heights, an integer bricks, and an integer ladders.

Output

An integer: the largest building index reachable from building 0.

Constraints

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

Examples

Example 1

Input: 
heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1
Output: 4
Explanation: Use bricks for climb 5 and a ladder for climb 3 to reach index 4. The next climb of 5 cannot be paid with the remaining bricks.

Example 2

Input: 
heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2
Output: 7
Explanation: Reserve ladders for the largest climbs seen so far. Bricks cover smaller climbs until the attempt to reach index 8 requires more bricks than remain.

Example 3

Input: 
heights = [14,3,19,3], bricks = 17, ladders = 0
Output: 3
Explanation: Only positive climbs cost resources. The single climb from 3 to 19 costs 16 bricks, so the end is reachable.

Learning Objectives

  • Identify why ladders should be saved for the largest climbs, not simply the earliest climbs.
  • Use a min-heap to downgrade the smallest ladder climb to bricks when too many climbs need ladders.
  • Stop exactly at the edge where brick usage first becomes negative.
  • Explain the exchange argument behind assigning premium resources to largest costs.

Intuition

The greedy insight is that ladders are more valuable on larger climbs because a ladder pays one climb regardless of height. If you have seen several positive climbs and only ladders ladders, the best use of those ladders is on the largest climbs among them.

A min-heap lets us revise earlier assignments. Pretend every positive climb gets a ladder by pushing it into the heap. When the heap contains more climbs than ladders, one climb must be paid with bricks. We choose the smallest climb in the heap for bricks, leaving ladders assigned to the largest climbs seen so far.

This avoids the common trap of spending ladders as soon as possible. The heap continuously upgrades ladders to the largest climbs and downgrades smaller climbs to bricks.

Common mistakes

  • ×Using a ladder on the first positive climb without considering larger climbs later.
  • ×Putting every height difference in the heap, including zero or negative moves that cost nothing.
  • ×Returning the next building index after bricks go negative instead of the current building index.
  • ×Using a max-heap for the ladder set and accidentally paying bricks for the largest climb.

Algorithm Explanation

Greedy strategy

Use ladders for the largest positive climbs seen so far. Store ladder-assigned climbs in a min-heap. Whenever the heap size exceeds ladders, remove the smallest climb and pay for that one with bricks.

Why it works

For any prefix of climbs, suppose we must choose which climbs get ladders. Since each ladder has the same cost no matter the climb size, bricks should cover the smaller climbs and ladders should cover the larger climbs. The min-heap enforces exactly that for every prefix.

Proof of correctness

Consider any reachable prefix and any allocation that uses a ladder on a smaller climb a while using bricks on a larger climb b. Swapping the ladder from a to b decreases brick usage by b - a or leaves it unchanged if a = b. The number of ladders used is the same, and reachability cannot get worse. Repeating this exchange transforms an optimal allocation into one where ladders cover the largest climbs in the prefix. Our heap algorithm maintains that allocation after every climb by ejecting the smallest ladder climb to bricks whenever there are too many ladder candidates. Therefore, when bricks first become negative, no other allocation can reach the next building.

Algorithm

  1. Create a min-heap for positive climbs currently assigned to ladders.
  2. Iterate from building 0 to n - 2.
  3. Ignore non-positive climbs.
  4. Push each positive climb into the heap.
  5. If the heap size is greater than ladders, poll the smallest climb and subtract it from bricks.
  6. If bricks becomes negative, return the current building index.
  7. If the loop completes, return n - 1.

Solutions

Solution: Min-heap of ladder climbs

Maintain the set of climbs currently receiving ladders. The heap always contains the largest climbs seen so far because whenever it grows beyond the ladder count, the smallest climb is removed and paid with bricks.

Step-by-step

  1. Create an empty min-heap named ladderClimbs.
  2. For each edge between adjacent buildings, compute the positive climb.
  3. Push every positive climb into the heap as if it were assigned a ladder.
  4. If the heap now has more entries than ladders, remove the smallest climb and spend that many bricks.
  5. If bricks are negative after that payment, return the current index because the next building cannot be reached.
  6. Otherwise continue and return the last index when all moves succeed.
Time

O(n log l)

Space

O(l)

The heap stores at most ladders + 1 climbs, so each positive climb costs O(log l), with l representing the number of ladders plus one for overflow.

Java implementation

Loading…

Dry Run

Sample input

heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1. The heap stores climbs currently reserved for ladders.

moveclimbheap after pushbrick paymentbricks leftfurthest confirmed
0 -> 10[]none51
1 -> 25[5]none52
2 -> 30[5]none53
3 -> 43[3,5]pay 324
4 -> 55[5,5]pay 5-34

With one ladder, the heap keeps one largest climb for the ladder. At move 4 -> 5, even paying bricks for the smallest ladder candidate costs 5, making bricks negative, so index 4 is the furthest reachable building.

Interview Tips

Phrase the heap as an assignment correction tool: every positive climb is a candidate for a ladder, but only the largest candidates keep ladders. When asked why the smallest heap item becomes bricks, use the premium-resource exchange: if a ladder is on a smaller climb while bricks pay a larger one, swapping them only helps.

Likely follow-ups

  • How would you solve it with a max-heap that spends bricks first and refunds the largest climb when a ladder is needed?
  • How would the answer change if ladders had different maximum heights?
  • Can you return which climbs used ladders in addition to the furthest index?
  • What if bricks could be replenished at certain buildings?

Similar Problems

Course Schedule III
HardAlso uses a heap to replace the worst previous commitment.
IPO
HardAnother heap greedy where the available set changes after each choice.
Meeting Rooms II
MediumUses a heap to track active resource commitments over a timeline.
Minimum Number of Refueling Stops
HardA closely related max-heap rollback problem over reachable checkpoints.

Key Takeaways

  • Use premium resources on the largest costs in the current prefix.
  • A min-heap of ladder climbs makes the smallest ladder assignment easy to downgrade to bricks.
  • When bricks first go negative, no exchange can make that prefix feasible.
  • Ignoring non-positive climbs is essential because they consume no resources.
Reusable template: Premium-resource greedy: assign the scarce resource to every candidate, then use a heap to downgrade the least deserving candidate whenever the resource count is exceeded.