Problem Description

The Maximum Building Height problem is a challenging algorithmic puzzle from Leetcode. You are given:

• An integer n, representing the total number of buildings in a row, numbered from 1 to n.
• A list of restrictions, where each restriction is a triplet [i, h]. This means that the height of building i cannot exceed h.

• The height of the first building (building 1) is always 0.
• The height difference between any two adjacent buildings is at most 1 (i.e., |height[i] - height[i-1]| ≤ 1 for all i).
• Each building's height cannot exceed its restriction (if any).

Thought Process

At first glance, the problem seems to invite a brute-force approach: try every possible height for every building, checking all restrictions and adjacency constraints. However, this would be computationally expensive for large n.

Instead, we can observe that the main challenge is to balance the restrictions and adjacency constraints. Since the difference between adjacent buildings is at most 1, the height profile is like a "mountain range" that can only rise or fall gradually. Restrictions act as "caps" that force the mountain down at certain points.

The key insight is to propagate these restrictions left-to-right and right-to-left, updating the maximum possible height at each building. This way, we ensure all constraints are respected, and we can efficiently compute the highest peak achievable between any two restrictions.

Solution Approach

We solve the problem in several steps:

1. Normalize Restrictions:
   • Add a restriction for building 1 with height 0 (if not already present), because the first building must always be height 0.
   • Add a restriction for building n with height n-1 (since the maximum possible height at building n is n-1 by adjacency constraints).
   • Sort the restrictions by building index.
2. Left-to-Right Pass:
   • For each restriction from left to right, update its allowed height based on the previous restriction and the maximum possible increase per building.
   • This ensures we do not violate the adjacency constraint when moving from one restriction to the next.
3. Right-to-Left Pass:
   • Repeat the process from right to left, ensuring no restriction's height is too high relative to the next restriction.
4. Find the Maximum Peak:
   • Between each pair of restrictions, the tallest possible building is at the midpoint between them, forming a "mountain peak".
   • Calculate the maximum possible height between each pair based on their positions and allowed heights, using the formula for the midpoint of two slopes.
   • The answer is the largest such height found.

We use arrays/lists to store and update the restrictions, and simple arithmetic to compute the maximum peak between two points.

Example Walkthrough

Sample Input:
n = 5, restrictions = [[2,1],[4,1]]

1. Normalize Restrictions:
   • Add [1,0] and [5,4] (since the max at building 5 cannot exceed 4 by adjacency).
   • Sorted restrictions: [[1,0],[2,1],[4,1],[5,4]]
2. Left-to-Right Pass:
   • From 1 to 2: max height at 2 is min(1, 0+1) = 1
   • From 2 to 4: max height at 4 is min(1, 1+2) = 1
   • From 4 to 5: max height at 5 is min(4, 1+1) = 2
3. Right-to-Left Pass:
   • From 5 to 4: max height at 4 is min(1, 2+1) = 1
   • From 4 to 2: max height at 2 is min(1, 1+2) = 1
   • From 2 to 1: max height at 1 is min(0, 1+1) = 0
4. Find Maximum Peak:
   • Between 1 and 2: max height is 1.
   • Between 2 and 4: positions 2 and 4, heights 1 and 1, distance = 2. The highest possible is at the middle: (1+1+2)//2 = 2
   • Between 4 and 5: max height is 2.
   • So, the answer is 2.

Time and Space Complexity

Brute-force approach: O(n²) or worse, since for each building you might try all possible heights and propagate constraints, leading to quadratic or worse time.

Optimized approach:

• Sorting restrictions: O(m log m), where m = number of restrictions.
• Two passes through the restrictions: O(m).
• Calculating the maximum peak: O(m).

Summary

The Maximum Building Height problem is a classic example of constraint propagation and greedy optimization. By normalizing and sorting restrictions, then performing two passes to propagate adjacency limits, we can efficiently compute the maximum possible building height. The solution cleverly leverages the "mountain" analogy to find the tallest peak between each pair of restrictions, making the approach both efficient and elegant.

Code Implementation

class Solution:
    def maxBuilding(self, n, restrictions):
        restrictions.append([1, 0])
        if restrictions and restrictions[-1][0] != n:
            restrictions.append([n, n-1])
        restrictions.sort()
        m = len(restrictions)
        # Forward pass
        for i in range(1, m):
            d = restrictions[i][0] - restrictions[i-1][0]
            restrictions[i][1] = min(restrictions[i][1], restrictions[i-1][1] + d)
        # Backward pass
        for i in range(m-2, -1, -1):
            d = restrictions[i+1][0] - restrictions[i][0]
            restrictions[i][1] = min(restrictions[i][1], restrictions[i+1][1] + d)
        # Find max peak
        ans = 0
        for i in range(1, m):
            left, h1 = restrictions[i-1]
            right, h2 = restrictions[i]
            d = right - left
            peak = (h1 + h2 + d) // 2
            ans = max(ans, peak)
        return ans
      

class Solution {
public:
    int maxBuilding(int n, vector<vector<int>>& restrictions) {
        restrictions.push_back({1, 0});
        if (restrictions.empty() || restrictions.back()[0] != n)
            restrictions.push_back({n, n - 1});
        sort(restrictions.begin(), restrictions.end());
        int m = restrictions.size();
        // Forward pass
        for (int i = 1; i < m; ++i) {
            int d = restrictions[i][0] - restrictions[i - 1][0];
            restrictions[i][1] = min(restrictions[i][1], restrictions[i - 1][1] + d);
        }
        // Backward pass
        for (int i = m - 2; i >= 0; --i) {
            int d = restrictions[i + 1][0] - restrictions[i][0];
            restrictions[i][1] = min(restrictions[i][1], restrictions[i + 1][1] + d);
        }
        int ans = 0;
        for (int i = 1; i < m; ++i) {
            int left = restrictions[i - 1][0], h1 = restrictions[i - 1][1];
            int right = restrictions[i][0], h2 = restrictions[i][1];
            int d = right - left;
            int peak = (h1 + h2 + d) / 2;
            ans = max(ans, peak);
        }
        return ans;
    }
};
      

import java.util.*;
class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        List<int[]> res = new ArrayList<>();
        for (int[] r : restrictions) res.add(r);
        res.add(new int[]{1, 0});
        if (res.isEmpty() || res.get(res.size()-1)[0] != n)
            res.add(new int[]{n, n-1});
        res.sort(Comparator.comparingInt(a -> a[0]));
        int m = res.size();
        // Forward pass
        for (int i = 1; i < m; ++i) {
            int d = res.get(i)[0] - res.get(i-1)[0];
            res.get(i)[1] = Math.min(res.get(i)[1], res.get(i-1)[1] + d);
        }
        // Backward pass
        for (int i = m-2; i >= 0; --i) {
            int d = res.get(i+1)[0] - res.get(i)[0];
            res.get(i)[1] = Math.min(res.get(i)[1], res.get(i+1)[1] + d);
        }
        int ans = 0;
        for (int i = 1; i < m; ++i) {
            int left = res.get(i-1)[0], h1 = res.get(i-1)[1];
            int right = res.get(i)[0], h2 = res.get(i)[1];
            int d = right - left;
            int peak = (h1 + h2 + d) / 2;
            ans = Math.max(ans, peak);
        }
        return ans;
    }
}
      

var maxBuilding = function(n, restrictions) {
    restrictions.push([1, 0]);
    if (restrictions.length === 0 || restrictions[restrictions.length-1][0] !== n)
        restrictions.push([n, n-1]);
    restrictions.sort((a, b) => a[0] - b[0]);
    let m = restrictions.length;
    // Forward pass
    for (let i = 1; i < m; ++i) {
        let d = restrictions[i][0] - restrictions[i-1][0];
        restrictions[i][1] = Math.min(restrictions[i][1], restrictions[i-1][1] + d);
    }
    // Backward pass
    for (let i = m-2; i >= 0; --i) {
        let d = restrictions[i+1][0] - restrictions[i][0];
        restrictions[i][1] = Math.min(restrictions[i][1], restrictions[i+1][1] + d);
    }
    let ans = 0;
    for (let i = 1; i < m; ++i) {
        let left = restrictions[i-1][0], h1 = restrictions[i-1][1];
        let right = restrictions[i][0], h2 = restrictions[i][1];
        let d = right - left;
        let peak = Math.floor((h1 + h2 + d) / 2);
        ans = Math.max(ans, peak);
    }
    return ans;
};