Problem statement

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

Solution

This is not the most optimal solution, but I think it is useful in educational purposes. The idea is to ask question:

given our bricks and ladders, can we reach building number k?

If we know in advance, what buildings we have and what gaps between them we need to cover, we can do it in greedy way: consider to_climb is the list of all positive gaps (we are not interested in negative gaps at all), and then we use ladders for the biggest L of them (L is number of ladders) and for all others we try to use bricks.

Now, we can see, that answers for questions, can we reach 1-st building, can we reach 2-nd building and so on will be in the form:

True, True, ... True, True, False, False, ..., False, ...

That is if we can reach some building k, we can reach all previous buildings as well. The question asked is what is the maximum number of building we can reach and binary search is ideal to deal with this problem. I also add infinitely tall building in the end and then just run BS, asking question isReach

Complexity

Time complexity is O(n * log n * log n), because we have range of length n to our binary search and each isReach problem can be solved in O(n log n). Space complexity is O(n).

Code

class Solution:
    def furthestBuilding(self, H, bricks, L):
        H += [float("inf")]

        def isReach(k):
            to_climb = [y - x for y, x in zip(H[1:k+1], H[:k+1]) if y-x > 0]
            return len(to_climb) <= L or sum(sorted(to_climb)[::-1][L:]) <= bricks
    
        beg, end = 0, len(H) - 1
        while beg + 1 < end:
            mid = (beg + end)//2
            if isReach(mid):
                beg = mid
            else:
                end = mid
        return beg

Remarks

When you see complexity like this it is often (but not always) the indicator, that complexity is not optimal: we have two logarithmic factors. Indeed, there exists solution with heaps: while we traverse our buildings, we keep in the heap the L biggest gaps we have so far. Each time when we have new positive gap, we put it to heap and extract one element from heap, the smallest one: we have no other choice but to use bricks for this gap. If in some moment of time we out of bricks, we return index we have. Time complexity will be O(n log L).

class Solution:
    def furthestBuilding(self, H, bricks, L):
        heap, n = [], len(H)

        for h1, h2, i in zip(H, H[1:], range(n)):
            if h2 - h1 > 0:
                heappush(heap, h2 - h1)
            if len(heap) > L:
                bricks -= heappop(heap)
            if bricks < 0:
                return i
            
        return n-1