1642. Furthest Building You Can Reach
Problem Description
In this problem, you are given an array heights
that represents the heights of a series of buildings in a line. You are also given a certain number of bricks
and ladders
. As you move from one building to the next, you can either use bricks or ladders based on the following rules:
- If the building you are currently on is of equal or greater height than the next one, you can move ahead without using any bricks or ladders.
- If the building you are currently on is shorter than the next one, you need to bridge the height difference by either using a ladder or using as many bricks as the height difference.
Your goal is to figure out the farthest building index (0-indexed) you can reach by using the ladders and bricks in the best way possible.
Intuition
The intuition behind the solution revolves around optimizing the use of ladders, which are more versatile and valuable than bricks. Since ladders can cover any height difference and you have a limited number of them, you want to use ladders for the largest height differences. For smaller height differences, it's more economical to use bricks.
One effective approach to solve this problem is using a min-heap to keep track of the ladders
largest height differences encountered so far as you iterate through the array. Here's the thought process:
- As you traverse each building, calculate the height difference with the next building if it's greater than the current one.
- Add these differences to a min-heap. Since the size of the heap is limited to the number of available ladders, whenever you add an item and the heap size exceeds the number of ladders, you pop the smallest item. This represents using bricks for the smallest climb that you initially thought of using a ladder for.
- When popping from the heap (which means using bricks instead of a ladder), subtract the height difference (number of bricks needed) from the available bricks.
- If at any point you run out of bricks, this means you can't make the climb using bricks anymore, and you've used all your ladders for higher climbs. The current index is the furthest you can reach.
This strategy ensures that ladders are reserved for the biggest climbs, and bricks are used for the smaller ones, which is an optimal way to go as far as possible.
Learn more about Greedy and Heap (Priority Queue) patterns.
Solution Approach
The solution approach uses a greedy algorithm to decide when to use bricks and when to save the ladders for taller buildings. To implement this strategy, we use a min-heap, which is a data structure that allows us to efficiently track and update the smallest height differences for which we've decided to use ladders.
Here are the steps taken in the Python code implementation:
-
We initialize a min-heap
h
as an empty list, which will store the heights differences where a ladder is used. -
We then iterate through the
heights
array with the variablei
indicating our current position, comparing each buildinga
with the next buildingb
. -
For each pair of buildings where building
b
is taller (i.e., the height differenced
is greater than 0), we push the difference to the heap usingheappush(h, d)
. -
We then check if the length of the heap exceeds the number of available ladders. If it does, this means we must use bricks instead of a ladder for the smallest height difference encountered so far. To do this, we pop from the heap using
heappop(h)
, which removes and returns the smallest item from the heap. We then subtract this value from our availablebricks
. -
If at any point our count of bricks falls below 0, we can no longer proceed to the next building using bricks. We return the current index
i
because that's the furthest we can go. -
If we finish iterating through the array without running out of bricks, it means we were able to reach the last building. We return
len(heights) - 1
as we have successfully reached the end.
The use of a min-heap here is crucial for keeping our algorithm efficient. Without the heap, we would have to search through all height differences we've encountered whenever we need to use bricks, which would make our solution much slower. With the min-heap, we ensure that we are always removing the smallest height difference in logarithmic time complexity, which keeps the overall time complexity of the algorithm controlled and efficient.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach:
Imagine you have an array heights = [4, 2, 7, 6, 9, 14, 12]
, bricks = 5
, and ladders = 1
.
Following the steps of the solution:
-
Initialize a Min-Heap: Start with an empty min-heap
h
. -
Iterate Over Buildings: Begin traversing the buildings. The comparison starts at the first building (
i = 0
) and goes to the second last one. -
Building Heights Comparison:
- From
4
to2
: No bricks or ladders needed because the next building is shorter. - From
2
to7
: The height difference is5
, so we push5
into the heap (h = [5]
). - From
7
to6
: No action needed, as the next building is shorter.
- From
-
Heap Size Check and Bricks Use:
- No check necessary since we have used only one ladder till now, and the heap size is within the limit of available ladders (
heap size = 1, ladders = 1
).
- No check necessary since we have used only one ladder till now, and the heap size is within the limit of available ladders (
-
Building Heights Comparison Continued:
- From
6
to9
: The height difference is3
, add this to the heap (h = [3, 5]
).
- From
-
Heap Size Exceeds Available Ladders:
- Because we have more items in the heap than available ladders, we must pop the smallest item. We pop
3
and subtract it from the bricks (bricks = 5 - 3 = 2
).
- Because we have more items in the heap than available ladders, we must pop the smallest item. We pop
-
Building Heights Comparison Continued:
- From
9
to14
: The height difference is5
. Add this to the heap (h = [5, 5]
).
- From
-
Heap Size Exceeds Again:
- Again, we have more items in the heap than ladders. Pop the smallest item (which is
5
) and subtract from the bricks (bricks = 2 - 5 = -3
).
- Again, we have more items in the heap than ladders. Pop the smallest item (which is
-
Bricks Are Depleted:
- Our brick count goes below 0, which means we cannot proceed further using bricks.
-
Conclusion:
- We are currently at index
4
(heights[4] = 9
) and can't move to index5
because we have a negative brick count. The farthest index we could reach is4
.
- We are currently at index
In the given example, the algorithm allows us to move as far as possible, using ladders for the most significant height differences when necessary and bricks for the smallest one until the bricks run out. The index 4
is the farthest building we can reach given the constraints of our bricks
and ladders
.
Solution Implementation
1from heapq import heappush, heappop
2
3class Solution:
4 def furthest_building(self, heights, bricks, ladders):
5 """
6 This method determines how far you can reach by climbing buildings of various heights using a given number of bricks and ladders.
7
8 :param heights: A list of integers representing the heights of buildings
9 :param bricks: The total number of bricks available to climb up the buildings
10 :param ladders: The total number of ladders available to climb up the buildings
11 :return: The index of the furthest building that can be reached
12 """
13 # A priority queue (min heap) to store the heights that we have used ladders for.
14 height_diffs_heap = []
15
16 for i in range(len(heights) - 1):
17 current_height = heights[i]
18 next_height = heights[i + 1]
19 # Calculate the height difference between the current building and the next one.
20 height_diff = next_height - current_height
21
22 # Only if the next building is higher than the current one do we need ladders or bricks
23 if height_diff > 0:
24 # We use a ladder and add the height difference to the heap.
25 heappush(height_diffs_heap, height_diff)
26 # If we have used more ladders than available, we must replace one ladder with bricks.
27 if len(height_diffs_heap) > ladders:
28 bricks -= heappop(height_diffs_heap) # Replace the ladder for the smallest height diff.
29 # If at any point we do not have enough bricks, we cannot move to the next building.
30 if bricks < 0:
31 return i
32
33 # If we can climb all the buildings with the given bricks and ladders, return the last building index.
34 return len(heights) - 1
35
1class Solution {
2 public int furthestBuilding(int[] heights, int bricks, int ladders) {
3 // Create a priority queue to store the heights that we can climb using ladders.
4 PriorityQueue<Integer> heightDifferences = new PriorityQueue<>();
5
6 // Get the number of buildings from the heights array.
7 int numberOfBuildings = heights.length;
8
9 // Iterate through the array of building heights.
10 for (int i = 0; i < numberOfBuildings - 1; i++) {
11 // Current building height and the next building height.
12 int currentHeight = heights[i];
13 int nextHeight = heights[i + 1];
14
15 // Calculate the height difference between the current and next building.
16 int diff = nextHeight - currentHeight;
17
18 // If the next building is taller, a climb is needed.
19 if (diff > 0) {
20 // Add the height difference to the priority queue.
21 heightDifferences.offer(diff);
22
23 // If we have used more ladders than available, we use bricks.
24 if (heightDifferences.size() > ladders) {
25 // Remove the smallest height difference and use bricks to climb up.
26 bricks -= heightDifferences.poll();
27
28 // If we do not have enough bricks to climb, return the current index.
29 if (bricks < 0) {
30 return i;
31 }
32 }
33 }
34 }
35
36 // If we can climb all buildings, return the last building index.
37 return numberOfBuildings - 1;
38 }
39}
40
1#include <vector>
2#include <queue>
3using namespace std;
4
5class Solution {
6public:
7 int furthestBuilding(vector<int>& heights, int bricks, int ladders) {
8 // Min-heap to keep track of the minimum heights we have had to jump using ladders
9 priority_queue<int, vector<int>, greater<int>> min_heap;
10 int buildingCount = heights.size(); // Total number of buildings
11
12 // Go through each building except the last one
13 for (int i = 0; i < buildingCount - 1; ++i) {
14 int current_height = heights[i]; // Height of the current building
15 int next_height = heights[i + 1]; // Height of the next building
16 int height_difference = next_height - current_height; // Calculate the height difference
17
18 if (height_difference > 0) { // If the next building is taller
19 min_heap.push(height_difference); // Use a ladder for now to climb up
20 if (min_heap.size() > ladders) { // If we have used more ladders than we have
21 bricks -= min_heap.top(); // Replace one ladder use with bricks
22 min_heap.pop(); // Remove the smallest height difference we overcame with a ladder
23 if (bricks < 0) { // If we don't have enough bricks to go to the next building
24 return i; // Return the index of the current building
25 }
26 }
27 }
28 }
29 // If we manage to consider all the buildings, return the index of the last building
30 return buildingCount - 1;
31 }
32};
33
1function furthestBuilding(heights: number[], bricks: number, ladders: number): number {
2 // Since TypeScript does not have a built-in priority queue, we'll use an array to simulate it.
3 let minHeap: number[] = []; // This will function as our min-heap.
4
5 const buildingCount = heights.length; // Total number of buildings.
6
7 // Helper function to simulate the push operation of the priority queue.
8 function pushHeap(value: number) {
9 minHeap.push(value);
10 minHeap.sort((a, b) => a - b); // Sort to keep the smallest elements at the start.
11 }
12
13 // Helper function to simulate the pop operation of the priority queue.
14 function popHeap() {
15 minHeap.shift(); // Remove the smallest element, akin to popping from a min-heap.
16 }
17
18 // Go through each building except the last one.
19 for (let i = 0; i < buildingCount - 1; ++i) {
20 const currentHeight = heights[i]; // Height of the current building.
21 const nextHeight = heights[i + 1]; // Height of the next building.
22 const heightDifference = nextHeight - currentHeight; // Calculate the height difference.
23
24 if (heightDifference > 0) { // If the next building is taller.
25 pushHeap(heightDifference); // Use a ladder, represented by storing heightDifference.
26 if (minHeap.length > ladders) { // If we've simulated using more ladders than we have.
27 bricks -= minHeap[0]; // Replace one ladder use with bricks.
28 popHeap(); // Remove the smallest height difference we've overcome with a ladder.
29 if (bricks < 0) { // If we don't have enough bricks to reach the next building.
30 return i; // Return the index of the current building.
31 }
32 }
33 }
34 }
35 // If able to consider all the buildings, return the index of the last building.
36 return buildingCount - 1;
37}
38
39// Example usage:
40// const result = furthestBuilding([4, 2, 7, 6, 9, 14, 12], 5, 1);
41// console.log(result); // Outputs the index of the furthest building that can be reached.
42
Time and Space Complexity
Time Complexity:
The function furthestBuilding
iterates through the heights
array once, which has n
elements (n
being the number of buildings). For each building, it may add a height difference to a min-heap:
-
The for-loop iterates
n - 1
times as it skips the last building. We know that inserting into a heap isO(log k)
, wherek
is the number of elements in the heap. In the worst case, the heap size could be equal to the number of ladders (l
). Thus, the worst-case time for insertion overn - 1
iterations isO((n - 1) * log l)
. -
The number of removals from the heap is at most equal to the number of ladders
l
, so the total time for all removals isO(l * log l)
assuming each removal is followed by a heapify operation, which isO(log l)
.
Combining these, since l
is less than or equal to n - 1
, we get the total time complexity to be O(n log l)
.
Space Complexity:
The space complexity is mostly determined by the min-heap that stores the height differences. In the worst case, the heap could store as many elements as there are ladders, so the space complexity is O(l)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which of these pictures shows the visit order of a depth-first search?
Recommended Readings
Greedy Introduction div class responsive iframe iframe src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you to calculate the max min of some value Commonly you may see this phrased in the problem as max min longest shortest largest smallest etc These keywords can be identified by just scanning
https algomonster s3 us east 2 amazonaws com cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!