# Furthest Building You Can Reach
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/furthest-building-you-can-reach)
Canonical: https://scaleengineer.com/dsa/problems/furthest-building-you-can-reach
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Flipkart](https://scaleengineer.com/companies/flipkart), [DE Shaw](https://scaleengineer.com/companies/de-shaw), [Media.net](https://scaleengineer.com/companies/media.net), [oyo](https://scaleengineer.com/companies/oyo), [Dream11](https://scaleengineer.com/companies/dream11)
---
## Problem
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:**

![](https://assets.glich.co/dsa/furthest-building-you-can-reach/image0.gif) 

**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
## Binary Search on the Answer
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.
**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.
**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.
### Explanation
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`).

```java
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;
    }
}
```
### 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.

## Greedy Approach with Max-Heap
A more direct greedy approach involves iterating through the buildings and making decisions on the fly. The strategy is to always try using the more abundant resource (bricks) first. We use bricks for every climb we encounter. To keep our options open, we store the cost of each of these climbs in a max-heap. If we ever run out of bricks, we check if we have any ladders. If so, we can 'undo' our most expensive brick purchase by using a ladder instead. The max-heap makes it easy to find this most expensive purchase. We take the largest climb from the heap, add its cost back to our brick supply, and use up one ladder. If we run out of bricks and have no ladders to salvage the situation, we've reached the furthest possible building.
**Time:** O(N log N). We iterate through `N-1` buildings. In each iteration, we might perform a heap insertion and/or a poll operation. The heap can grow up to size `N`, so each heap operation takes `O(log N)` time. · **Space:** O(N) in the worst case, as the max-heap could potentially store a difference for every step if all are climbs.
**Pros:** A single-pass `O(N log N)` solution, which is generally more efficient than the binary search approach.; The logic of "use bricks, then swap for a ladder if needed" can be quite intuitive.
**Cons:** The space complexity can be up to `O(N)` if every step is a climb, which is less optimal than the min-heap approach.; The time complexity of `O(N log N)` is generally good but can be improved upon.
### Explanation
This greedy approach iterates through the buildings once, making locally optimal decisions. We prioritize using bricks for any climb and only resort to using a ladder when we're forced to.

We use a max-priority queue to keep track of the height differences of all climbs for which we've used bricks. As we iterate from building `i` to `i+1`:
1. If it's a climb (`heights[i+1] > heights[i]`), we subtract the required bricks and add the difference to our max-heap.
2. If our brick count drops below zero, we're in debt. We must now use a ladder. If we have no ladders, we can't proceed, so `i` is the furthest we can reach.
3. If we do have a ladder, we use it on the largest climb we've paid for with bricks so far. This is the most efficient way to reclaim bricks. We pop the top element from the max-heap (the largest climb), add it back to our `bricks` total, and decrement our ladder count.
4. We continue this until we either reach the end of the buildings or cannot proceed further.

```java
class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        // Max-heap to store the differences where we used bricks
        java.util.PriorityQueue<Integer> maxHeap = new java.util.PriorityQueue<>(java.util.Collections.reverseOrder());

        for (int i = 0; i < heights.length - 1; i++) {
            int diff = heights[i+1] - heights[i];

            if (diff > 0) {
                bricks -= diff;
                maxHeap.add(diff);

                // If we are out of bricks, we need to use a ladder on a past climb
                if (bricks < 0) {
                    if (ladders > 0) {
                        // Use a ladder on the largest climb to save the most bricks
                        bricks += maxHeap.poll();
                        ladders--;
                    } else {
                        // No ladders left and not enough bricks
                        return i;
                    }
                }
            }
        }

        // If we reach here, we can get to the last building
        return heights.length - 1;
    }
}
```
### Algorithm
- Iterate through the buildings from `i = 0` to `n-2`.
- At each step, calculate the height difference `diff = heights[i+1] - heights[i]`.
- If `diff <= 0`, we can move to the next building for free.
- If `diff > 0`, we have a climb. We greedily assume we will use bricks for this climb.
  - We subtract `diff` from our `bricks` count.
  - We push the value of `diff` into a max-priority queue. This queue keeps track of all the brick amounts we have spent.
- After spending bricks, if our `bricks` count becomes negative, it means we have a deficit.
  - To resolve the deficit, we must retroactively use a ladder on a previous climb.
  - If we have no ladders left (`ladders == 0`), we cannot resolve the deficit and are stuck. We return the current index `i`.
  - If we have ladders, we should use one on the climb that required the most bricks to get the biggest "refund". This is the largest element in our max-priority queue.
  - We pop the max element from the heap, add it back to our `bricks` count, and decrement `ladders`.
- If the loop completes without getting stuck, it means we can reach the final building. Return `n-1`.

## Greedy Approach with Min-Heap (Most Efficient)
This is the most efficient approach, leveraging a greedy strategy with a min-heap. The insight is that ladders should always be used for the largest height differences to maximize their value. We iterate through the buildings, and for every climb, we add its height difference to a min-heap of a fixed capacity equal to the number of ladders. This heap effectively keeps track of the largest climbs seen so far. If the heap size exceeds the number of ladders, it means we have more climbs than ladders. In this case, the smallest climb in the heap (the one at the top) must be handled by bricks. We remove it from the heap and subtract its cost from our brick supply. If we can't afford it, we've found the furthest building we can reach.
**Time:** O(N log L), where `N` is the number of buildings and `L` is the number of ladders. We iterate through `N-1` buildings, and each heap operation takes `O(log L)` time since the heap's size is capped by `L`. · **Space:** O(L), where `L` is the number of ladders. The min-heap stores at most `L+1` elements.
**Pros:** The most efficient solution with the best time and space complexity.; The heap size is bounded by `ladders`, making it very fast when the number of ladders is small.; It's a single-pass algorithm.
**Cons:** The logic can be slightly less direct to grasp compared to the max-heap approach, as it involves maintaining a set of climbs for ladders and only paying with bricks when that set overflows.
### Explanation
This optimized greedy approach ensures that ladders are always used for the largest climbs encountered. We use a min-priority queue to maintain the `k` largest climbs, where `k` is the number of ladders.

As we iterate through the buildings:
1. For each climb `diff > 0`, we add it to the min-heap.
2. The min-heap will store the climbs we are reserving our ladders for.
3. If the number of climbs in the heap exceeds the number of ladders, it means we can't use a ladder for all of them. The one to give up is the smallest one in this set, which is conveniently at the top of the min-heap.
4. We `poll()` this smallest climb from the heap and pay for it using bricks.
5. If our brick supply `bricks` drops below zero after paying, it's impossible to proceed. The furthest we can reach is the current building `i`.
6. If we successfully iterate through all the buildings, it means we can reach the end.

This method is highly efficient because the heap size is bounded by the number of ladders, which can be much smaller than `N`.

```java
class Solution {
    public int furthestBuilding(int[] heights, int bricks, int ladders) {
        // Min-heap to store the `ladders` largest climbs
        java.util.PriorityQueue<Integer> minHeap = new java.util.PriorityQueue<>();

        for (int i = 0; i < heights.length - 1; i++) {
            int diff = heights[i+1] - heights[i];

            if (diff > 0) {
                minHeap.add(diff);
                // If we have more climbs than ladders, the smallest one must be paid by bricks
                if (minHeap.size() > ladders) {
                    bricks -= minHeap.poll();
                }

                // If we run out of bricks, we can't go further
                if (bricks < 0) {
                    return i;
                }
            }
        }

        return heights.length - 1;
    }
}
```
### Algorithm
- The core idea is that ladders are invaluable and should be reserved for the largest climbs.
- We iterate through the buildings from `i = 0` to `n-2`.
- We use a min-priority queue to keep track of the `ladders` largest climbs encountered so far.
- At each step `i`, calculate the height difference `diff = heights[i+1] - heights[i]`.
- If `diff <= 0`, move on for free.
- If `diff > 0`, we have a climb. We tentatively add this `diff` to our min-heap. This heap represents the climbs we are currently using ladders for.
- If the size of the min-heap becomes greater than the number of `ladders` we have, it means we are trying to use one too many ladders.
- To fix this, we must pay for one of the climbs with bricks. To be optimal, we should use bricks for the smallest of the climbs currently designated for ladders. This smallest climb is the root of the min-heap.
- We poll the minimum element from the heap and subtract this cost from our `bricks` count.
- If at any point our `bricks` count becomes negative, it means we cannot afford even the smallest of the largest climbs. We are stuck and must return the current index `i`.
- If the loop finishes, we can reach the last building, so we return `n-1`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int furthestBuilding(vector<int> &heights, int bricks, int ladders) {
    priority_queue<int, vector<int>, greater<int>> q;
    int n = heights.size();
    for (int i = 0; i < n - 1; ++i) {
      int a = heights[i], b = heights[i + 1];
      int d = b - a;
      if (d > 0) {
        q.push(d);
        if (q.size() > ladders) {
          bricks -= q.top();
          q.pop();
          if (bricks < 0) {
            return i;
          }
        }
      }
    }
    return n - 1;
  }
};

```

### Python

```python
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int: h = [] for i, a in enumerate(heights[: - 1]): b = heights[i + 1] d = b - a if d > 0: heappush(h, d) if len(h) > ladders: bricks -= heappop(h) if bricks < 0: return i return len(heights) - 1

```