1840. Maximum Building Height

Array
Math
Greedy

TIME

O(r log r)

SPACE

O(r)

Intuition

Because adjacent buildings can differ by at most 1, the height at a building is bounded by how far it is from any fixed-height constraint. Each restricted building acts as a "checkpoint": the height anywhere can rise or fall at most 1 per step away from a checkpoint.

Once all checkpoints have their true effective caps (after propagating constraints in both directions), the highest point achievable between any two consecutive checkpoints is determined purely by climbing from both ends and meeting in the middle.

Approach

Anchor: add [1, 0] to the restrictions (building 1 is always 0) and sort by building id.
Forward pass: propagate the left-side reachability cap to each checkpoint:
```
h[i] = min(h[i], h[i-1] + (id[i] - id[i-1]))
```

Backward pass: propagate from the right:

h[i] = min(h[i], h[i+1] + (id[i+1] - id[i]))

Peak between consecutive checkpoints (id1, h1) and (id2, h2): climb from both sides and meet at the top:
```
peak = (h1 + h2 + (id2 - id1)) // 2
```
Tail from the last checkpoint to building n (no upper bound on the right):
```
last_h + (n - last_id)
```
Return the maximum over all peaks and the tail.

Complexity

Time: O(r log r), sorting the r restrictions; passes are O(r)
Space: O(r), the sorted restriction list

Edge Cases

No restrictions -> only [1, 0] anchor; answer is n - 1
Last restriction is on building n -> tail contributes 0 beyond the last checkpoint
h1 + h2 + gap can reach ~3 × 10^9, use 64-bit integers in Java for this intermediate value
Restriction cap higher than reachable height -> forward pass trims it to the true reachable value

Code

from typing import List


class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        """
        1840. Maximum Building Height
        Time: O(r log r)
        Space: O(r)
        """
        restrictions.append([1, 0])
        restrictions.sort()
        r = len(restrictions)

        # Forward pass: each checkpoint is bounded by what's reachable from the left.
        for i in range(1, r):
            gap = restrictions[i][0] - restrictions[i - 1][0]
            restrictions[i][1] = min(restrictions[i][1], restrictions[i - 1][1] + gap)

        # Backward pass: each checkpoint is bounded by what's reachable from the right.
        for i in range(r - 2, -1, -1):
            gap = restrictions[i + 1][0] - restrictions[i][0]
            restrictions[i][1] = min(restrictions[i][1], restrictions[i + 1][1] + gap)

        ans = 0

        # Peak between every pair of consecutive checkpoints.
        for i in range(r - 1):
            id1, h1 = restrictions[i]
            id2, h2 = restrictions[i + 1]
            ans = max(ans, (h1 + h2 + (id2 - id1)) // 2)

        # Free climb from the last checkpoint to building n.
        last_id, last_h = restrictions[-1]
        ans = max(ans, last_h + (n - last_id))

        return ans

import java.util.Arrays;

/**
 * 1840. Maximum Building Height
 * Time: O(r log r)
 * Space: O(r)
 */
class Solution {
    public int maxBuilding(int n, int[][] restrictions) {
        // Append [1, 0] as the anchor, then sort by building id.
        int r = restrictions.length;
        int[][] pts = new int[r + 1][2];
        for (int i = 0; i < r; i++) {
            pts[i][0] = restrictions[i][0];
            pts[i][1] = restrictions[i][1];
        }
        pts[r][0] = 1;
        pts[r][1] = 0;
        Arrays.sort(pts, (a, b) -> a[0] - b[0]);
        int total = pts.length;

        // Forward pass.
        for (int i = 1; i < total; i++) {
            long gap = pts[i][0] - pts[i - 1][0];
            pts[i][1] = (int) Math.min(pts[i][1], pts[i - 1][1] + gap);
        }

        // Backward pass.
        for (int i = total - 2; i >= 0; i--) {
            long gap = pts[i + 1][0] - pts[i][0];
            pts[i][1] = (int) Math.min(pts[i][1], pts[i + 1][1] + gap);
        }

        long ans = 0;

        // Peak between consecutive checkpoints.
        for (int i = 0; i < total - 1; i++) {
            long h1 = pts[i][1], h2 = pts[i + 1][1];
            long gap = pts[i + 1][0] - pts[i][0];
            ans = Math.max(ans, (h1 + h2 + gap) / 2);
        }

        // Free climb from the last checkpoint to building n.
        long lastH = pts[total - 1][1];
        long lastId = pts[total - 1][0];
        ans = Math.max(ans, lastH + (n - lastId));

        return (int) ans;
    }
}