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.
This approach uses a greedy strategy combined with a max-heap (priority queue) to determine the optimal use of bricks and ladders. The idea is to always use bricks first for the smallest height difference and use ladders for the largest, potentially reserving the ladders for future taller buildings. Whenever we encounter a new jump (difference in height), we add it to the heap, and if the total number of jumps exceeds the available ladders, we use bricks for the smallest jump. If we don’t have enough bricks, we can’t proceed further.
This C code uses a simple array to store differences between consecutive buildings that require resource expenditure. It sorts these differences in descending order and tries to accommodate the largest jumps with ladders, using bricks for the rest. While sorting and processing the differences, it tracks when there are insufficient bricks to continue, returning the last accessible building index.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing height differences.
This approach employs binary search to find the furthest building we can reach. The binary search is performed over the indices of the buildings (0 to n-1). For each index midpoint in the search, we check if it's possible to reach that building, given the constraints of available bricks and ladders using a helper function that checks feasibility by simulating resource allocation greedily. The search continually refines the possible maximum index based on resource ability.
In this C code, a binary search is conducted over the range of buildings. For each midpoint, a helper function 'canReach' checks the viability of reaching that point by exploiting a simulated min-heap strategy. This allows optimal usage of the available bricks and ladders, guiding the binary search to converge on the maximum reachable building index.
Time Complexity: O(n log n) because of binary search with operations similar to heap for each midpoint.
Space Complexity: O(n) to store the min-heap simulation for each search step.
| Approach | Complexity |
|---|---|
| Greedy Approach with Max-Heap | Time Complexity: O(n log n) due to sorting. |
| Binary Search Approach | Time Complexity: O(n log n) because of binary search with operations similar to heap for each midpoint. |
| Default Approach | — |
| 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. |
Furthest Building You Can Reach - Leetcode 1642 - Python • NeetCodeIO • 21,460 views views
Watch 9 more video solutions →Practice Furthest Building You Can Reach with our built-in code editor and test cases.
Practice on FleetCode