Furthest Building You Can Reach

Patrick Leaton
Published: June 5, 2021, 4:19 p.m.
Problem Description

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

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

Example 3:

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

 

Constraints:

  • 1 <= heights.length <= 10^5
  • 1 <= heights[i] <= 10^6
  • 0 <= bricks <= 10^9
  • 0 <= ladders <= heights.length

 

The description was taken from https://leetcode.com/problems/furthest-building-you-can-reach/.

Problem Solution

#O(N(Log K)) Time, O(K) Space
class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        bricks_used = [] 
 
        for i in range(len(heights) - 1):
            height = heights[i + 1] - heights[i]
            if height <= 0:
                continue
            bricks -= height
            heapq.heappush(bricks_used, -height)
            if bricks < 0 and ladders == 0:
                return i
            if bricks < 0:
                ladders -= 1
                bricks -= heapq.heappop(bricks_used)
               
        return len(heights) - 1

Problem Explanation

In the problem, we have bricks and ladders.

The number of bricks used to complete a climb is a static length, one height difference requires one brick. However, the number of ladders is always one regardless of height, giving it a dynamic length.  That means that the ladders are more valuable to us than bricks, and we should be greedy with them, only using them when we are out of bricks.

With the given constraints, we are going to want to have a somewhat greedy approach.  Greedy approaches typically are to sort the given requirements and then continuously try to fit in either the cheapest or most expensive task at a time so that we can conserve the most resources.

Here, we will use bricks first and keep track of the largest heights we used the bricks on by utilizing a max heap.  Only when we are out of bricks we will use ladders.

Once we are out of both, we will return where we ended up last. 

Let's start by initializing our heap that we will use to track the greatest amount of bricks used from each climb.

        bricks_used = []

 

Then, we will begin our traversal through the building tops.

        for i in range(len(heights) - 1):

 

At the beginning of each traversal, we will calculate the height difference between the current building and the next building.

            height = heights[i + 1] - heights[i]

 

If the height is negative, we can just jump down and won't need bricks or ladders.  Similarly, if the height is zero then we can just walk over.

            if height <= 0:
                continue

 

Otherwise, we will use bricks to climb to the next building and make note of how many bricks we used.

            bricks -= height
            heapq.heappush(bricks_used, -height)

 

To create a make-shift max-heap from a min-heap, we will make the heap input, the height, negative so that the largest positive height in the heap becomes the smallest when negative.

If we are out of bricks and ladders, we have nothing to get to the next building so we will return the current building.

            if bricks < 0 and ladders == 0:
                return i

 

If we had to go into brick debt to make this most recent climb, we will consolidate that debt by using a ladder to reclaim the bricks we used in climbing the greatest height we noted so far, so that we get the most bricks back for a ladder.

            if bricks < 0:
                ladders -= 1
                bricks -= heapq.heappop(bricks_used)

 

Remember, we have negative heights in the heap so we will subtract the bricks by the height at the top of the heap.  A negative number subtracted by another becomes a positive.  We could have also just negated the value during the pop.

If we traversed all of the buildings then that means we were able to climb each one so we will return the number of buildings we climbed.

        return len(heights) - 1