Maximum Building Height

Hard

#1682Time: O(n * k), where `n` is the number of buildings and `k` is the number of restrictions. Calculating the initial height bounds for `n` buildings against `k` restrictions takes O(n*k). The subsequent two passes take O(n).Space: O(n), where `n` is the number of buildings. This is required to store the height array for all buildings.1 company

Patterns

Algorithms

Data structures

Companies

Prompt

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] = [id_i, maxHeight_i] indicates that building id_i must have a height less than or equal to maxHeight_i.

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 <= 10⁹
0 <= restrictions.length <= min(n - 1, 10⁵)
2 <= id_i <= n
id_i is unique.
0 <= maxHeight_i <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

This approach calculates the maximum possible height for every single building from 1 to n. It first determines an initial upper bound for each building's height based on all restrictions. Then, it uses dynamic programming with two passes (one forward, one backward) over all n buildings to enforce the adjacency constraint (|h[i] - h[i-1]| <= 1). The final maximum height is the largest value in the resulting height array.

Algorithm

Initialize an array max_h of size n+1.
For i from 1 to n:
- Set max_h[i] = i - 1 (constraint from building 1).
- For each restriction [id, h] in restrictions:
  - Update max_h[i] = min(max_h[i], h + abs(i - id)).
Perform a forward pass. For i from 2 to n:
- max_h[i] = min(max_h[i], max_h[i-1] + 1).
Perform a backward pass. For i from n-1 down to 1:
- max_h[i] = min(max_h[i], max_h[i+1] + 1).
The result is the maximum value in the max_h array.

Walkthrough

First, we create an array max_h of size n+1 to store the maximum possible height for each building. We initialize max_h[i] for each building i by considering all restrictions. The height of building i is limited by its distance from building 1 (h[1]=0) and from every restricted building j.

h[i] <= h[1] + |i-1| = i-1.
h[i] <= maxHeight_j + |i - id_j| for each restriction j.

So, for each i from 1 to n, we calculate max_h[i] = min(i-1, min_j(restrictions[j][1] + |i - restrictions[j][0]|)). This step takes O(n*k) time.

The max_h array now holds upper bounds, but it might not represent a valid sequence of building heights because the adjacency rule might be violated (e.g., max_h[i] and max_h[i+1] could differ by more than 1).

To enforce the adjacency rule, we perform two passes:

Forward pass: Iterate from i = 2 to n. Update max_h[i] = min(max_h[i], max_h[i-1] + 1). This ensures that no building is too tall compared to its left neighbor.
Backward pass: Iterate from i = n-1 down to 1. Update max_h[i] = min(max_h[i], max_h[i+1] + 1). This ensures no building is too tall compared to its right neighbor.

After these two passes, the max_h array represents the highest possible valid height profile. The final answer is the maximum value in the max_h array.

1// This approach is too slow and will cause Time Limit Exceeded (TLE)2// due to n being up to 10^9. It's for conceptual understanding.3class Solution {4    public int maxBuilding(int n, int[][] restrictions) {5        if (n == 1) return 0;6        long[] max_h = new long[n + 1];7 8        // Initialize max_h with upper bounds from all restrictions9        for (int i = 1; i <= n; i++) {10            max_h[i] = (long)i - 1;11            for (int[] r : restrictions) {12                max_h[i] = Math.min(max_h[i], (long)r[1] + Math.abs(i - r[0]));13            }14        }15 16        // Forward pass to enforce adjacency from left17        for (int i = 2; i <= n; i++) {18            max_h[i] = Math.min(max_h[i], max_h[i - 1] + 1);19        }20 21        // Backward pass to enforce adjacency from right22        for (int i = n - 1; i >= 1; i--) {23            max_h[i] = Math.min(max_h[i], max_h[i + 1] + 1);24        }25 26        // Find the maximum height27        long tallest = 0;28        for (int i = 1; i <= n; i++) {29            tallest = Math.max(tallest, max_h[i]);30        }31        return (int) tallest;32    }33}

Complexity

Time

O(n * k), where `n` is the number of buildings and `k` is the number of restrictions. Calculating the initial height bounds for `n` buildings against `k` restrictions takes O(n*k). The subsequent two passes take O(n).

Space

O(n), where `n` is the number of buildings. This is required to store the height array for all buildings.

Trade-offs

Pros

Conceptually simple and directly models the problem's constraints.

Cons

The time complexity of O(n * k) is too slow given n can be up to 10<sup>9</sup>, which will lead to a 'Time Limit Exceeded' error.
The space complexity of O(n) is also too high and will cause a 'Memory Limit Exceeded' error for large n.

This approach avoids iterating through all n buildings. It recognizes that the maximum height profile is determined by the 'checkpoints' created by the restrictions. The core idea is to first calculate the tightest possible height limit at each restricted building, considering the influence of all other restrictions. This is done with two passes (forward and backward) over the sorted list of restrictions. Once these tightest limits are found, the maximum height of the entire city is calculated by finding the peak height in the 'tent' formed between each adjacent pair of restricted buildings.

Algorithm

Create a new list all_restrictions and add [1, 0] to it. Add all from the input restrictions.
Sort all_restrictions based on building IDs.
Forward Pass: For i from 1 to all_restrictions.size() - 1:
- r_i.maxHeight = min(r_i.maxHeight, r_{i-1}.maxHeight + (r_i.id - r_{i-1}.id)).
Backward Pass: For i from all_restrictions.size() - 2 down to 0:
- r_i.maxHeight = min(r_i.maxHeight, r_{i+1}.maxHeight + (r_{i+1}.id - r_i.id)).
Initialize max_h = 0.
For i from 0 to all_restrictions.size() - 2:
- Let (id1, h1) be restriction i and (id2, h2) be restriction i+1.
- Calculate the peak height in the segment: peak_h = (h1 + h2 + id2 - id1) / 2.
- Update max_h = max(max_h, peak_h).
Handle the last segment. Let (id_last, h_last) be the last restriction.
- last_segment_max = h_last + (n - id_last).
- max_h = max(max_h, last_segment_max).
Return max_h.

Walkthrough

The key observation is that the height of any building is only constrained by building 1 and the buildings with restrictions. The height profile between any two such 'checkpoints' will rise and then fall, forming a tent-like shape. The maximum height must occur either at one of the restricted buildings or at the peak of one of these tents.

The algorithm proceeds as follows:

Create a list of all checkpoints. This includes the given restrictions plus a mandatory checkpoint for the first building: [1, 0].
Sort this list of checkpoints by their building ID.
The initial maxHeight in the restrictions might not be achievable due to the adjacency rule and other restrictions. We need to tighten these bounds. This is done in two passes:
- Forward Pass: Iterate through the sorted checkpoints from left to right. For each checkpoint i, its height is limited by the height of the previous checkpoint i-1. The height at id_i cannot be more than the height at id_{i-1} plus the distance between them. So, we update maxHeight_i = min(maxHeight_i, maxHeight_{i-1} + (id_i - id_{i-1})).
- Backward Pass: Iterate from right to left. Similarly, the height at id_i is limited by the next checkpoint i+1. We update maxHeight_i = min(maxHeight_i, maxHeight_{i+1} + (id_{i+1} - id_i)).
After these two passes, we have the tightest possible maximum heights for each restricted building.
Now, we calculate the maximum possible height for the entire city. We iterate through adjacent pairs of checkpoints (id1, h1) and (id2, h2). The maximum height in the segment between them can be found at a peak. The height of this peak is floor((h1 + h2 + id2 - id1) / 2). We keep track of the maximum peak height found across all segments.
Finally, we must consider the segment after the last restriction (id_last, h_last) up to building n. The height can continue to increase by 1 for each building. The maximum height in this final segment will be at building n, with a height of h_last + (n - id_last).
The answer is the maximum of all calculated peak heights and the height of the last segment's end.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public int maxBuilding(int n, int[][] restrictions) {7        List<int[]> allRestrictions = new ArrayList<>();8        allRestrictions.add(new int[]{1, 0});9        for (int[] r : restrictions) {10            allRestrictions.add(r);11        }12        13        Collections.sort(allRestrictions, (a, b) -> Integer.compare(a[0], b[0]));14 15        // Forward pass to propagate constraints from left to right16        for (int i = 1; i < allRestrictions.size(); i++) {17            int[] prev = allRestrictions.get(i - 1);18            int[] curr = allRestrictions.get(i);19            curr[1] = Math.min(curr[1], prev[1] + (curr[0] - prev[0]));20        }21 22        // Backward pass to propagate constraints from right to left23        for (int i = allRestrictions.size() - 2; i >= 0; i--) {24            int[] curr = allRestrictions.get(i);25            int[] next = allRestrictions.get(i + 1);26            curr[1] = Math.min(curr[1], next[1] + (next[0] - curr[0]));27        }28 29        long max_h = 0;30        // Calculate max height between adjacent restrictions31        for (int i = 0; i < allRestrictions.size() - 1; i++) {32            long id1 = allRestrictions.get(i)[0];33            long h1 = allRestrictions.get(i)[1];34            long id2 = allRestrictions.get(i + 1)[0];35            long h2 = allRestrictions.get(i + 1)[1];36            37            // The peak height in the 'tent' between (id1, h1) and (id2, h2)38            long peak_h = (h1 + h2 + (id2 - id1)) / 2;39            max_h = Math.max(max_h, peak_h);40        }41 42        // Handle the last segment from the last restriction to n43        int[] lastRestriction = allRestrictions.get(allRestrictions.size() - 1);44        long last_segment_max = (long)lastRestriction[1] + (n - lastRestriction[0]);45        max_h = Math.max(max_h, last_segment_max);46 47        return (int) max_h;48    }49}

Complexity

Time

O(k log k), where `k` is the number of restrictions. Sorting the restrictions dominates the runtime. The two passes and the final calculation loop each take O(k).

Space

O(k), where `k` is the number of restrictions. This is required to store the list of all restrictions.

Trade-offs

Pros

Highly efficient. The complexity depends on the number of restrictions k, not n.
This makes it suitable for the given constraints where n is large but k is moderate.

Cons

The logic is more complex than the straightforward DP approach, involving insights about the problem's geometric structure.

Solutions

Solution

1class Solution {2public3  int maxBuilding(int n, int[][] restrictions) {4    List<int[]> r = new ArrayList<>();5    r.addAll(Arrays.asList(restrictions));6    r.add(new int[]{1, 0});7    Collections.sort(r, (a, b)->a[0] - b[0]);8    if (r.get(r.size() - 1)[0] != n) {9      r.add(new int[]{n, n - 1});10    }11    int m = r.size();12    for (int i = 1; i < m; ++i) {13      int[] a = r.get(i - 1), b = r.get(i);14      b[1] = Math.min(b[1], a[1] + b[0] - a[0]);15    }16    for (int i = m - 2; i > 0; --i) {17      int[] a = r.get(i), b = r.get(i + 1);18      a[1] = Math.min(a[1], b[1] + b[0] - a[0]);19    }20    int ans = 0;21    for (int i = 0; i < m - 1; ++i) {22      int[] a = r.get(i), b = r.get(i + 1);23      int t = (a[1] + b[1] + b[0] - a[0]) / 2;24      ans = Math.max(ans, t);25    }26    return ans;27  }28}

1class Solution {2public:3  int maxBuilding(int n, vector<vector<int>> &restrictions) {4    auto &&r = restrictions;5    r.push_back({1, 0});6    sort(r.begin(), r.end());7    if (r[r.size() - 1][0] != n)8      r.push_back({n, n - 1});9    int m = r.size();10    for (int i = 1; i < m; ++i) {11      r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0]);12    }13    for (int i = m - 2; i > 0; --i) {14      r[i][1] = min(r[i][1], r[i + 1][1] + r[i + 1][0] - r[i][0]);15    }16    int ans = 0;17    for (int i = 0; i < m - 1; ++i) {18      int t = (r[i][1] + r[i + 1][1] + r[i + 1][0] - r[i][0]) / 2;19      ans = max(ans, t);20    }21    return ans;22  }23};

1class Solution:2    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int: r = restrictions r . append([1, 0]) r . sort() if r[- 1][0] != n: r . append([n, n - 1]) m = len(r) for i in range(1, m): r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0]) for i in range(m - 2, 0, - 1): r[i][1] = min(r[i][1], r[i + 1][1] + r[i + 1][0] - r[i][0]) ans = 0 for i in range(m - 1): t = (r[i][1] + r[i + 1][1] + r[i + 1][0] - r[i][0]) // 2 ans = max(ans, t) return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem