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
- a list of building heights: [4,2,4,7,1,6,8,5,7]
- bricks: 5
- ladders: 2
- 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
- return the max index you can reach
1 <= len(heights) <= 105
1 <= heights[i] <= 106
0 <= bricks <= 109
0 <= ladders <= len(heights)
1. Furthest Building You Can Reach: First Thoughts
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.
After applying memoization, our time complexity is still
#indices * #ladders * #bricks. This means we are looking at something upwards of 1019. Definitely not going to work.
So, what now?
2. Furthest Building You Can Reach: Observations & Logic
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
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
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
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.
O(L)for the size of the heap/PQ that we maintain to keep a track of the biggest L gaps
June 13, 2022
January 24, 2022