1642. Furthest Building You Can Reach - Explanation

1. Brute Force (Greedy)

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

        for i in range(1, n):
            if ladders >= i:
                continue

            diffs = []
            for j in range(i):
                if heights[j + 1] > heights[j]:
                    diffs.append(heights[j + 1] - heights[j])

            diffs.sort()
            brickSum = 0
            for j in range(len(diffs) - ladders):
                brickSum += diffs[j]

            if brickSum > bricks:
                return i - 1

        return n - 1

Time & Space Complexity

Time complexity: $O(n ^ 2 \log n)$
Space complexity: $O(n)$

2. Binary Search On Buildings

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        def canReach(mid):
            diffs = []
            for i in range(mid):
                if heights[i + 1] > heights[i]:
                    diffs.append(heights[i + 1] - heights[i])

            diffs.sort()
            brickSum = 0
            for j in range(len(diffs) - ladders):
                brickSum += diffs[j]
                if brickSum > bricks:
                    return False

            return True

        l, r = ladders - 1, len(heights) - 1
        while l <= r:
            mid = (l + r) // 2
            if canReach(mid):
                l = mid + 1
            else:
                r = mid - 1

        return l - 1

Time & Space Complexity

Time complexity: $O(n \log ^ 2 n)$
Space complexity: $O(n)$

3. Binary Search On Buildings (Optimal)

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        diffs = []
        for i in range(1, len(heights)):
            if heights[i] > heights[i - 1]:
                diffs.append((heights[i] - heights[i - 1], i))

        diffs.sort(reverse=True)

        def canReach(index):
            useLadders = useBricks = 0
            for diff, i in diffs:
                if i > index:
                    continue

                if useLadders < ladders:
                    useLadders += 1
                else:
                    useBricks += diff
                    if useBricks > bricks:
                        return False
            return True

        l, r = 1, len(heights) - 1
        while l <= r:
            mid = (l + r) >> 1
            if canReach(mid):
                l = mid + 1
            else:
                r = mid - 1
        return l - 1

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

4. Max-Heap

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        heap = []  # Max heap of bricks used

        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
            if diff <= 0:
                continue

            bricks -= diff
            heapq.heappush(heap, -diff)

            if bricks < 0:
                if ladders == 0:
                    return i
                ladders -= 1
                bricks += -heapq.heappop(heap)

        return len(heights) - 1

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$

5. Min-Heap

class Solution:
    def furthestBuilding(self, heights: List[int], bricks: int, ladders: int) -> int:
        minHeap = []

        for i in range(len(heights) - 1):
            diff = heights[i + 1] - heights[i]
            if diff <= 0:
                continue

            heapq.heappush(minHeap, diff)
            if len(minHeap) > ladders:
                bricks -= heapq.heappop(minHeap)
                if bricks < 0:
                    return i

        return len(heights) - 1

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(n)$