Skip to main content
Talentd

Maximum Building Height - Solution & Explanation

HardArrayMathSorting15 min readAsked at: Amazon, Microsoft, Meta +3
Practice this problem

Problem Statement

You want to build n new buildings in a city. The new buildings will be built in a line and are labeled from 1 to n.

However, there are city restrictions on the heights of the new buildings:

  • The height of each building must be a non-negative integer.
  • The height of the first building must be 0.
  • The height difference between any two adjacent buildings cannot exceed 1.

Additionally, there are city restrictions on the maximum height of specific buildings. These restrictions are given as a 2D integer array restrictions where restrictions[i] = [idi, maxHeighti] indicates that building idi must have a height less than or equal to maxHeighti.

It is guaranteed that each building will appear at most once in restrictions, and building 1 will not be in restrictions.

Return the maximum possible height of the tallest building.

 

Example 1:

Input: n = 5, restrictions = [[2,1],[4,1]]
Output: 2
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,1,2], and the tallest building has a height of 2.

Example 2:

Input: n = 6, restrictions = []
Output: 5
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,3,4,5], and the tallest building has a height of 5.

Example 3:

Input: n = 10, restrictions = [[5,3],[2,5],[7,4],[10,3]]
Output: 5
Explanation: The green area in the image indicates the maximum allowed height for each building.
We can build the buildings with heights [0,1,2,3,3,4,4,5,4,3], and the tallest building has a height of 5.

 

Constraints:

  • 2 <= n <= 109
  • 0 <= restrictions.length <= min(n - 1, 105)
  • 2 <= idi <= n
  • idi is unique.
  • 0 <= maxHeighti <= 109

Approach Overview

Problem Overview: You are given n buildings in a row where adjacent buildings can differ in height by at most 1. Some buildings also have maximum height restrictions. The task is to determine the highest possible building that can exist while satisfying all restrictions.

Approach 1: Divide and Conquer Approach (O(m log m) time, O(m) space)

This strategy treats the restrictions as boundary constraints and recursively evaluates the maximum possible peak between them. First, sort the restriction list by building index and add implicit constraints such as building 1 with height 0. During recursion, split the range between two restriction points and compute the highest peak allowed using the slope constraint |h[i] - h[i-1]| ≤ 1. The midpoint height is limited by both boundaries, so the peak becomes (leftHeight + rightHeight + distance) / 2. Recursively evaluating segments ensures the height never violates neighboring limits. Time complexity is O(m log m) due to sorting and divide steps, while auxiliary recursion storage uses O(m) space. This approach highlights the mathematical structure of the problem and works well when reasoning about independent segments.

Approach 2: Iterative In-Place Sorting (O(m log m) time, O(1) extra space)

The practical solution most engineers implement starts by sorting restrictions by building index. Add a base restriction (1, 0) and optionally (n, n-1) to cap the final building. Then perform two constraint passes. The left-to-right pass ensures every restriction respects the maximum slope from the previous one: h[i] = min(h[i], h[i-1] + distance). The right-to-left pass enforces the same constraint from the opposite direction. After normalization, each pair of adjacent restrictions defines a segment where the height increases then decreases like a pyramid. The highest peak between them is computed using the same midpoint formula based on distance and boundary heights. Iterate through all segments and track the maximum. Sorting dominates the complexity at O(m log m), and the algorithm runs in O(1) additional space when updates are done in place.

Both solutions rely heavily on reasoning about ordered constraints, which is why understanding sorting and boundary propagation in arrays is critical. The peak calculation itself comes from simple math around linear growth and symmetric slopes.

Recommended for interviews: The iterative sorted approach is what most interviewers expect. It shows you can normalize constraints with forward and backward passes and derive the peak mathematically. Mentioning a divide-and-conquer perspective demonstrates deeper understanding, but the sorted propagation solution is simpler to implement and easier to reason about under interview pressure.

Approach 1: Divide and Conquer Approach

This approach involves breaking down the problem into smaller subproblems, solving each subproblem independently, and then combining their results to solve the original problem. It is particularly useful when the problem has a recursive subproblem structure.

This C code implements the Merge Sort algorithm using a divide-and-conquer approach. First, the array is split into two halves, sorted independently, and then merged together. The merge operation combines these halves in a sorted manner.

Code

CPython

C

Python

Complexity

Time Complexity: O(n log n) as it divides the array into halves and combines them in linear time.
Space Complexity: O(n) due to the temporary arrays used during merging.

Try this approach in the editor →

Approach 2: Iterative In-Place Sorting

This approach involves using an iterative sorting algorithm that operates directly on the array without requiring additional auxiliary space. The Insertion Sort algorithm is a classic example of such an algorithm.

In this JavaScript implementation of Insertion Sort, the algorithm iteratively builds the sorted array by inserting each item into its proper place. By shifting elements to the right, it preserves order and operates entirely within the given array space.

Code

JavaScriptJava

JavaScript

Java

Complexity

Time Complexity: O(n^2) in the average and worst case scenarios, when the array is not sorted or reversed.
Space Complexity: O(1) as it uses no additional arrays for insertion.

Try this approach in the editor →

Approach 3: Sorting + Mathematics

First, we sort all the constraints by the building number in ascending order.

Then we traverse all the constraints from left to right. For each constraint, we can get an upper bound on the maximum height, i.e., r_i[1] = min(r_i[1], r_{i-1}[1] + r_i[0] - r_{i-1}[0]), where r_i represents the i-th constraint, and r_i[0] and r_i[1] represent the building number and the upper bound on the maximum height of the building, respectively.

Next, we traverse all the constraints from right to left. For each constraint, we can get an upper bound on the maximum height, i.e., r_i[1] = min(r_i[1], r_{i+1}[1] + r_{i+1}[0] - r_i[0]).

In this way, we obtain the upper bound on the maximum height for each constrained building.

The problem asks for the height of the tallest building. We can enumerate the buildings between two adjacent constraints i and i+1. To maximize the height, the height should first increase and then decrease. Suppose the maximum height is t, then t - r_i[1] + t - r_{i+1}[1] leq r_{i+1}[0] - r_i[0], i.e., t leq \frac{r_i[1] + r_{i+1}[1] + r_{i+1}[0] - r_{i}[0]}{2}. We take the maximum value of all such t.

The time complexity is O(m times log m), and the space complexity is O(m). Here, m is the number of constraints.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Divide and Conquer Approach

Time Complexity: O(n log n) as it divides the array into halves and combines them in linear time.
Space Complexity: O(n) due to the temporary arrays used during merging.

Iterative In-Place Sorting

Time Complexity: O(n^2) in the average and worst case scenarios, when the array is not sorted or reversed.
Space Complexity: O(1) as it uses no additional arrays for insertion.

Sorting + Mathematics—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Divide and ConquerO(m log m)O(m)Useful when reasoning about independent segments and recursive constraint splitting
Iterative In-Place Sorting with Constraint PropagationO(m log m)O(1)Best general solution; easy to implement and commonly expected in interviews

Video Solution

Maximum Building Height | Detailed For Beginners | Dry Runs | Leetcode 1840 | codestorywithMIK • codestorywithMIK • 8,123 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximum Building Height easy or hard?
Maximum Building Height is classified as a Hard problem on LeetCode. The difficulty comes from recognizing that restrictions must be normalized first and that the maximum height appears between restriction boundaries rather than at the restricted buildings themselves.
Maximum Building Height Python/Java solution
Python and Java implementations typically follow the same pattern: sort the restrictions, add boundary constraints, run two passes to enforce slope limits, and then compute the maximum peak between consecutive restrictions. The logic remains identical across languages with O(m log m) time complexity.
How to solve Maximum Building Height in O(n)?
A strictly O(n) solution is not typical because restrictions must be processed in sorted order of building index. However, once the restrictions are sorted, all constraint propagation and peak calculations run in linear time. The main idea is to enforce slope limits in two passes and then compute the highest possible midpoint between each pair of restrictions.
What is the best approach for Maximum Building Height?
The most practical solution sorts all building restrictions and then propagates height constraints from left-to-right and right-to-left. After normalization, each adjacent restriction pair defines a segment where the maximum peak can be computed mathematically. This approach runs in O(m log m) time due to sorting and uses constant extra space.
Is Maximum Building Height asked at Google/Amazon/Meta?
Hard array and constraint-propagation problems like Maximum Building Height frequently appear in interviews at companies such as Google, Amazon, and Meta. They test reasoning about constraints, mathematical bounds, and careful iteration across sorted data.
What data structure is used in Maximum Building Height?
The core data structure is an array or list of restriction pairs. After sorting by building index, the algorithm iterates through the array to enforce height limits and compute segment peaks. No advanced structures like heaps or trees are required.
What is the time complexity of Maximum Building Height?
The optimal solution runs in O(m log m) time where m is the number of restrictions. Sorting the restriction list dominates the runtime, while the forward pass, backward pass, and peak calculations are all linear. Space complexity can be reduced to O(1) if updates are done in place.

Ready to solve this problem?

Practice Maximum Building Height with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Maximum Value in a Constrained Sequence