LeetCode 1840 - Maximum Building Height

This problem asks us to construct heights for n buildings arranged in a straight line while satisfying several constraints. Each building has a non-negative integer height. Building 1 must always have height 0.

leetcodehardarraymathsorting

LeetCode Problem 1840

Difficulty: 🔴 Hard
Topics: Array, Math, Sorting

Solution

LeetCode 1840 - Maximum Building Height

Problem Understanding

This problem asks us to construct heights for n buildings arranged in a straight line while satisfying several constraints.

Each building has a non-negative integer height. Building 1 must always have height 0. Additionally, adjacent buildings cannot differ in height by more than 1. This means that if one building has height h, the next building can only have height h - 1, h, or h + 1, assuming heights remain non-negative.

On top of these global constraints, some buildings have explicit upper bounds. The array restrictions contains pairs [id, maxHeight], meaning building id cannot exceed maxHeight.

The goal is not to construct the full height array explicitly. Instead, we only need to determine the maximum possible height that any building can achieve while satisfying all constraints.

The input size is large:

  • n can be as large as 10^9
  • restrictions.length can be as large as 10^5

The enormous value of n immediately tells us that we cannot simulate all buildings one by one. Any solution depending on iterating through every building position would be too slow.

The important observation is that only restricted buildings matter directly. Between restricted positions, the height changes are governed entirely by the slope constraint of at most 1 per step.

Several edge cases are important:

  • There may be no restrictions at all. In that case, the tallest building is simply n - 1, because heights can increase by 1 starting from building 1.
  • Restrictions may be inconsistent unless adjusted. For example, if one building is forced very low, nearby restrictions may also need to be reduced.
  • The last building may not appear in the restrictions array. We must still account for it.
  • Restrictions can appear in arbitrary order, so sorting is required.

Approaches

Brute Force Approach

A brute force strategy would attempt to assign heights to every building while respecting all constraints.

One possibility would be:

  1. Initialize all buildings with their maximum feasible heights.
  2. Propagate constraints left and right repeatedly until all adjacent differences are at most 1.
  3. Track the maximum resulting height.

This approach is correct because eventually all constraints become satisfied through repeated relaxation.

However, it is completely impractical for the given constraints. Since n can reach 10^9, even storing all building heights is impossible.

The brute force idea fails because it treats every building individually, while the real structure of the problem depends only on restriction boundaries.

Optimal Approach

The key insight is that only restricted buildings matter.

Suppose we know the maximum allowed heights at two positions:

  • (x1, h1)
  • (x2, h2)

Because adjacent heights can differ by at most 1, the feasible height profile between them forms a "mountain" shape.

The tallest achievable point between these positions depends only on:

  • the distance between them
  • the endpoint height limits

This transforms the problem into constraint propagation between restricted positions.

The algorithm works in three phases:

  1. Add implicit restrictions:
  • building 1 has height 0
  • building n can initially be at most n - 1
  1. Sort restrictions by position.
  2. Perform:
  • a left-to-right pass
  • a right-to-left pass

These passes tighten all restriction heights so they become mutually consistent.

After that, each neighboring restriction pair independently determines the tallest achievable peak between them.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) or worse O(n) Impossible for large n
Optimal O(m log m) O(m) m = restrictions.length, uses sorting and constraint propagation

Algorithm Walkthrough

Step 1: Add implicit restrictions

Building 1 must always have height 0, so we add:

[1, 0]

If building n is not already restricted, we add:

[n, n - 1]

Why n - 1?

Starting from building 1 at height 0, the largest possible height increase over n - 1 steps is exactly n - 1.

This gives a natural upper bound for the last building.

Step 2: Sort restrictions

We sort all restrictions by building index.

This allows us to process neighboring restrictions efficiently.

Suppose after sorting we have:

[id1, h1], [id2, h2]

The distance between them is:

d = id2 - id1

Because heights can change by at most 1 per step:

h2 <= h1 + d

and similarly:

h1 <= h2 + d

These inequalities define feasible relationships between neighboring restrictions.

Step 3: Left-to-right constraint propagation

We scan from left to right.

For each restriction:

currentHeight = min(currentHeight, previousHeight + distance)

This ensures that the current restriction is reachable from the previous one.

Without this pass, some restrictions could demand impossible jumps upward.

Step 4: Right-to-left constraint propagation

We now scan from right to left.

For each restriction:

currentHeight = min(currentHeight, nextHeight + distance)

This ensures feasibility from the opposite direction.

Together, the two passes guarantee global consistency.

Step 5: Compute maximum peak between restrictions

Now consider two neighboring restrictions:

(x1, h1)
(x2, h2)

Let:

d = x2 - x1

The tallest possible peak occurs when we increase from the lower side as much as possible before descending toward the other endpoint.

The maximum achievable height is:

(h1 + h2 + d) // 2

This formula comes from balancing the ascent and descent slopes.

We compute this value for every adjacent pair and take the maximum.

Why it works

After the two propagation passes, every restriction becomes globally feasible. That means any adjacent restriction pair can be connected using valid slopes.

Between two feasible endpoints, the optimal strategy for maximizing height is always to climb as high as possible before descending. Because the slope limit is 1, the tallest achievable point is exactly the midpoint balancing formula:

(h1 + h2 + d) // 2

Taking the maximum over all neighboring intervals therefore gives the tallest achievable building overall.

Python Solution

from typing import List

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        restrictions.append([1, 0])

        has_last = False
        for building_id, _ in restrictions:
            if building_id == n:
                has_last = True
                break

        if not has_last:
            restrictions.append([n, n - 1])

        restrictions.sort()

        # Left-to-right pass
        for i in range(1, len(restrictions)):
            prev_id, prev_height = restrictions[i - 1]
            curr_id, curr_height = restrictions[i]

            max_allowed = prev_height + (curr_id - prev_id)
            restrictions[i][1] = min(curr_height, max_allowed)

        # Right-to-left pass
        for i in range(len(restrictions) - 2, -1, -1):
            next_id, next_height = restrictions[i + 1]
            curr_id, curr_height = restrictions[i]

            max_allowed = next_height + (next_id - curr_id)
            restrictions[i][1] = min(curr_height, max_allowed)

        answer = 0

        # Compute best peak between adjacent restrictions
        for i in range(1, len(restrictions)):
            left_id, left_height = restrictions[i - 1]
            right_id, right_height = restrictions[i]

            distance = right_id - left_id

            peak = (left_height + right_height + distance) // 2
            answer = max(answer, peak)

        return answer

The implementation begins by inserting the mandatory restriction [1, 0].

Next, it ensures that building n has an explicit restriction. Even though the problem may not provide one, adding [n, n - 1] simplifies later processing because every interval now has a defined endpoint.

The restrictions are then sorted by building position.

The left-to-right pass enforces that each restriction can be reached from the previous restriction under the slope constraint. If a restriction is too high, it gets reduced.

The right-to-left pass performs the symmetric adjustment from the opposite direction.

At this point, all restrictions are globally feasible.

Finally, the algorithm examines each neighboring pair and computes the tallest achievable peak between them using the midpoint formula.

The maximum over all intervals is returned.

Go Solution

package main

import "sort"

func maxBuilding(n int, restrictions [][]int) int {
	restrictions = append(restrictions, []int{1, 0})

	hasLast := false
	for _, r := range restrictions {
		if r[0] == n {
			hasLast = true
			break
		}
	}

	if !hasLast {
		restrictions = append(restrictions, []int{n, n - 1})
	}

	sort.Slice(restrictions, func(i, j int) bool {
		return restrictions[i][0] < restrictions[j][0]
	})

	// Left-to-right pass
	for i := 1; i < len(restrictions); i++ {
		prevID := restrictions[i-1][0]
		prevHeight := restrictions[i-1][1]

		currID := restrictions[i][0]
		currHeight := restrictions[i][1]

		maxAllowed := prevHeight + (currID - prevID)

		if currHeight > maxAllowed {
			restrictions[i][1] = maxAllowed
		}
	}

	// Right-to-left pass
	for i := len(restrictions) - 2; i >= 0; i-- {
		nextID := restrictions[i+1][0]
		nextHeight := restrictions[i+1][1]

		currID := restrictions[i][0]
		currHeight := restrictions[i][1]

		maxAllowed := nextHeight + (nextID - currID)

		if currHeight > maxAllowed {
			restrictions[i][1] = maxAllowed
		}
	}

	answer := 0

	for i := 1; i < len(restrictions); i++ {
		leftID := restrictions[i-1][0]
		leftHeight := restrictions[i-1][1]

		rightID := restrictions[i][0]
		rightHeight := restrictions[i][1]

		distance := rightID - leftID

		peak := (leftHeight + rightHeight + distance) / 2

		if peak > answer {
			answer = peak
		}
	}

	return answer
}

The Go implementation follows the exact same algorithmic structure as the Python version.

The primary difference is the use of sort.Slice for sorting the restrictions.

Go slices are modified in place, so updating restriction heights directly changes the underlying data structure without extra copying.

Integer overflow is not a concern because the maximum possible values remain comfortably within Go's 64-bit integer range on modern systems, and LeetCode's int type is sufficient for these constraints.

Worked Examples

Example 1

Input:

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

Step 1: Add implicit restrictions

[[2,1],[4,1],[1,0],[5,4]]

Step 2: Sort

Index Restriction
0 [1,0]
1 [2,1]
2 [4,1]
3 [5,4]

Step 3: Left-to-right pass

Current Previous Max Allowed Updated
[2,1] [1,0] 1 [2,1]
[4,1] [2,1] 3 [4,1]
[5,4] [4,1] 2 [5,2]

Result:

[[1,0],[2,1],[4,1],[5,2]]

Step 4: Right-to-left pass

No further reductions occur.

Step 5: Compute peaks

Interval Formula Peak
[1,0] to [2,1] (0 + 1 + 1) // 2 1
[2,1] to [4,1] (1 + 1 + 2) // 2 2
[4,1] to [5,2] (1 + 2 + 1) // 2 2

Answer:

2

Example 2

Input:

n = 6
restrictions = []

Step 1: Add implicit restrictions

[[1,0],[6,5]]

Step 2: Left-to-right pass

No reductions needed.

Step 3: Right-to-left pass

No reductions needed.

Step 4: Compute peak

Interval Formula Peak
[1,0] to [6,5] (0 + 5 + 5) // 2 5

Answer:

5

Example 3

Input:

n = 10
restrictions = [[5,3],[2,5],[7,4],[10,3]]

Step 1: Add implicit restriction

[[1,0],[2,5],[5,3],[7,4],[10,3]]

Step 2: Sort

Index Restriction
0 [1,0]
1 [2,5]
2 [5,3]
3 [7,4]
4 [10,3]

Step 3: Left-to-right pass

Restriction Updated Height
[2,5] 1
[5,3] 3
[7,4] 4
[10,3] 3

Result:

[[1,0],[2,1],[5,3],[7,4],[10,3]]

Step 4: Right-to-left pass

No further changes.

Step 5: Compute peaks

Interval Peak
[1,0] to [2,1] 1
[2,1] to [5,3] 3
[5,3] to [7,4] 4
[7,4] to [10,3] 5

Answer:

5

Complexity Analysis

Measure Complexity Explanation
Time O(m log m) Sorting dominates the runtime
Space O(m) Stores all restrictions including added boundaries

Here, m is the number of restrictions.

The two propagation passes and the final peak computation are all linear in the number of restrictions. The only non-linear operation is sorting.

The algorithm never depends on n directly, which is critical because n may be as large as 10^9.

Test Cases

from typing import List

class Solution:
    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
        restrictions.append([1, 0])

        has_last = False
        for building_id, _ in restrictions:
            if building_id == n:
                has_last = True
                break

        if not has_last:
            restrictions.append([n, n - 1])

        restrictions.sort()

        for i in range(1, len(restrictions)):
            prev_id, prev_height = restrictions[i - 1]
            curr_id, curr_height = restrictions[i]

            restrictions[i][1] = min(
                curr_height,
                prev_height + (curr_id - prev_id)
            )

        for i in range(len(restrictions) - 2, -1, -1):
            next_id, next_height = restrictions[i + 1]
            curr_id, curr_height = restrictions[i]

            restrictions[i][1] = min(
                curr_height,
                next_height + (next_id - curr_id)
            )

        answer = 0

        for i in range(1, len(restrictions)):
            left_id, left_height = restrictions[i - 1]
            right_id, right_height = restrictions[i]

            distance = right_id - left_id

            peak = (left_height + right_height + distance) // 2
            answer = max(answer, peak)

        return answer

sol = Solution()

assert sol.maxBuilding(5, [[2,1],[4,1]]) == 2
# Basic example with two restrictions

assert sol.maxBuilding(6, []) == 5
# No restrictions, pure increasing sequence

assert sol.maxBuilding(10, [[5,3],[2,5],[7,4],[10,3]]) == 5
# Example with multiple interacting restrictions

assert sol.maxBuilding(2, []) == 1
# Smallest valid n

assert sol.maxBuilding(5, [[5,0]]) == 2
# Last building forced low

assert sol.maxBuilding(10, [[2,1]]) == 9
# Early restriction does not prevent later growth

assert sol.maxBuilding(10, [[2,0]]) == 7
# Immediate flattening then growth

assert sol.maxBuilding(10, [[3,0],[8,0]]) == 2
# Valley between strict zero-height restrictions

assert sol.maxBuilding(1000000000, []) == 999999999
# Maximum n without restrictions

assert sol.maxBuilding(10, [[4,2],[7,2]]) == 4
# Symmetric restriction interval
Test Why
n=5, [[2,1],[4,1]] Validates standard restricted growth
n=6, [] Validates unrestricted increasing heights
n=10, [[5,3],[2,5],[7,4],[10,3]] Tests propagation in both directions
n=2, [] Smallest possible input
n=5, [[5,0]] Ensures low final restriction propagates backward
n=10, [[2,1]] Tests large unrestricted suffix
n=10, [[2,0]] Tests forced flat start
n=10, [[3,0],[8,0]] Tests narrow feasible mountain
n=1000000000, [] Confirms algorithm does not depend on n
n=10, [[4,2],[7,2]] Tests balanced interval peak calculation

Edge Cases

One important edge case occurs when there are no restrictions at all. A naive implementation might incorrectly return 0 or fail because no intervals exist. The correct behavior is that heights can increase by 1 starting from building 1, producing a tallest height of n - 1. The implementation handles this by explicitly adding [1,0] and [n,n-1].

Another tricky case happens when restrictions are initially inconsistent. For example:

[[2,0],[5,10]]

The restriction at building 5 cannot actually reach height 10 because there are only three steps between buildings 2 and 5. The left-to-right propagation pass automatically reduces impossible heights to their maximum feasible values.

A third important edge case occurs when the tallest point lies between restrictions rather than directly on one. Many incorrect solutions only examine restricted buildings themselves. However, the actual maximum may appear in the middle of an interval where the height rises and then falls. The midpoint formula correctly computes this hidden peak.

Another subtle case is when the final building already appears in the restriction list. The implementation avoids adding a duplicate restriction for building n, preventing incorrect interval calculations or duplicated processing.