Maximum Building Height

HARD

Description

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

Checkout 2 different approaches to solve Maximum Building Height. Click on different approaches to view the approach and algorithm in detail.

Dynamic Programming on All Buildings

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.

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 Analysis

Time Complexity: 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 Complexity: O(n), where `n` is the number of buildings. This is required to store the height array for all buildings.

Pros and Cons

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.

Code Solutions

Checking out 3 solutions in different languages for Maximum Building Height. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Maximum Building Height

Algorithms:

Sorting

Patterns:

Math

Data Structures:

Array

Companies:

Dataminr |