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:
0.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 <= 1090 <= restrictions.length <= min(n - 1, 105)2 <= idi <= nidi is unique.0 <= maxHeighti <= 109Problem 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.
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.
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.
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.
JavaScript
Java
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.
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Divide and Conquer Approach | Time Complexity: O(n log n) as it divides the array into halves and combines them in linear time. |
| Iterative In-Place Sorting | Time Complexity: O(n^2) in the average and worst case scenarios, when the array is not sorted or reversed. |
| Sorting + Mathematics | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Divide and Conquer | O(m log m) | O(m) | Useful when reasoning about independent segments and recursive constraint splitting |
| Iterative In-Place Sorting with Constraint Propagation | O(m log m) | O(1) | Best general solution; easy to implement and commonly expected in interviews |
LeetCode 1840. Maximum Building Height • Happy Coding • 1,861 views views
Watch 6 more video solutions →Practice Maximum Building Height with our built-in code editor and test cases.
Practice on FleetCode