In this guide, you will get 1840. Maximum Building Height LeetCode Solution with the best time and space complexity. The solution to Maximum Building Height problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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
Complexity Analysis
Time Complexity: O(\texttt{sort})
Space Complexity: O(n)
1840. Maximum Building Height LeetCode Solution in C++
class Solution {
public:
int maxBuilding(int n, vector<vector<int>>& restrictions) {
vector<vector<int>> A(restrictions);
A.push_back({1, 0});
A.push_back({n, n - 1});
ranges::sort(A);
for (int i = 1; i < A.size(); ++i) {
const int dist = A[i][0] - A[i - 1][0];
A[i][1] = min(A[i][1], A[i - 1][1] + dist);
}
for (int i = A.size() - 2; i >= 0; --i) {
const int dist = A[i + 1][0] - A[i][0];
A[i][1] = min(A[i][1], A[i + 1][1] + dist);
}
int ans = 0;
for (int i = 1; i < A.size(); ++i) {
const int l = A[i - 1][0];
const int r = A[i][0];
const int hL = A[i - 1][1];
const int hR = A[i][1];
ans = max(ans, max(hL, hR) + (r - l - abs(hL - hR)) / 2);
}
return ans;
}
}; /* code provided by PROGIEZ */
1840. Maximum Building Height LeetCode Solution in Java
class Solution {
public int maxBuilding(int n, int[][] restrictions) {
final int k = restrictions.length;
int[][] A = new int[k + 2][2];
System.arraycopy(restrictions, 0, A, 0, k);
A[k] = new int[] {1, 0};
A[k + 1] = new int[] {n, n - 1};
Arrays.sort(A,
(a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
for (int i = 1; i < A.length; ++i) {
final int dist = A[i][0] - A[i - 1][0];
A[i][1] = Math.min(A[i][1], A[i - 1][1] + dist);
}
for (int i = A.length - 2; i >= 0; --i) {
final int dist = A[i + 1][0] - A[i][0];
A[i][1] = Math.min(A[i][1], A[i + 1][1] + dist);
}
int ans = 0;
for (int i = 1; i < A.length; ++i) {
final int l = A[i - 1][0];
final int r = A[i][0];
final int hL = A[i - 1][1];
final int hR = A[i][1];
ans = Math.max(ans, Math.max(hL, hR) + (r - l - Math.abs(hL - hR)) / 2);
}
return ans;
}
} // code provided by PROGIEZ
1840. Maximum Building Height LeetCode Solution in Python
class Solution:
def maxBuilding(self, n: int, restrictions: list[list[int]]) -> int:
A = sorted(restrictions + [[1, 0]] + [[n, n - 1]])
for i in range(len(A)):
dist = A[i][0] - A[i - 1][0]
A[i][1] = min(A[i][1], A[i - 1][1] + dist)
for i in reversed(range(len(A) - 1)):
dist = A[i + 1][0] - A[i][0]
A[i][1] = min(A[i][1], A[i + 1][1] + dist)
ans = 0
for (l, hL), (r, hR) in zip(A, A[1:]):
ans = max(ans, max(hL, hR) + (r - l - abs(hL - hR)) // 2)
return ans # code by PROGIEZ
