Leetcode - Furthest Building You Can Reach (Python)

April 2021 Leetcode Challenge
Leetcode - Furthest Building You Can Reach #1642
Difficulty: Medium

[janmichaelaustria]

This problem was tricky. Like intitially I would have just gone through the array, use ladders first, and then bricks, and then stop. It was kinda hard thinking about how to reclaim a ladder using a smaller amount of bricks. Thanks Tim!

My ugly attempt at trying to control for the empty heap case:

class Solution(object):
def furthestBuilding(self, heights, bricks, ladders):
"""
:type heights: List[int]
:type bricks: int
:type ladders: int
:rtype: int
"""
N = len(heights)
ladders_used = []
for i in range(N-1):
climb = heights[i+1] - heights[i]
if climb <= 0:
continue #no need for a climb
#use up a ladder
if ladders > 0:
ladders -= 1
heappush(ladders_used, climb)
#what if we have no ladders, use brick
else:
if ladders_used:
smallest_ladder = ladders_used[0]
if climb < smallest_ladder: #forced to use bricks
bricks -= climb
else: #we can reallocate
smallest_ladder = heappop(ladders_used)
heappush(ladders_used, climb)
bricks -= smallest_ladder
#watch for the empty heap case, we just use the current climb
#and deduct from bricks
else:
bricks -= climb
#if bricks is negative and now ladders, end
if bricks < 0:
return i

return N-1

[alexander]

Can you explain what is: heappush ? Do you mean heap.push or it is a new variable?

[aashigupta]

Yes, if we return i at bricks = 0, we might have shorter buildings coming up that we can cross, but we'll never account for them.

[CEOofTheHood]

hey Tim, did you delete my comment. I wanted to come back to this question and I remember writing down in the comments how I understood this question but I can't find my comment.