This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1642 (Medium): Furthest Building You Can Reach
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
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.
Examples:
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.Visual:
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 <= 10^51 <= heights[i] <= 10^60 <= bricks <= 10^90 <= ladders <= heights.length
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
The first realization should be that we always want to use our ladders to their best effect: where they would save us the most amount of bricks. Unfortunately, we can't just save the ladders for the largest gaps in the building heights, because we may not be able to reach them by using bricks.
Since we can't find out how far we can go until we figure out where to place the ladders, and we can't figure out where to put the ladders until we see how far we can go, we'll have to move the ladders around as we go in order to maintain their maximum effect.
To put this in terms of a coding solution, as we iterate through the building heights array (H), we'll want to continuously make sure that the largest L number of positive differences are occupied with ladders, allowing us the best use of our B number of bricks.
In general, this means that we should start iterating through H, ignoring any difference (diff) that is 0 or less, and place a ladder whenever we have a positive difference. Once we've used up all the ladders, then we can start using bricks. If we come across a diff that is larger than the smallest ladder that we're currently using, we should replace that ladder with bricks and move the ladder forwad to the current diff. Otherwise we should use bricks for the current diff.
The second big realization at this point is that we need a min-heap or min priority queue in order to keep track of the heights of the ladders in use, so that we can always take the smallest one, thus keeping the ladders always on the largest diff values.
If at any point we run out bricks, then we can't reach the next building and should return i. If we're able to reach the end of H without running out of bricks, we can return H.length - 1, signifying that we reached the last building.
- Time Complexity: O(N) where N is the length of H
- Space Complexity: O(L) to keep track of L number of ladder lengths
Implementation:
The Javascript MinPriorityQueue() npm package isn't as efficient as a min-heap, but it is much more succinct, so I've included both versions of code for comparison.
For C++, the priority_queue defaults to a max order, so we can just invert the sign on the diff values before insertion to effectively turn it into a min priority queue instead.
Javascript Code:
(Jump to: Problem Description || Solution Idea)
w/ MinPriorityQueue():
var furthestBuilding = function(H, B, L) {
let len = H.length - 1,
pq = new MinPriorityQueue({priority: x => x})
for (let i = 0; i < len; i++) {
let diff = H[i+1] - H[i]
if (diff > 0) {
if (L > 0) pq.enqueue(diff), L--
else if (pq.front() && diff > pq.front().element)
pq.enqueue(diff), B -= pq.dequeue().element
else B -= diff
if (B < 0) return i
}
}
return len
};
w/ Min-Heap:
var furthestBuilding = function(H, B, L) {
let len = H.length - 1, heap = [,]
const heapify = val => {
let i = heap.length, par = i >> 1, temp
heap.push(val)
while (heap[par] > heap[i]) {
temp = heap[par], heap[par] = heap[i], heap[i] = temp
i = par, par = i >> 1
}
}
const extract = () => {
if (heap.length === 1) return null
let top = heap[1], left, right, temp,
i = 1, child = heap[3] < heap[2] ? 3 : 2
if (heap.length > 2) heap[1] = heap.pop()
else heap.pop()
while (heap[i] > heap[child]) {
temp = heap[child], heap[child] = heap[i], heap[i] = temp
i = child, left = i << 1, right = left + 1
child = heap[right] < heap[left] ? right : left
}
return top
}
for (let i = 0; i < len; i++) {
let diff = H[i+1] - H[i]
if (diff > 0) {
if (L > 0) heapify(diff), L--
else if (heap.length > 1 && diff > heap[1])
heapify(diff), B -= extract()
else B -= diff
if (B < 0) return i
}
}
return len
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def furthestBuilding(self, H: List[int], B: int, L: int) -> int:
heap = []
for i in range(len(H) - 1):
diff = H[i+1] - H[i]
if diff > 0:
if L > 0:
heappush(heap, diff)
L -= 1
elif heap and diff > heap[0]:
heappush(heap, diff)
B -= heappop(heap)
else: B -= diff
if B < 0: return i
return len(H) - 1
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public int furthestBuilding(int[] H, int B, int L) {
int len = H.length - 1;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < len; i++) {
int diff = H[i+1] - H[i];
if (diff > 0) {
if (L > 0) {
pq.add(diff);
L--;
} else if (pq.size() > 0 && diff > pq.peek()) {
pq.add(diff);
B -= pq.poll();
} else B -= diff;
if (B < 0) return i;
}
}
return len;
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
int furthestBuilding(vector<int>& H, int B, int L) {
int len = H.size() - 1;
priority_queue<int> pq;
for (int i = 0; i < len; i++) {
int diff = H[i+1] - H[i];
if (diff > 0) {
if (L) pq.push(-diff), L--;
else if (!pq.empty() && diff > -pq.top())
pq.push(-diff), B += pq.top(), pq.pop();
else B -= diff;
if (B < 0) return i;
}
}
return len;
}
};
Top comments (2)
I really enjoyed reading this, great article. The best part has to be how you pointed out the npm package shortcomings in JS and the caveats to solve the problem in C++ by inverting the sign before adding to a priority queue.
Thanks for the response!
I will admit that I felt a little bit bad about including an entire heap implementation (even if only for one JS solution) without actually going into how the heap structure works, but it really does provide much more efficient processing than the MinPriorityQueue npm, which is also obviously not in the standard library.