1840. Maximum Building Height

/**
 * Problem: LeetCode 1840 - Maximum Building Height
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
import java.util.*;

/**
 * Problem: LeetCode 1840 - Maximum Building Height
 * Difficulty: Hard
 * Language: Java
 * Author: CodeByTushu
 */
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;
    }
}

"""
Problem: LeetCode 1840 - Maximum Building Height
Difficulty: Hard
Language: Python
Author: CodeByTushu
"""
from typing import List

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        r = [[1, 0]]
        for item in restrictions:
            r.append([item[0], item[1]])
        
        has_n = any(item[0] == n for item in r)
        if not has_n:
            r.append([n, n - 1])
            
        r.sort(key=lambda x: x[0])
        m = len(r)
        
        # Left to right pass
        for i in range(1, m):
            dist = r[i][0] - r[i - 1][0]
            r[i][1] = min(r[i][1], r[i - 1][1] + dist)
            
        # Right to left pass
        for i in range(m - 2, -1, -1):
            dist = r[i + 1][0] - r[i][0]
            r[i][1] = min(r[i][1], r[i + 1][1] + dist)
            
        ans = 0
        for i in range(1, m):
            x1, h1 = r[i - 1]
            x2, h2 = r[i]
            dist = x2 - x1
            peak = (h1 + h2 + dist) // 2
            ans = max(ans, peak)
            
        return ans

/**
 * Problem: LeetCode 1840 - Maximum Building Height
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
#include <vector>
#include <algorithm>

using namespace std;

/**
 * Problem: LeetCode 1840 - Maximum Building Height
 * Difficulty: Hard
 * Language: C++
 * Author: CodeByTushu
 */
class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        vector<vector<int>> list;
        list.push_back({1, 0});
        for (const auto& r : restrictions) {
            list.push_back(r);
        }

        bool hasN = false;
        for (const auto& r : list) {
            if (r[0] == n) {
                hasN = true;
                break;
            }
        }
        if (!hasN) {
            list.push_back({n, n - 1});
        }

        sort(list.begin(), list.end(), [](const vector<int>& a, const vector<int>& b) {
            return a[0] < b[0];
        });

        int m = list.size();

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

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

        int ans = 0;
        for (int i = 1; i < m; i++) {
            int x1 = list[i - 1][0];
            int h1 = list[i - 1][1];
            int x2 = list[i][0];
            int h2 = list[i][1];
            int dist = x2 - x1;
            int peak = (h1 + h2 + dist) / 2;
            ans = max(ans, peak);
        }

        return ans;
    }
};

/**
 * Problem: LeetCode 1840 - Maximum Building Height
 * Difficulty: Hard
 * Language: JavaScript
 * Author: CodeByTushu
 */
var maxBuilding = function(n, restrictions) {
    const list = [[1, 0]];
    for (const r of restrictions) {
        list.push([r[0], r[1]]);
    }

    let hasN = false;
    for (const r of list) {
        if (r[0] === n) {
            hasN = true;
            break;
        }
    }
    if (!hasN) {
        list.push([n, n - 1]);
    }

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

    const m = list.length;

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

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

    let ans = 0;
    for (let i = 1; i < m; i++) {
        const x1 = list[i - 1][0];
        const h1 = list[i - 1][1];
        const x2 = list[i][0];
        const h2 = list[i][1];
        const dist = x2 - x1;
        const peak = Math.floor((h1 + h2 + dist) / 2);
        ans = Math.max(ans, peak);
    }

    return ans;
};