Skip to main content
Talentd

Furthest Building You Can Reach - Solution & Explanation

MediumArrayGreedyHeap (Priority Queue)19 min readAsked at: Amazon, Meta, Uber +12
Practice this problem

Problem Statement

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),

  • If the current building's height is greater than or equal to the next building's height, you do not need a ladder or bricks.
  • If the current building's height is less than the next building's height, you can either use one ladder or (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 <= 105
  • 1 <= heights[i] <= 106
  • 0 <= bricks <= 109
  • 0 <= ladders <= heights.length

Approach Overview

Problem 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 1: Greedy Approach with Max-Heap

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing height differences.

Try this approach in the editor →

Approach 2: Binary Search Approach

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.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Approach with Max-Heap

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing height differences.

Binary Search Approach

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.

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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 CheckO(n log n)O(n)Useful when modeling the problem as "can we reach index k" and applying binary search.

Video Solution

Furthest Building You Can Reach - Leetcode 1642 - Python • NeetCodeIO • 22,102 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Furthest Building You Can Reach easy or hard?
Furthest Building You Can Reach is classified as Medium difficulty on LeetCode with an acceptance rate around 50%. The challenge lies in recognizing the greedy insight that ladders should be reserved for the largest climbs and implementing it efficiently with a heap.
How to solve Furthest Building You Can Reach in O(n)?
A strict O(n) solution is difficult because the algorithm needs to repeatedly identify the largest climb seen so far. Using a heap provides that capability in O(log n) time per operation, leading to an overall O(n log n) complexity. Most optimal interview solutions rely on this heap-based greedy method.
Furthest Building You Can Reach Python or Java solution?
Python solutions typically use the heapq module to manage climbs, while Java implementations rely on PriorityQueue. The algorithm iterates through the height array, pushes positive climbs into the heap, and swaps brick usage with ladders when bricks run out.
What is the best approach for Furthest Building You Can Reach?
The optimal approach uses a greedy strategy with a heap (priority queue). Track every upward climb and always assign ladders to the largest climbs while bricks handle smaller ones. This dynamic reassignment ensures resources are used efficiently. The algorithm runs in O(n log n) time with O(n) space.
What data structure is used in Furthest Building You Can Reach?
The key data structure is a heap (priority queue). It tracks height differences between buildings so the algorithm can quickly choose the largest climb to allocate a ladder. Arrays are used for traversal, while the heap enables efficient greedy decisions.
What is the time complexity of Furthest Building You Can Reach?
The most common solution uses a heap and runs in O(n log n) time because each climb may be inserted or removed from the priority queue. Space complexity is O(n) in the worst case if every step requires tracking a climb.
Is Furthest Building You Can Reach asked at Google, Amazon, or Meta?
Furthest Building You Can Reach appears in interview preparation lists for companies like Google, Amazon, and Meta because it tests greedy decision making with heaps. Candidates must recognize when to reassign limited resources to maximize progress.

Ready to solve this problem?

Practice Furthest Building You Can Reach with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Building Where Alice and Bob Can Meet

Next

Make the Prefix Sum Non-negative