Scale Engineer

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
Math
Algorithms
Sorting
Data structures
Array
Companies
Dataminr

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] = [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

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.

// This approach is too slow and will cause Time Limit Exceeded (TLE)// due to n being up to 10^9. It's for conceptual understanding.class Solution {    public int maxBuilding(int n, int[][] restrictions) {        if (n == 1) return 0;        long[] max_h = new long[n + 1];         // Initialize max_h with upper bounds from all restrictions        for (int i = 1; i <= n; i++) {            max_h[i] = (long)i - 1;            for (int[] r : restrictions) {                max_h[i] = Math.min(max_h[i], (long)r[1] + Math.abs(i - r[0]));            }        }         // Forward pass to enforce adjacency from left        for (int i = 2; i <= n; i++) {            max_h[i] = Math.min(max_h[i], max_h[i - 1] + 1);        }         // Backward pass to enforce adjacency from right        for (int i = n - 1; i >= 1; i--) {            max_h[i] = Math.min(max_h[i], max_h[i + 1] + 1);        }         // Find the maximum height        long tallest = 0;        for (int i = 1; i <= n; i++) {            tallest = Math.max(tallest, max_h[i]);        }        return (int) tallest;    }}

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.

Solutions

class Solution {public  int maxBuilding(int n, int[][] restrictions) {    List<int[]> r = new ArrayList<>();    r.addAll(Arrays.asList(restrictions));    r.add(new int[]{1, 0});    Collections.sort(r, (a, b)->a[0] - b[0]);    if (r.get(r.size() - 1)[0] != n) {      r.add(new int[]{n, n - 1});    }    int m = r.size();    for (int i = 1; i < m; ++i) {      int[] a = r.get(i - 1), b = r.get(i);      b[1] = Math.min(b[1], a[1] + b[0] - a[0]);    }    for (int i = m - 2; i > 0; --i) {      int[] a = r.get(i), b = r.get(i + 1);      a[1] = Math.min(a[1], b[1] + b[0] - a[0]);    }    int ans = 0;    for (int i = 0; i < m - 1; ++i) {      int[] a = r.get(i), b = r.get(i + 1);      int t = (a[1] + b[1] + b[0] - a[0]) / 2;      ans = Math.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 →

Next problem