Furthest Building You Can Reach | LeetCode | Solution Explained

Solution to LeetCode 1642. Furthest Building You Can Reach. I explain the Priority Queue/Min Heap based approach in detail using visuals and basic observations. Problem Link.

YouTube video with simulation will be added soon!

0. Furthest Building You Can Reach: Problem Discussion

0.0. IO Format

• input:
  • a list of building heights: [4,2,4,7,1,6,8,5,7]
  • bricks: 5
  • ladders: 2
• conditions:
  • from a building at index i, if the next one is <= current one’s height, then we can jump down
  • if the next height is greater, we need to use either bricks to go up, or 1 ladder
  • ladders don’t have any constraint on how long they have to be
• output:
  • return the max index you can reach
• constraints:
  • 1 <= len(heights) <= 105
  • 1 <= heights[i] <= 106
  • 0 <= bricks <= 109
  • 0 <= ladders <= len(heights)

0.1. Examples

1. Furthest Building You Can Reach: First Thoughts

1.0. DP?

In many questions talking about finding the maximum/minimum means that we want to think in terms of dynamic programming.

Since at the ith index, we want to make a decision between choosing a ladder/bricks for spanning a height, we could build a recursion as

recurse(i, ladders, bricks) -> None

Where we keep a track of which index we are on, the number of ladders and bricks left. To keep a track of the max index, we could create a global/class variable.

But this won’t work.

1.1. Constraints

After applying memoization, our time complexity is still #indices * #ladders * #bricks. This means we are looking at something upwards of 10¹⁹. Definitely not going to work.

So, what now?

2. Furthest Building You Can Reach: Observations & Logic

2.0. Intuitions

Firstly, we only ever care about the up direction. Down we can always jump, but in the up direction we have to make the choice of bricks or ladder.

One interesting point is that ladders have no restriction on the height or gap they can span – bricks do.

It thus makes sense for us to use the largest gaps with ladders instead of bricks. Now the question is, how?

2.1. Core Logic

First assume that we have used only bricks to reach a certain point, i.

Now, we have L ladders. This means that we can substitute L gaps with ladders instead of bricks. Now we noted from earlier, that the best case is to substitute the highest gaps with ladders instead of bricks. In other words, we need to keep a track of the highest L gaps.

Now once we do that substitution, we would free up more bricks.

This means that we can now move to the next index, with some extra bricks in hand.

Note how for the next index, we again need to do the computations – of finding the highest L gaps, and then substituting the bricks with the ladders.

2.2. Priority Queue / Min-Heap

From above, “we need to keep a track of the highest L gaps“. How?

We can use a Priority Queue / Min-Heap for this purpose.

• we have a PQ of size L.
• insert the current gap and do saved_bricks += gap
• if len(PQ) > L, we pop the smallest element and do saved_bricks -= smallest_gap

2.3. Simulation

I have covered that in the YouTube video, where I go over each and every single step of what our logic should do.

3. Furthest Building You Can Reach: Optimized Implementation

3.0. Code

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        def get_saved_bricks(gap):
            heappush(biggest_gaps, gap)
            if len(biggest_gaps) > ladders:
                temp = heappop(biggest_gaps)
                return gap - temp
            return gap
            
        bricks_required = 0
        bricks_saved = 0
        biggest_gaps = []
        
        for i, h in enumerate(heights[:-1]):
            gap = heights[i+1] - h
            if gap <= 0: continue
            
            bricks_required += gap
            bricks_saved += get_saved_bricks(gap)

            if bricks_required - bricks_saved > bricks:
                return i
        
        return len(heights)-1

3.1. Complexity Analysis

• Time: O(N.log(L)), where N is the number of heights and L is the number of ladders available. We iterate over each element one by one, and for each, we may have to do an insertion and/or deletion in the heap/PQ of L size.
• Space: O(L) for the size of the heap/PQ that we maintain to keep a track of the biggest L gaps

Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.