Furthest Building You Can Reach

Medium

Google

1 view

Topics:

Greedy AlgorithmsArraysStacks

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:

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.

Example 2:

heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2

Output: 7

Can you provide an efficient solution to determine the furthest reachable building index?

Furthest Building You Can Reach

Medium

Google

1 view

Topics:

Greedy AlgorithmsArraysStacks

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:

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.

Example 2:

heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2

Output: 7

Can you provide an efficient solution to determine the furthest reachable building index?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the values of heights[i], bricks, and ladders? Specifically, what are the maximum and minimum possible values for each?
If I run out of both bricks and ladders before reaching the end of the heights array, what index should I return? Should I return the last building I *could* reach, or is there a specific value I should return to indicate no solution?
Is it possible for the input array 'heights' to be empty or null?
If a jump requires no bricks (heights[i+1] <= heights[i]), can I proceed without using either bricks or a ladder?
Are 'bricks' and 'ladders' guaranteed to be non-negative integers?

Brute Force Solution

Approach

The brute force method to find the furthest reachable building involves exhaustively checking every possible path you can take. At each building, you consider whether you can reach the next one using your bricks or ladders, and explore all combinations of these choices.

Here's how the algorithm would work step-by-step:

Start at the first building.
Consider if you can reach the next building using either bricks or a ladder.
If you use bricks, subtract the brick amount from your total bricks, and continue to the next building.
If you use a ladder, subtract one ladder from your total ladders, and continue to the next building.
Keep track of the furthest building you can reach for each different combination of brick and ladder usage.
If at any point you run out of both bricks and ladders, stop and note the building you're currently at.
Repeat the above steps by trying all possible sequences of using bricks and ladders.
After trying all possibilities, determine which sequence lets you reach the furthest building.

Code Implementation

def furthest_building_brute_force(heights, bricks, ladders):
    max_reachable_building = 0

    def explore_paths(current_building, remaining_bricks, remaining_ladders):
        nonlocal max_reachable_building
        max_reachable_building = max(max_reachable_building, current_building)

        if current_building == len(heights) - 1:
            return

        height_difference = heights[current_building + 1] - heights[current_building]

        if height_difference <= 0:
            explore_paths(current_building + 1, remaining_bricks, remaining_ladders)
        else:
            # Try using bricks if possible
            if remaining_bricks >= height_difference:
                explore_paths(current_building + 1, remaining_bricks - height_difference, remaining_ladders)

            # Try using ladders if possible
            if remaining_ladders > 0:
                explore_paths(current_building + 1, remaining_bricks, remaining_ladders - 1)

    # Initiate recursive exploration
    explore_paths(0, bricks, ladders)

    return max_reachable_building

Big(O) Analysis

Time Complexity

O(2^n) – The brute force approach explores all possible combinations of using bricks or ladders to reach the next building. For each building, we have two choices: use bricks or use a ladder (if we have enough). Therefore, for n buildings, we have 2 possible choices for each building (except the first one), resulting in 2 * 2 * ... * 2 (n-1 times) possibilities, which is 2^(n-1). Since constants are dropped in Big O notation, the time complexity is O(2^n), representing exponential growth with the number of buildings.

Space Complexity

O(2^N) – The described brute force approach explores all possible combinations of using bricks or ladders at each building. This can be visualized as a binary tree where each node represents a building, and each branch represents either using bricks or a ladder to reach the next building. In the worst-case scenario, the height of this tree would be N, where N is the number of buildings (heights.length). Since the algorithm is essentially performing a depth-first search of this tree, the maximum number of nodes that would need to be stored on the call stack at any one time is proportional to the total number of possible paths. As each building presents two choices (bricks or ladder), it results in a space complexity of O(2^N) due to the exponential branching factor.

Optimal Solution

Approach

The key to solving this problem efficiently is to prioritize using the available bricks for the smallest height differences first and using ladders only for the larger differences. This ensures we maximize the distance we can travel. We can achieve this using a priority queue or a similar data structure that always gives us the smallest differences to cover.

Here's how the algorithm would work step-by-step:

Go through the buildings one by one, comparing the height of each building to the one before it.
If the next building is shorter or the same height, we don't need to use any resources and can move on.
If the next building is taller, we need to use bricks or a ladder. Calculate the height difference.
Imagine we use bricks for this height difference and add it to a collection of height differences we've used bricks for so far, using a data structure that keeps the smallest height differences at the top.
If we run out of bricks, we need to use a ladder. To use a ladder, we find the largest height difference among those we've previously covered using bricks, and replace the most costly set of bricks (the largest difference) with a ladder, freeing up those bricks to use elsewhere. If we haven't used any bricks yet, then we can't make this replacement.
If, even after replacing the largest brick usage with a ladder, we still don't have enough bricks, then we can't reach the next building. We stop and return the index of the current building.
If we reach the last building, we can reach it. So, return the index of the last building.

Code Implementation

import heapq

def furthestBuilding(heights, bricks, ladders):
    height_differences = []
    for i in range(len(heights) - 1):
        difference = heights[i+1] - heights[i]
        if difference > 0:
            # Add the height difference assuming we use bricks
            heapq.heappush(height_differences, difference)

            bricks -= difference

            # If we run out of bricks, use a ladder to replace the largest brick usage
            if bricks < 0:
                if ladders > 0 and height_differences:
                    # Use a ladder for the largest height difference
                    bricks += heapq.heappop(height_differences)
                    ladders -= 1

                # If we still don't have enough resources, we can't proceed
                else:
                    return i

    return len(heights) - 1

Big(O) Analysis

Time Complexity

O(n log n) – The algorithm iterates through the buildings array once, which contributes a factor of n. Inside the loop, a priority queue (heap) is used to store height differences. Inserting an element into the priority queue takes O(log k) time, where k is the number of elements in the priority queue, which is at most n. Thus, the dominant operation is the insertion and potentially the extraction of the maximum element from the priority queue within the loop. Therefore, the overall time complexity is O(n log n).

Space Complexity

O(L) – The auxiliary space complexity is determined by the priority queue (or similar data structure) used to store height differences for which bricks were initially used. In the worst case, we might use bricks for all height differences up to the point where we run out of ladders, so the priority queue could potentially store L elements, where L is the number of ladders available. Thus, the space required for the priority queue is proportional to L. This leads to an auxiliary space complexity of O(L).

Edge Cases

Case	How to Handle
Empty heights array	Return 0 as we start at index 0; no movement is possible from an empty array.
Heights array with only one building	Return 0, as we start at index 0 and no further movement is needed.
Heights array where buildings are monotonically decreasing	Return heights.length -1 since no bricks or ladders are needed.
Heights array where buildings are monotonically increasing and not enough bricks, but enough ladders	Return heights.length -1 since we can use a ladder for each increase.
bricks and ladders are both zero, and heights are increasing	Return 0, as we can't move past the first building.
Very large heights values leading to potential integer overflow when calculating differences	Use long data types to represent height differences to avoid potential overflow issues.
Large heights array size (performance concerns)	Prioritize using a heap-based approach to efficiently track and use the smallest differences, ensuring O(n log k) time complexity where k is the number of ladders.
Zero height difference between buildings	Continue traversal without using any bricks or ladders since no height difference exists.