1840. Maximum Building Height

Time: O(k log k)

Space: O(k)

Problem Overview

Buildings sit on positions 1..n.

Intuition

Buildings sit on positions 1..n. Height can change by at most 1 per step, and position 1 starts at height 0 — so position i can never exceed i − 1 without restrictions. Each restriction [id, height] caps that position. After adding sentinels at (1, 0) and (n, n − 1), propagate caps left-to-right and right-to-left so neighboring limits are consistent with the slope-1 rule. The maximum height between two consecutive caps is the peak of the best “mountain” that fits between them.

Algorithm

1Append sentinels [1, 0] and [n, n − 1] to restrictions; sort by position then height.
2Forward: for i = 1..end, set cap[i] = min(cap[i], cap[i−1] + position[i] − position[i−1]).
3Backward: for i = end−1..0, set cap[i] = min(cap[i], cap[i+1] + position[i+1] − position[i]).
4For each adjacent pair (l, hL) and (r, hR), update ans with max(hL, hR) + (r − l − |hL − hR|) / 2.
5Return ans.

Example Walkthrough

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

1.Sentinels → (1,0), (2,1), (4,1), (5,4). Forward/backward passes keep caps (1,0), (2,1), (4,1), (5,2).
2.Segment 1→2: max(0,1) + (1 − 1)/2 = 1.
3.Segment 2→4: max(1,1) + (2 − 0)/2 = 2.
4.Segment 4→5: max(1,2) + (1 − 1)/2 = 2.

Output: 2

Common Pitfalls

•Include sentinel at position 1 with height 0 — the problem starts there.
•Position n is capped at n − 1 by the slope rule even without user restrictions.
•Integer division in the peak formula — (r − l − |hL − hR|) must be even when caps are feasible.

1840.cs

// Approach: Add sentinel restrictions at (1, 0) and (n, n-1), then sort by position.
// Forward pass: each cap is tightened by the left neighbor — height[i] <= height[i-1] + distance.
// Backward pass: tighten from the right the same way.
// Between consecutive caps, max height is max(hL, hR) + (dist - |hL - hR|) / 2 (best peak under slope-1 constraint).
// Time: O(k log k) Space: O(k)
public class Solution
{
    public int MaxBuilding(int n, int[][] restrictions)
    {
        int k = restrictions.Length;
        int[][] A = new int[k + 2][];
        Array.Copy(restrictions, A, k);
        A[k] = new int[] { 1, 0 };
        A[k + 1] = new int[] { n, n - 1 };

        A = A.OrderBy(a => a[0]).ThenBy(a => a[1]).ToArray();

        for (int i = 1; i < A.Length; ++i)
        {
            int dist = A[i][0] - A[i - 1][0];
            A[i][1] = Math.Min(A[i][1], A[i - 1][1] + dist);
        }

        for (int i = A.Length - 2; i >= 0; --i)
        {
            int dist = A[i + 1][0] - A[i][0];
            A[i][1] = Math.Min(A[i][1], A[i + 1][1] + dist);
        }

        int ans = 0;

        for (int i = 1; i < A.Length; ++i)
        {
            int l = A[i - 1][0];
            int r = A[i][0];
            int hL = A[i - 1][1];
            int hR = A[i][1];
            ans = Math.Max(ans, Math.Max(hL, hR) + (r - l - Math.Abs(hL - hR)) / 2);
        }

        return ans;
    }
}

Was this solution helpful?