Scale Engineer

Furthest Building You Can Reach

Med
#1508Time: O(N log N * log N). The binary search performs `O(log N)` iterations. In each iteration, `isReachable(k)` takes `O(k log k)` time to collect and sort up to `k` climbs. Since `k` can be up to `N`, this gives a total complexity of `O(N log^2 N)`. This can be optimized to `O(N log N)` by using a selection algorithm (like Quickselect) to find the `ladders`-th largest climb in `O(k)` time, but the sorting-based implementation is simpler.Space: O(N), as the list of climbs can, in the worst case, store up to `N-1` differences.5 companies
Patterns
Greedy
Data structures
ArrayHeap (Priority Queue)
Companies
FlipkartDE ShawMedia.netoyo

Prompt

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach reformulates the problem from "find the furthest building" to "can we reach building k?". Since the ability to reach a building is monotonic (if you can reach building k, you can reach all buildings before it), we can binary search for the furthest reachable index. For each candidate index k, we check if it's possible to reach it by calculating the resources needed. To do this, we find all the necessary climbs up to k, use ladders for the largest ones, and check if we have enough bricks for the rest.

Algorithm

  • The problem has a monotonic property: if we can reach building k, we can also reach any building j < k. This allows us to use binary search on the answer, which is the furthest reachable building index.
  • We binary search for an index k within the range [0, n-1].
  • For each mid index from the binary search, we check if it's possible to reach that building using a helper function isReachable(k).
  • The isReachable(k) function works as follows:
    1. Iterate from building 0 to k-1 and collect all the height differences (diff = heights[i+1] - heights[i]) for climbs (diff > 0) into a list.
    2. To use resources optimally, ladders should be used for the largest climbs. Sort the list of differences in descending order.
    3. Use the available ladders for the largest differences. These climbs cost 0 bricks.
    4. Sum the remaining smaller differences. This sum represents the total bricks required.
    5. If the required bricks are less than or equal to the available bricks, then building k is reachable.
  • Based on the result of isReachable(mid):
    • If true, it means we can reach mid, so we store it as a potential answer and try to reach further by setting low = mid + 1.
    • If false, mid is unreachable, so we must try a smaller index by setting high = mid - 1.
  • The final answer is the largest index for which isReachable returned true.

Walkthrough

We can binary search on the building index to find the furthest one we can reach. The search space for the answer will be from 0 to n-1 (where n is the number of buildings).

For a given index k, we need a function isReachable(k) to determine if it's possible to get there. This function will gather all the climbs (where heights[i+1] > heights[i]) required to get from building 0 to k. To check if these climbs are possible, we should use our ladders on the largest climbs to save the most bricks. So, we collect all climb heights, sort them, assign ladders to the largest ones, and sum up the rest to see if our bricks are sufficient.

The main binary search loop will adjust its search range (low and high pointers) based on whether the middle index mid is reachable. If isReachable(mid) is true, we know we can at least reach mid, so we record it as our answer and try for a further building (low = mid + 1). If it's false, we know mid is too far, so we must aim for a closer building (high = mid - 1).

class Solution {    public int furthestBuilding(int[] heights, int bricks, int ladders) {        int n = heights.length;        int low = 0, high = n - 1;        int ans = 0;         while (low <= high) {            int mid = low + (high - low) / 2;            if (isReachable(mid, heights, bricks, ladders)) {                ans = mid;                low = mid + 1;            } else {                high = mid - 1;            }        }        return ans;    }     private boolean isReachable(int k, int[] heights, int bricks, int ladders) {        java.util.List<Integer> climbs = new java.util.ArrayList<>();        for (int i = 0; i < k; i++) {            if (heights[i+1] > heights[i]) {                climbs.add(heights[i+1] - heights[i]);            }        }         if (climbs.size() <= ladders) {            return true;        }         java.util.Collections.sort(climbs, java.util.Collections.reverseOrder());         long bricksNeeded = 0;        for (int i = ladders; i < climbs.size(); i++) {            bricksNeeded += climbs.get(i);        }         return bricksNeeded <= bricks;    }}

Complexity

Time

O(N log N * log N). The binary search performs `O(log N)` iterations. In each iteration, `isReachable(k)` takes `O(k log k)` time to collect and sort up to `k` climbs. Since `k` can be up to `N`, this gives a total complexity of `O(N log^2 N)`. This can be optimized to `O(N log N)` by using a selection algorithm (like Quickselect) to find the `ladders`-th largest climb in `O(k)` time, but the sorting-based implementation is simpler.

Space

O(N), as the list of climbs can, in the worst case, store up to `N-1` differences.

Trade-offs

Pros

  • A standard and reliable pattern for problems with a monotonic property.

  • The logic is relatively easy to understand and implement correctly.

Cons

  • Less efficient than greedy approaches due to repeated computations. The isReachable function recalculates and sorts climbs for each tested index.

  • The complexity O(N log^2 N) might be too slow for very large inputs, although it often passes within time limits.

Solutions

class Solution {public  int furthestBuilding(int[] heights, int bricks, int ladders) {    PriorityQueue<Integer> q = new PriorityQueue<>();    int n = heights.length;    for (int i = 0; i < n - 1; ++i) {      int a = heights[i], b = heights[i + 1];      int d = b - a;      if (d > 0) {        q.offer(d);        if (q.size() > ladders) {          bricks -= q.poll();          if (bricks < 0) {            return i;          }        }      }    }    return n - 1;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem