1642. Furthest Building You Can Reach

MediumGreedyArrayHeap (Priority Queue)
Leetcode Link

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:

  1. As you traverse each building, calculate the height difference with the next building if it's greater than the current one.
  2. 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.
  3. 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.
  4. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which technique can we use to find the middle of a linked list?

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:

  1. We initialize a min-heap h as an empty list, which will store the heights differences where a ladder is used.

  2. We then iterate through the heights array with the variable i indicating our current position, comparing each building a with the next building b.

  3. For each pair of buildings where building b is taller (i.e., the height difference d is greater than 0), we push the difference to the heap using heappush(h, d).

  4. 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 available bricks.

  5. 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.

  6. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Example 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:

  1. Initialize a Min-Heap: Start with an empty min-heap h.

  2. Iterate Over Buildings: Begin traversing the buildings. The comparison starts at the first building (i = 0) and goes to the second last one.

  3. Building Heights Comparison:

    • From 4 to 2: No bricks or ladders needed because the next building is shorter.
    • From 2 to 7: The height difference is 5, so we push 5 into the heap (h = [5]).
    • From 7 to 6: No action needed, as the next building is shorter.

  4. 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).

  5. Building Heights Comparison Continued:

    • From 6 to 9: The height difference is 3, add this to the heap (h = [3, 5]).

  6. 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).

  7. Building Heights Comparison Continued:

    • From 9 to 14: The height difference is 5. Add this to the heap (h = [5, 5]).

  8. 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).

  9. Bricks Are Depleted:

    • Our brick count goes below 0, which means we cannot proceed further using bricks.

  10. Conclusion:

    • We are currently at index 4 (heights[4] = 9) and can't move to index 5 because we have a negative brick count. The farthest index we could reach is 4.

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
Not Sure What to Study? Take the 2-min Quiz：

How many ways can you arrange the three letters A, B and C?

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 is O(log k), where k 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 over n - 1 iterations is O((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 is O(l * log l) assuming each removal is followed by a heapify operation, which is O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Greedy Introduction

Greedy Introduction iframe width 560 height 315 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 When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you

Heap Fundamentals

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 - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫