Furthest Building You Can Reach

Problem Summary

• Given a list of heights of buildings, your task is to determine the furthest we can travel
• You can certain bricks and ladders
• With ladders you can jump unlimited height
• With bricks you can jump the difference in height of the two buildings
• Use both resources optimally

Key Observations

• Could be solved with Dynamic Programming but a Greedy approach could be optimal

Approach Taken

• Maintain a Min Heap of the smallest ladder usage
• Swap smaller ladder usage with bricks where possible
• Greedily use ladders first

Why This Works

• You retroactivity swap the waste of ladder usage with bricks and use ladder where its most beneficial

Main Concepts Used

• Heap
• Greedy

Time & Space Complexity

• Time: $O(nlogn)$ → Reason: Adding removing to Heap is $O(logn)$ and iterating through the array is $O(n)$
• Space: $O(n)$ → Reason: Storing each item

Code

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        # heights = [4,12,2,7,3,18,20,3,19], bricks = 10, ladders = 2

        # 4->12 - ladder
        # 12->2 - nothing
        # 2->7  - bricks
        # 7->3  - nothing
        # we are out of ladders but we have 10 bricks
        # whats the smallest jump we can replace with bricks 2->7 = 5 bricks
        # 3->18 - ladder now
        # 20->3 - nothing
        # we stop here because:
        #   - cant replace a ladder with remaining bricks

        smallestLadderUsage = [] # 8,15

        prevHeight = None
        for i, currentHeight in enumerate(heights):
            if prevHeight is not None and currentHeight > prevHeight:
                diffToClimb = currentHeight - prevHeight # 8, 5, 2
                if ladders: # try ladders first
                    ladders -= 1
                    heapq.heappush(smallestLadderUsage, diffToClimb)
                else:
                    if smallestLadderUsage and smallestLadderUsage[0] <= bricks and diffToClimb > smallestLadderUsage[0]:
                        bricks -= heapq.heappop(smallestLadderUsage)
                        heapq.heappush(smallestLadderUsage, diffToClimb)
                    elif diffToClimb <= bricks:
                        bricks -= diffToClimb
                    else:
                        return i - 1
            prevHeight = currentHeight
        return i

Common Mistakes / Things I Got Stuck On

• Edge cases forgot to consider
• When to do the swap and when not to
• Its a hard greedy problem to think through
• Apparently using the Max Heap approach is better