#1642

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Furthest Building You Can Reach

Furthest Building You Can Reach explores a greedy approach with heap-based optimization to find the maximum reachable building with limited resources.

array greedy heap priority queue

Problem Statement

You are given an integer array heights representing the heights of buildings, a number of bricks, and a number of ladders. Starting from the first building, you need to move through subsequent buildings by using either bricks or ladders to overcome height differences. A ladder can only be used once, while bricks are consumed based on the difference in heights.

For each building, check if you can reach the next one. If the next building is higher, use bricks or a ladder as required. You must manage your resources efficiently and determine how far you can go. The challenge is to identify the farthest building you can reach with the given resources, ensuring that at no point you run out of either.

Examples

Example 1

Input: heights = [4,2,7,6,9,14,12], bricks = 5, ladders = 1

Output: 4

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.

Example 2

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

Output: 7

Example details omitted.

Example 3

Input: heights = [14,3,19,3], bricks = 17, ladders = 0

Output: 3

Example details omitted.

Constraints

1 <= heights.length <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= heights.length

Solution Approach

Greedy Choice and Invariant Validation

Start by iterating through the buildings, comparing height differences. If the next building is taller, decide whether to use bricks or a ladder. Always prefer using a ladder for larger height differences to conserve bricks. If resources run out, you must stop and return the last reachable building.

Heap Optimization

Use a max-heap (priority queue) to keep track of height differences where bricks are used. When running out of bricks, replace the largest brick usage with a ladder to maximize reach. This ensures that we always minimize brick usage for the most costly height differences.

Edge Case Considerations

Handle edge cases where no bricks or ladders are available. If the first building is unreachable, return 0. Also, consider cases where you may have excess resources and can continue beyond the last building.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the heap operations, where each building requires logarithmic time to insert or remove from the heap. Hence, the time complexity is O(n log n). The space complexity is O(n) due to the heap storage and the need to track building differences.

What Interviewers Usually Probe

Check for the candidate's understanding of greedy algorithms and resource optimization.
Ensure they are comfortable with heap operations and how it helps in managing resources efficiently.
Evaluate if they can handle edge cases effectively, such as when there are no bricks or ladders.

Common Pitfalls or Variants

Common pitfalls

Forgetting to use the heap to track and optimize the largest height differences when resources are exhausted.
Failing to correctly prioritize ladders over bricks for larger height gaps.
Mismanaging edge cases where no resources are available or all buildings are reachable with limited resources.

Follow-up variants

What if there were multiple ladders or bricks at specific intervals?
Can the problem be solved with a more straightforward dynamic programming approach?
What if the heights array is reversed, would the solution change?

FAQ

How does the greedy approach apply to the Furthest Building You Can Reach problem?

The greedy approach is applied by always trying to use a ladder for larger gaps and using bricks for smaller gaps, ensuring minimal resource consumption for greater reach.

What role does the heap (priority queue) play in solving this problem?

The heap helps track the largest height differences where bricks are used, allowing us to replace the largest brick usage with a ladder when needed, optimizing resource usage.

What are common mistakes to avoid in the Furthest Building You Can Reach problem?

Common mistakes include not using the heap to track brick usage efficiently or failing to prioritize ladders for larger gaps.

How do edge cases affect the solution for this problem?

Edge cases, such as having no resources or starting with an unreachable building, must be handled by early termination or returning 0.

Can the solution for Furthest Building You Can Reach be improved in terms of time complexity?

The current solution, using a heap, is already optimized with a time complexity of O(n log n). Any improvement would likely involve trade-offs in space or complexity.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        h = []
        for i, a in enumerate(heights[:-1]):
            b = heights[i + 1]
            d = b - a
            if d > 0:
                heappush(h, d)
                if len(h) > ladders:
                    bricks -= heappop(h)
                    if bricks < 0:
                        return i
        return len(heights) - 1

Continue Practicing

#1648 sell diminishing valued colored balls #1675 minimize deviation in array #1606 find servers that handled most number of requests