1642. Furthest Building You Can Reach LeetCode Solution
In this guide, you will get 1642. Furthest Building You Can Reach LeetCode Solution with the best time and space complexity. The solution to Furthest Building You Can Reach problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Furthest Building You Can Reach
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 = 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.
Time Complexity: O(|\texttt{heights}|\log\texttt{ladders})
Space Complexity: O(|\texttt{heights}|)
1642. Furthest Building You Can Reach LeetCode Solution in C++
class Solution {
public:
int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int i = 1; i < heights.size(); ++i) {
const int diff = heights[i] - heights[i - 1];
if (diff <= 0)
continue;
minHeap.push(diff);
// If we run out of ladders, greedily use as less bricks as possible.
if (minHeap.size() > ladders)
bricks -= minHeap.top(), minHeap.pop();
if (bricks < 0)
return i - 1;
}
return heights.size() - 1;
}
}; /* code provided by PROGIEZ */
1642. Furthest Building You Can Reach LeetCode Solution in Java
class Solution {
public int furthestBuilding(int[] heights, int bricks, int ladders) {
Queue<Integer> minHeap = new PriorityQueue<>();
for (int i = 1; i < heights.length; ++i) {
final int diff = heights[i] - heights[i - 1];
if (diff <= 0)
continue;
minHeap.offer(diff);
// If we run out of ladders, greedily use as less bricks as possible.
if (minHeap.size() > ladders)
bricks -= minHeap.poll();
if (bricks < 0)
return i - 1;
}
return heights.length - 1;
}
} // code provided by PROGIEZ
1642. Furthest Building You Can Reach LeetCode Solution in Python
class Solution:
def furthestBuilding(
self,
heights: list[int],
bricks: int,
ladders: int,
) -> int:
minHeap = []
for i, (a, b) in enumerate(itertools.pairwise(heights)):
diff = b - a
if diff <= 0:
continue
heapq.heappush(minHeap, diff)
# If we run out of ladders, greedily use as less bricks as possible.
if len(minHeap) > ladders:
bricks -= heapq.heappop(minHeap)
if bricks < 0:
return i
return len(heights) - 1 # code by PROGIEZ
