Furthest Building You Can Reach

---

Intuition

• You know you can’t jump to the next building if: You have used up all your bricks and ladders.
• Therefore, for each new building you are trying to jump to, if you have to jump up to it, and you have no ladders left, check if you have bricks left. If you don’t, you can’t jump to the next building and should just stop right there.
• Importantly if you use bricks on a jump, then you need one less ladder, which is what this code implicitly does

Complexity

Runtime

$O(N)$

Space

$O(N)$ since there can be N elements in a heap.

Code

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        heap = []
        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
 
            if diff > 0:
                heappush(heap, diff)
            if len(heap) > ladders:
                bricks -= heappop(heap)
                if bricks < 0:
                    return i
        
        return len(heights) - 1

Cards

START Basic Front: Furthest Building You Can Reach Back: Simulate the placing of ladders until you can’t place any more, then offload the ladders with bricks while you can do so. END

---

References

• Furthest Building You Can Reach
• ChatGPT