Watch 10 video solutions for Furthest Building You Can Reach, a medium level problem involving Array, Greedy, Heap (Priority Queue). This walkthrough by NeetCodeIO has 21,460 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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),
(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: Starting at building 0, you can follow these steps: - Go to building 1 without using ladders nor bricks since 4 >= 2. - Go to building 2 using 5 bricks. You must use either bricks or ladders because 2 < 7. - Go to building 3 without using ladders nor bricks since 7 >= 6. - Go to building 4 using your only ladder. You must use either bricks or ladders because 6 < 9. It is impossible to go beyond building 4 because you do not have any more bricks or ladders.
Example 2:
Input: heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2 Output: 7
Example 3:
Input: heights = [14,3,19,3], bricks = 17, ladders = 0 Output: 3
Constraints:
1 <= heights.length <= 1051 <= heights[i] <= 1060 <= bricks <= 1090 <= ladders <= heights.lengthProblem Overview: You move from left to right across buildings with different heights. When the next building is taller, you must use either bricks equal to the height difference or one ladder. With limited bricks and ladders, the goal is to determine the furthest index you can reach.
Approach 1: Greedy with Heap (Priority Queue) (Time: O(n log n), Space: O(n))
This problem rewards a greedy strategy. Ladders should cover the largest climbs while bricks handle smaller ones. Iterate through the array of building heights and compute the difference between consecutive buildings. Whenever you encounter a positive climb, push the difference into a heap and temporarily assume bricks will be used. If total brick usage exceeds the available amount, replace the largest climb with a ladder by removing it from the heap. This effectively assigns ladders to the most expensive climbs.
The heap keeps track of climbs you've encountered so far, allowing you to dynamically decide where ladders provide the most value. This combination of a greedy decision process and a heap (priority queue) makes the solution efficient. As soon as bricks become negative and no ladder can compensate, the current building index is the furthest reachable.
Approach 2: Binary Search on Reachable Distance (Time: O(n log n), Space: O(n))
Another way to think about the problem is to ask: can you reach building k? If you can efficiently validate this, the answer can be found with binary search over the building index range. For each candidate index, compute all height differences up to that point and focus only on positive climbs. Sort or maintain them in a heap so that ladders are used on the largest climbs and bricks cover the remaining ones.
If the required bricks exceed the available supply, the candidate index is not reachable. Binary search narrows the range until the maximum reachable building is identified. This method separates feasibility checking from traversal logic and can be useful when reasoning about constraints or adapting the problem to variations.
Recommended for interviews: The greedy heap solution is what interviewers expect. It demonstrates recognition that ladders should cover the largest climbs and shows comfort with a priority queue to dynamically rebalance decisions. The binary search variant proves you can reframe the problem as a monotonic feasibility check, but the heap-based greedy approach is simpler and more commonly discussed in interviews.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Heap (Priority Queue) | O(n log n) | O(n) | Best general solution. Efficiently assigns ladders to the largest climbs using a heap. |
| Binary Search + Feasibility Check | O(n log n) | O(n) | Useful when modeling the problem as "can we reach index k" and applying binary search. |