# Maximum Building Height
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-building-height)
Canonical: https://scaleengineer.com/dsa/problems/maximum-building-height
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
**Companies:** [Dataminr](https://scaleengineer.com/companies/dataminr)
---
## Problem
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
## 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.
**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.
**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 109, 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`.
### Explanation
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.
```java
// 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;
}
}
```
### 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.
## Two-Pass Greedy Approach on Restrictions
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.
**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.
**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.
### Explanation
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:
1. Create a list of all checkpoints. This includes the given `restrictions` plus a mandatory checkpoint for the first building: `[1, 0]`.
2. Sort this list of checkpoints by their building ID.
3. 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))`.
4. After these two passes, we have the tightest possible maximum heights for each restricted building.
5. 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.
6. 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)`.
7. The answer is the maximum of all calculated peak heights and the height of the last segment's end.
```java
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Solution {
public int maxBuilding(int n, int[][] restrictions) {
List allRestrictions = new ArrayList<>();
allRestrictions.add(new int[]{1, 0});
for (int[] r : restrictions) {
allRestrictions.add(r);
}
Collections.sort(allRestrictions, (a, b) -> Integer.compare(a[0], b[0]));
// Forward pass to propagate constraints from left to right
for (int i = 1; i < allRestrictions.size(); i++) {
int[] prev = allRestrictions.get(i - 1);
int[] curr = allRestrictions.get(i);
curr[1] = Math.min(curr[1], prev[1] + (curr[0] - prev[0]));
}
// Backward pass to propagate constraints from right to left
for (int i = allRestrictions.size() - 2; i >= 0; i--) {
int[] curr = allRestrictions.get(i);
int[] next = allRestrictions.get(i + 1);
curr[1] = Math.min(curr[1], next[1] + (next[0] - curr[0]));
}
long max_h = 0;
// Calculate max height between adjacent restrictions
for (int i = 0; i < allRestrictions.size() - 1; i++) {
long id1 = allRestrictions.get(i)[0];
long h1 = allRestrictions.get(i)[1];
long id2 = allRestrictions.get(i + 1)[0];
long h2 = allRestrictions.get(i + 1)[1];
// The peak height in the 'tent' between (id1, h1) and (id2, h2)
long peak_h = (h1 + h2 + (id2 - id1)) / 2;
max_h = Math.max(max_h, peak_h);
}
// Handle the last segment from the last restriction to n
int[] lastRestriction = allRestrictions.get(allRestrictions.size() - 1);
long last_segment_max = (long)lastRestriction[1] + (n - lastRestriction[0]);
max_h = Math.max(max_h, last_segment_max);
return (int) max_h;
}
}
```
### 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`.
# Solutions
### Java
```java
class Solution {
public
int maxBuilding(int n, int[][] restrictions) {
List 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;
}
}
```
### CPP
```cpp
class Solution {
public:
int maxBuilding(int n, vector> &restrictions) {
auto &&r = restrictions;
r.push_back({1, 0});
sort(r.begin(), r.end());
if (r[r.size() - 1][0] != n)
r.push_back({n, n - 1});
int m = r.size();
for (int i = 1; i < m; ++i) {
r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0]);
}
for (int i = m - 2; i > 0; --i) {
r[i][1] = min(r[i][1], r[i + 1][1] + r[i + 1][0] - r[i][0]);
}
int ans = 0;
for (int i = 0; i < m - 1; ++i) {
int t = (r[i][1] + r[i + 1][1] + r[i + 1][0] - r[i][0]) / 2;
ans = max(ans, t);
}
return ans;
}
};
```
### Python
```python
class Solution:
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
```