Maximum Building Height

You are given n buildings in a row (1-indexed). Building 1 must have height 0, and adjacent buildings can differ in height by at most 1. Some buildings have maximum height restrictions. What is the tallest building you can construct?

This is LeetCode 1840: Maximum Building Height, a hard problem that looks like it might need dynamic programming or binary search but actually reduces to a clean three-phase greedy approach: sort the restrictions, propagate limits in both directions, then compute the peak between each consecutive pair.

Why this problem matters

Maximum Building Height is a great example of bidirectional constraint propagation. Each building's height depends on its neighbors in both directions, and the restrictions create hard ceilings at specific positions. Trying to figure out all heights in a single pass fails because a restriction to the right can retroactively limit buildings to the left.

The two-pass propagation technique here is the same pattern behind problems like Candy, Trapping Rain Water, and Product of Array Except Self. Once you recognize that bidirectional dependencies can be split into two independent linear passes, a whole class of problems becomes approachable.

The core observations

Three key observations make this problem tractable:

1. Building 1 is fixed at height 0. This gives you a known anchor on the left.
2. Between two restricted positions, heights can rise and fall freely (within the +/- 1 rule). The tallest building between two restricted positions forms a "tent" that peaks somewhere in the middle.
3. Restrictions interact. A restriction at position p with max height h also limits buildings near p. Specifically, a building at distance d from p can be at most h + d. Two restrictions can tighten each other.

The algorithm

Here is the plan:

1. Sort restrictions by position. Add sentinels: (1, 0) for the fixed starting building and (n, n - 1) as a loose upper bound for the last building.
2. Left-to-right pass. For each consecutive pair of restrictions, the right one's effective limit is min(its own limit, left limit + gap) where gap is the distance between positions.
3. Right-to-left pass. Same idea in reverse: min(its own limit, right limit + gap).
4. Peak computation. Between each consecutive pair (pos_a, h_a) and (pos_b, h_b), the tallest achievable building is (h_a + h_b + (pos_b - pos_a)) // 2. Track the maximum across all pairs.

The peak formula comes from the fact that if you start at height h_a and increase by 1 per step going right, and start at height h_b and increase by 1 per step going left, the two slopes meet at the midpoint. The integer division handles the case where the gap is odd.

Walking through it step by step

Let's trace through n = 6, restrictions = [[2, 1], [5, 2]]. The answer is 3.

After sorting and adding sentinels, you have four restricted points. The left pass ensures no building exceeds what its left neighbor allows. The right pass does the same from the other direction. Then between each pair, you compute where the "tent" peaks. The tallest tent reaches height 3, which is the answer.

The solution

def maxBuilding(n, restrictions):
    restrictions.append([1, 0])
    restrictions.append([n, n - 1])
    restrictions.sort()

    m = len(restrictions)

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

    for i in range(m - 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
    for i in range(1, m):
        pos_a, h_a = restrictions[i - 1]
        pos_b, h_b = restrictions[i]
        peak = (h_a + h_b + (pos_b - pos_a)) // 2
        ans = max(ans, peak)

    return ans

Here is what each piece does:

1. Add sentinels. Building 1 must be height 0. Building n has no restriction beyond n - 1 (the maximum possible height if you climb 1 per step from building 1).
2. Sort by position. This lets you process restrictions in order and reason about the gap between consecutive ones.
3. Left-to-right pass. Each restriction's effective limit cannot exceed the previous restriction's limit plus the number of steps between them. This catches cases where a tight restriction to the left constrains what you can build further right.
4. Right-to-left pass. Same logic in reverse. A tight restriction to the right constrains what you can build further left.
5. Peak computation. Between any two consecutive restricted positions, the best you can do is build up from both sides and meet in the middle. The formula (h_a + h_b + gap) // 2 gives the peak height of that tent.

Why integer division handles odd gaps correctly

If positions are 3 apart and heights are h_a = 1 and h_b = 1, you have buildings at three positions. Starting from the left: 1, 2, 1. The peak is 2. The formula gives (1 + 1 + 3) // 2 = 2. If the gap were 4 with the same heights: 1, 2, 3, 2, 1. Peak is 3. Formula: (1 + 1 + 4) // 2 = 3. The floor division naturally handles the symmetry.

Complexity analysis

The two propagation passes and the peak computation are each O(m). Since m can be at most n, and sorting is O(m log m), that is the bottleneck. For all practical purposes this is efficient: m is bounded by the number of restrictions given, which is typically much smaller than n.

Building blocks

This problem is built on three reusable patterns that show up across many LeetCode problems.

1. Sorting as preprocessing

When constraints reference specific positions, sorting them by position turns a scattered set of constraints into a sequential chain. This is the same idea behind problems like Merge Intervals, Non-overlapping Intervals, and Meeting Rooms. Once sorted, you can process constraints in a single linear pass instead of searching for neighbors.

2. Two-pass propagation

The forward-backward pattern of propagating limits from both directions:

for i in range(1, m):
    limit[i] = min(limit[i], limit[i - 1] + gap)

for i in range(m - 2, -1, -1):
    limit[i] = min(limit[i], limit[i + 1] + gap)

This is the same skeleton used in Candy (propagate candy counts) and Trapping Rain Water (propagate max heights). Whenever each element depends on neighbors in both directions, splitting the work into two passes avoids circular dependencies.

3. Peak between two constrained points

The formula (h_a + h_b + gap) // 2 computes the maximum height achievable between two fixed endpoints when adjacent values can differ by at most 1. Think of it as two slopes meeting. This is a math observation that comes up in geometry and optimization problems involving linear constraints.

Edge cases

Before submitting, make sure your solution handles these:

• No restrictions. The only constraint is building 1 at height 0. You can build up to height n - 1 at position n. The sentinels handle this automatically.
• Single restriction at position n. The restriction may cap the last building below n - 1. The propagation handles it.
• Restriction of 0 at some position. This creates a valley. Buildings on both sides must slope down to 0. The two-pass propagation correctly limits neighbors.
• Two adjacent restrictions with incompatible heights. For example, positions 3 and 4 with max heights 5 and 1. The left pass sets position 4's limit to min(1, 5 + 1) = 1. The right pass sets position 3's limit to min(5, 1 + 1) = 2. The propagation resolves the conflict.
• Restriction at position 1. Must be 0 (since building 1 is always 0). If the restriction says 0, no conflict. If it says something higher, the sentinel (1, 0) overrides it.

From understanding to recall

You have read the solution and the logic makes sense. Sort, propagate left, propagate right, compute peaks. But can you write it from scratch in an interview without looking at it?

The details matter: remembering to add both sentinels, using min (not max) in the propagation passes, and getting the peak formula (h_a + h_b + gap) // 2 right with integer division. These are small but critical, and they slip away under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the two-pass propagation and peak computation from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "bidirectional constraints with a peak between endpoints" and the code flows out without hesitation.

The two-pass propagation pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Candy - Another hard problem solved with two-pass constraint propagation from both directions
• Trapping Rain Water - The classic forward-backward problem where each position depends on information from both sides
• Gas Station - A greedy problem where sorting and single-pass reasoning replace brute-force simulation

CodeBricks breaks the Maximum Building Height problem into its sorting, two-pass propagation, and peak computation building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a constraint propagation question shows up in your interview, you do not think about it. You just write it.