1840. Maximum Building Height Difficulty

import java.util.*;
class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        List<int[]> list = new ArrayList<>();

        // Building 1 always has height 0
        list.add(new int[]{1, 0});

        for (int[] r : restrictions) {
            list.add(new int[]{r[0], r[1]});
        }

        // Add building n if not already present
        boolean hasN = false;
        for (int[] r : list) {
            if (r[0] == n) {
                hasN = true;
                break;
            }
        }
        if (!hasN) {
            list.add(new int[]{n, n - 1});
        }

        // Sort by building index
        Collections.sort(list, (a, b) -> Integer.compare(a[0], b[0]));

        int m = list.size();

        // Left to right pass
        for (int i = 1; i < m; i++) {
            int dist = list.get(i)[0] - list.get(i - 1)[0];
            list.get(i)[1] = Math.min(list.get(i)[1],
                    list.get(i - 1)[1] + dist);
        }

        // Right to left pass
        for (int i = m - 2; i >= 0; i--) {
            int dist = list.get(i + 1)[0] - list.get(i)[0];
            list.get(i)[1] = Math.min(list.get(i)[1],
                    list.get(i + 1)[1] + dist);
        }

        int ans = 0;

        // Compute maximum possible peak between adjacent restrictions
        for (int i = 1; i < m; i++) {

            int x1 = list.get(i - 1)[0];
            int h1 = list.get(i - 1)[1];

            int x2 = list.get(i)[0];
            int h2 = list.get(i)[1];

            int dist = x2 - x1;

            int peak = (h1 + h2 + dist) / 2;

            ans = Math.max(ans, peak);
        }

        return ans;
    }
}

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:

        arr = [[1, 0]]
        arr.extend(restrictions)

        if not any(x[0] == n for x in arr):
            arr.append([n, n - 1])

        arr.sort()

        m = len(arr)

        for i in range(1, m):
            d = arr[i][0] - arr[i - 1][0]
            arr[i][1] = min(arr[i][1], arr[i - 1][1] + d)

        for i in range(m - 2, -1, -1):
            d = arr[i + 1][0] - arr[i][0]
            arr[i][1] = min(arr[i][1], arr[i + 1][1] + d)

        ans = 0

        for i in range(1, m):
            x1, h1 = arr[i - 1]
            x2, h2 = arr[i]

            dist = x2 - x1
            peak = (h1 + h2 + dist) // 2

            ans = max(ans, peak)

        return ans

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {

        vector<vector<int>> arr;

        arr.push_back({1,0});

        for(auto &x : restrictions)
            arr.push_back(x);

        bool found = false;

        for(auto &x : arr)
            if(x[0]==n) found=true;

        if(!found)
            arr.push_back({n,n-1});

        sort(arr.begin(),arr.end());

        int m=arr.size();

        for(int i=1;i<m;i++){
            int d=arr[i][0]-arr[i-1][0];
            arr[i][1]=min(arr[i][1],arr[i-1][1]+d);
        }

        for(int i=m-2;i>=0;i--){
            int d=arr[i+1][0]-arr[i][0];
            arr[i][1]=min(arr[i][1],arr[i+1][1]+d);
        }

        int ans=0;

        for(int i=1;i<m;i++){

            int x1=arr[i-1][0];
            int h1=arr[i-1][1];

            int x2=arr[i][0];
            int h2=arr[i][1];

            int dist=x2-x1;

            ans=max(ans,(h1+h2+dist)/2);
        }

        return ans;
    }
};

var maxBuilding = function(n, restrictions) {

    const arr = [[1,0], ...restrictions];

    if (!arr.some(x => x[0] === n))
        arr.push([n,n-1]);

    arr.sort((a,b)=>a[0]-b[0]);

    for(let i=1;i<arr.length;i++){

        let d=arr[i][0]-arr[i-1][0];

        arr[i][1]=Math.min(arr[i][1],arr[i-1][1]+d);
    }

    for(let i=arr.length-2;i>=0;i--){

        let d=arr[i+1][0]-arr[i][0];

        arr[i][1]=Math.min(arr[i][1],arr[i+1][1]+d);
    }

    let ans=0;

    for(let i=1;i<arr.length;i++){

        let [x1,h1]=arr[i-1];
        let [x2,h2]=arr[i];

        let dist=x2-x1;

        ans=Math.max(ans,Math.floor((h1+h2+dist)/2));
    }

    return ans;
};