Problem statement

https://leetcode.com/problems/maximum-building-height/

Solution

See similar problem 0135. Candy, here the idea is almost the same. Iterate from left to right and update heights we can reach. Then iterate from right to left and again update heights. Then iterate once again and for all pairs of buildings with adjacent indexes calculate maximum we can get between these buildings.

Alternatively what you can do is to find points of local minimum and then propogate updates to the left and to the right which is more difficult to code, but complexity is the same.

Complexity

Time complexity is $O(n\log n)$, space complexity is $O(n)$.

Code

class Solution:
    def maxBuilding(self, n, arr):
        arr = [[1, 0]] + sorted(arr) + [[n, n-1]]
        m, ans = len(arr), 0
        
        for i in range(1, m):
            arr[i][1] = min(arr[i][1], arr[i-1][1] + arr[i][0] - arr[i-1][0])
        for i in range(m - 2, -1, -1):
            arr[i][1] = min(arr[i][1], arr[i+1][1] + arr[i+1][0] - arr[i][0])

        for i in range(m-1):
            x1, h1 = arr[i]
            x2, h2 = arr[i+1]
            ans = max(ans, (x2 - x1 - abs(h2-h1))//2 + max(h1, h2))
        
        return ans

Remark

There is alternative solution with stack.