Leetcode 1642. Furthest Building You Can Reach

Problem

You are provided with an integer array in which each element represents the height of a building, a certain number of bricks and a certain number of ladders. You can climb the buildings using these bricks and ladders. If the next building is lower or of the same height, you don't need any item to proceed. However, if the next building is higher, you can either use the number of bricks equal to the difference in the heights of the two buildings, or you can use one ladder. Your task is to determine the maximum number of buildings you can climb using these bricks and ladders.

Example

Let's take an example. Suppose, you are given a height list which includes elements [4, 2, 7, 6, 9, 14, 12], 5 bricks and 1 ladder. Now, the first building is 4 units high and the second building is 2 units high. As the next building is not higher, you don't need anything to proceed so you move to building 2. But to move to building 3 which is 7 units high, you need to spend 5 bricks so you move to building 3. Next, you don't need anything to proceed to building 4 as it is not higher than the previous building. But to proceed to building 5 which is 9 units height, you need to use a ladder. Now, you have no remaining bricks or ladders so you can't proceed any further. Hence, you can climb to building index 4.

Approach

The approach we are using here is with the help of a priority queue minHeap which will store the differences in height of the two consecutive buildings. We iterate through each pair of consecutive buildings i, i+1. If the difference in the height is negative, we continue without further consideration, as this means we won't need ladders or bricks to proceed. In other cases, we'll add this difference to the minHeap. If the size of minHeap is larger than the number of ladders available, we start using bricks. We always aim to use bricks on heights which are smaller to reach the building with the maximum index possible at the end. If we don't have enough bricks to climb to the next building, then the current one is our maximum possible.

We can represent this approach as follows;

1
2
3Given: heights = [4, 2, 7, 6, 9, 14, 12], bricks = 5, ladders = 1
4
5minimum heap = []
6
7Start iterating from index 1,
8
91. At index 1, difference = heights[1] - heights[0] = 2 - 4 = -2, 
10   If diff is not a positive number, continue the loop.
11   
12
132. At index 2, difference = heights[2] - heights[1] = 7 - 2 = 5, 
14   If diff is a positive number, push it to minHeap and check if heap size greater than ladders,
15   If it is, Pop the smallest element from heap and reduce it from bricks. Now, bricks = 5 - 5 = 0
16        Now, heap = [], bricks = 0, ladders = 1
17
183. At index 3, difference = heights[3] - heights[2] = 6 - 7 = -1,
19    If diff is not a positive number, continue the loop.
20
214. At index 4, difference = heights[4] - heights[3] = 9 - 6 = 3,
22    If diff is a positive number, push it to minHeap and check if heap size greater than ladders,
23    If it is, Pop the smallest element from heap and reduce it from bricks. 
24    But as bricks are already zero, you can't reduce it further. Hence return the current index - 1 which is 4-1=3.

Solution

Python

1
2python
3import heapq
4
5class Solution:
6    def furthestBuilding(self, heights, bricks, ladders):
7        heap = []
8        for i in range(len(heights) - 1):
9            diff = heights[i + 1] - heights[i]
10            if diff > 0:
11                heapq.heappush(heap, diff)
12            if len(heap) > ladders:
13                bricks -= heapq.heappop(heap)
14            if bricks < 0:
15                return i
16        return len(heights) - 1

Java

1
2java
3public class Solution {
4 public:
5  public int furthestBuilding(int[] heights, int bricks, int ladders) {
6    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();  
7
8    for (int i = 1; i < heights.length; ++i) {
9      int diff = heights[i] - heights[i - 1];
10      if (diff <= 0) continue;
11      minHeap.add(diff);
12      if (minHeap.size() > ladders) 
13        bricks -= minHeap.poll();
14      if (bricks < 0)
15        return i - 1;
16    }
17    return heights.length - 1;
18  }  
19}    

C++

1
2c++
3#include <queue>
4
5class Solution {
6public:
7  int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
8    priority_queue<int, vector<int>, greater<int>> minHeap;
9
10    for (int i = 1; i < heights.size(); ++i) {
11      const int diff = heights[i] - heights[i - 1];
12      if (diff <= 0) continue;
13      minHeap.push(diff);
14      if (minHeap.size() > ladders)
15        bricks -= minHeap.top(), minHeap.pop();
16      if (bricks < 0)
17        return i - 1;
18    }
19    return heights.size() - 1;
20  }
21};

C#

1
2csharp
3public class Solution {
4    public int FurthestBuilding(int[] heights, int bricks, int ladders) {
5        var heap = new MinHeapComparer();        
6        for (int i = 0; i < heights.Length - 1; i++) {
7            int diff = heights[i + 1] - heights[i];
8
9            if (diff > 0) heap.Add(diff);
10            if (heap.Count > ladders) bricks -= heap.Poll();
11            if (bricks < 0) return i;
12        }
13
14        return heights.Length - 1;
15    }
16}

JavaScript

1
2javascript
3function furthestBuilding(heights, bricks, ladders) {
4    var diffPeek = [], diffIndex = 0, i = 1;
5    for (; i < heights.length; ++i) {
6        if (heights[i] > heights[i - 1]) {
7            diffIndex = insertSort(diffPeek, diffIndex, heights[i] - heights[i - 1]);
8            if (diffIndex > ladders) 
9                bricks -= diffPeek[--diffIndex];
10            if (bricks < 0) return i - 1;
11        }
12    }
13    return i - 1;    
14}
15
16function insertSort(arr, index, value) {
17    let i = Math.min(index, arr.length - 1);
18    while (i >= 0 && arr[i] > value) i--;
19    arr.splice(i+1, arr.length - 1 - i, value)
20    return Math.min(index + 1, arr.length);
21}

In this problem, we need to consider larger differences in building heights if we have sufficient bricks, otherwise, we use a ladder. When we have neither bricks nor ladders left, we return the index of the maximum building we can climb. This problem is a perfect application of a priority queue, which always provides the minimum (or maximum) value in O(1) time.

In Python, we use a min-heap implemented via the heapq module, which pops the smallest difference from the heap, reducing it from the bricks.

Accomplishing the same task in Java, we make use of the PriorityQueue class, with similar steps as Python.

In C++, we utilize the priority_queue function from the queue library, implementing a min-heap to determine the minimum difference.

In C#, we use a priority queue from a custom MinHeapComparer class, which works similarly to the Python heapq module.

Finally, JavaScript doesn't have built-in support for priority queues or heaps, so we implement our version of a sorted array as a priority queue. We insert every element in its correct position so that the smallest item is always at the end and we ignore elements exceeding the ladders limit.

Overall, the common theme across all these solutions is the use of a priority queue to keep track of the minimum differences in height, thereby reducing the amount of bricks needed to climb to the next building. If we do not have enough bricks, we resort to using ladders until we exhaust those as well, at which point we return the maximum building index we can reach.