Leetcode 1762 Solution

This article provides solution to leetcode question 1762 (furthest-building-you-can-reach)
Categories:
Tags:
Access this page by simply typing in "lcs 1762" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/furthest-building-you-can-reach

Solution

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        n = len(heights)
        heights.append(0)

        used_bricks = []

        for i in range(n):
            curr_height = heights[i]
            next_height = heights[i + 1]

            if next_height <= curr_height:
                continue

            gap = next_height - curr_height
            while bricks < gap and used_bricks and -used_bricks[0] > gap and ladders > 0:
                brick = -heapq.heappop(used_bricks)
                bricks += brick
                ladders -= 1

            if bricks >= gap:
                brick = gap
                bricks -= brick
                heapq.heappush(used_bricks, -brick)
            elif ladders > 0:
                ladders -= 1
            else:
                return i

        return n - 1