Watch 7 video solutions for Maximum Building Height, a hard level problem involving Array, Math, Sorting. This walkthrough by Happy Coding has 1,861 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |