1840. Maximum Building Height
Problem Description
In this problem, we're tasked with determining the maximum possible height of the tallest building that can be built, given some specific constraints.
We have to build n
new buildings in a line, labeled from 1
to n
, with the following restrictions:
- 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
. This means each building can either be the same height as the previous one, one unit taller, or one unit shorter.
Additionally, there's an array called restrictions
that provides further limits on the height of certain buildings. This array is composed of elements [id_i, maxHeight_i]
, which means the building with label id_i
must not exceed the height maxHeight_i
. It's assured that each building appears at most once in the array, and the first building (with label 1
) will not be included in the restrictions.
The goal is to find the maximum height achievable for the tallest building among those built under these constraints.
Intuition
To approach this problem, we can follow these steps:
-
First, we add a restriction for the first building with id
1
and height0
since it's given that the first building's height must be0
. Also, if the last buildingn
doesn't have a restriction, we add a default restriction for it as[n, n - 1]
, supposing we could reach the maximum height one less than its position since each building height can increase by at most1
. -
Then, we sort the restrictions by building id so that we can iterate through the buildings in ascending order.
-
The height restrictions for buildings in between the given restrictions can be effectively calculated by a forward pass, updating the
maxHeight
to the minimum of its own height or the height imposed by the previous building'smaxHeight
increased by the difference in their ids. This ensures that a building conforms not only to its explicit restrictions but also maintains the difference of1
height unit constraint with previous buildings. -
We repeat a similar process in a backward pass. We iterate backward through the array and update each
maxHeight
to be the minimum of its own or the height possible due to the height constraint from the next building decreased by the difference in ids. This balances the height constraints both from forward and backward directions for each building. -
The tallest possible building will be at the location where we can maximize the given constraints. To find this maximum, we examine each gap between two adjacent restrictions after the above forward and backward passes. Due to the constraint that adjacent buildings can have at most a height difference of
1
, the maximum height in a gap will be at the halfway point between the two restrictions. -
By examining each gap and calculating this potential maximum height using the adjusted restrictions, we can determine the overall maximum height of any building. The final answer is the maximum of these potential maximum heights.
The intuition behind this approach is that each restriction "ripples" through its neighbors ahead and behind, effectively spreading the constraints throughout the range of buildings. We seek a balance point within each gap between restrictions where we can attain the tallest height before descending down to meet the next restriction.
Learn more about Math patterns.
Solution Approach
The solution provided uses a few important programming concepts to achieve the desired result: sorting, iteration, and comparative logic.
Here’s a step-by-step breakdown of the implementation:
-
Inserting Boundary Restrictions:
- The code begins by appending the artificial restrictions
r.append([1, 0])
for the first building, which must always be height0
, andr.append([n, n - 1])
for the last building, if there isn't any existing restriction for it, which ensures that the possible height of the last buildingn
is within the permissible range subject to the incremental restriction.
- The code begins by appending the artificial restrictions
-
Sorting Restrictions:
- The list of restrictions
r
is then sorted by the buildingid
(r.sort()
), so that we can consider the restrictions in the order of building positions.
- The list of restrictions
-
Forward Pass:
- A forward iteration (
for i in range(1, m):
) adjusts each building's height based on the constraints "rippling forward." Specifically, each restriction’s maxHeight is updated (r[i][1] = min(r[i][1], r[i - 1][1] + r[i][0] - r[i - 1][0])
) to the smaller of the existing restriction or the height allowed by the previous building’s restriction plus the difference between their ids. This maintains the constraint that no two adjacent buildings differ in height by more than1
.
- A forward iteration (
-
Backward Pass:
- Next, the code performs a backward iteration (
for i in range(m - 2, 0, -1):
) to adjust the heights based on the restrictions "rippling backward." This adjustment (r[i][1] = min(r[i][1], r[i + 1][1] + r[i + 1][0] - r[i][0])
) ensures that each building's height is the smaller of the existing restriction or what is allowed by the next building’s restriction minus the difference between their ids.
- Next, the code performs a backward iteration (
-
Finding the Maximum Height:
- The code then enters a loop that examines the gaps between two adjacent restrictions (
for i in range(m - 1):
). The potential maximum height at the midpoint of the gap is calculated ast = (r[i][1] + r[i + 1][1] + r[i + 1][0] - r[i][0]) // 2
. This accounts for the "climbing up" from one restriction and "climbing down" from the next, finding the highest point where both constraints meet.
- The code then enters a loop that examines the gaps between two adjacent restrictions (
-
Computing the Answer:
- Finally, within this loop, the answer (
ans
) is updated to the maximum height found (ans = max(ans, t)
) after each iteration.
- Finally, within this loop, the answer (
The algorithm smartly leverages the given constraints in a constructive manner by first ensuring that all imposed restrictions are met and then finding the maximum height that can still be achieved within those limits. It doesn't use any complex data structures, just a list to store the restrictions and simple iterations to propagate the constraints through adjacent buildings.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example.
Suppose we need to construct 5 buildings and the array of restrictions is restrictions = [[3, 2], [5, 3]]
. This implies building 3 must not exceed height 2, and building 5 must not exceed height 3.
-
Inserting Boundary Restrictions:
- We start by appending artificial restrictions
[1, 0]
for the first building and[5, 4]
for the last building (since there is an existing restriction, we don’t change it). Now the updated restrictions list isr = [[1, 0], [3, 2], [5, 3]]
.
- We start by appending artificial restrictions
-
Sorting Restrictions:
r
is already sorted by the building ids[1, 3, 5]
, so we do not need to perform a sort in this case.
-
Forward Pass:
- We then apply the forward pass. There is no update required for building 2, since the default increasing sequence satisfies the restrictions. The height of building 3 remains
2
, as it satisfies its restriction and the incremental rule. - Updated
r = [[1, 0], [3, 2], [5, 3]]
(no changes in this phase).
- We then apply the forward pass. There is no update required for building 2, since the default increasing sequence satisfies the restrictions. The height of building 3 remains
-
Backward Pass:
- Now applying the backward pass: For building 3, the maxHeight becomes
min(2, 3 + (5 - 3)) = 2
, which is no change. - For building 1, there is still no change as the minHeight 0 is already as low as it can be.
- Final updated
r = [[1, 0], [3, 2], [5, 3]]
(again, no changes in this phase as the restrictions match the increasing step rule).
- Now applying the backward pass: For building 3, the maxHeight becomes
-
Finding the Maximum Height:
- Looking at the gap between buildings 1 and 3, using
(r[i][1] + r[i + 1][1] + r[i + 1][0] - r[i][0]) // 2
, we calculatet = (0 + 2 + 3 - 1) // 2 = 2
. - For the gap between buildings 3 and 5, we calculate
t = (2 + 3 + 5 - 3) // 2 = 3
.
- Looking at the gap between buildings 1 and 3, using
-
Computing the Answer:
- The final answer
ans
is the maximum value from the calculated midpoint heights, which in this case ismax(2, 3) = 3
.
- The final answer
In this example, the tallest building that can be built will have a maximum height of 3. This approach illustrates how the algorithm efficiently adheres to the constraints by working within the boundaries defined by the restrictions and incrementally adjusting the heights of the buildings through forward and backward passes. The smart traversal of gaps between restrictions helps find the highest feasible point that satisfies both the '1 unit height difference' rule and the height limits given in any additional restrictions.
Solution Implementation
1class Solution:
2 def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
3 # Add the first building restriction (building 1 can't exceed height 0)
4 restrictions.append([1, 0])
5 # Sort restrictions based on the building index
6 restrictions.sort()
7
8 # If the last restriction is not for the last building, add a restriction for it
9 # The height of the last building can't exceed n - 1 (1-indexed)
10 if restrictions[-1][0] != n:
11 restrictions.append([n, n - 1])
12
13 # Update the maximum height for each building in the forward direction
14 # Ensuring that each next building isn't taller than the previous plus the distance between them
15 for i in range(1, len(restrictions)):
16 restrictions[i][1] = min(restrictions[i][1], restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0])
17
18 # Update the maximum height for each building in the backward direction
19 # Making sure it follows restrictions coming from the buildings in front
20 for i in range(len(restrictions) - 2, -1, -1):
21 restrictions[i][1] = min(restrictions[i][1], restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0])
22
23 # Calculate the maximum height we can achieve between each adjacent pair of buildings
24 max_height = 0
25 for i in range(len(restrictions) - 1):
26 # Maximum possible height between two buildings, considering their restrictions and distance
27 peak_height = (restrictions[i][1] + restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0]) // 2
28 max_height = max(max_height, peak_height)
29
30 # Return the maximum height found
31 return max_height
32
1import java.util.*;
2
3class Solution {
4 public int maxBuilding(int totalBuildings, int[][] restrictions) {
5 // Create a list to hold the restrictions and add the initial and end restrictions
6 List<int[]> restrictionList = new ArrayList<>();
7 restrictionList.add(new int[]{1, 0}); // Add a restriction for the first building, height 0
8 restrictionList.addAll(Arrays.asList(restrictions)); // Add all other restrictions
9
10 // Sort the list of restrictions by the building index in ascending order
11 Collections.sort(restrictionList, (a, b) -> Integer.compare(a[0], b[0]));
12
13 // Ensure an end restriction is in place if not already specified
14 if (restrictionList.get(restrictionList.size() - 1)[0] != totalBuildings) {
15 restrictionList.add(new int[]{totalBuildings, totalBuildings - 1});
16 }
17
18 int restrictionCount = restrictionList.size();
19
20 // Forward pass: ensure that each restriction respects the previous one
21 for (int i = 1; i < restrictionCount; ++i) {
22 int[] previousRestriction = restrictionList.get(i - 1);
23 int[] currentRestriction = restrictionList.get(i);
24 currentRestriction[1] = Math.min(currentRestriction[1], previousRestriction[1] + currentRestriction[0] - previousRestriction[0]);
25 }
26
27 // Backward pass: adjust restrictions based on later restrictions
28 for (int i = restrictionCount - 2; i >= 0; --i) {
29 int[] currentRestriction = restrictionList.get(i);
30 int[] nextRestriction = restrictionList.get(i + 1);
31 currentRestriction[1] = Math.min(currentRestriction[1], nextRestriction[1] + nextRestriction[0] - currentRestriction[0]);
32 }
33
34 // Find the maximum possible height between each pair of adjacent restrictions
35 int maximumHeight = 0;
36 for (int i = 0; i < restrictionCount - 1; ++i) {
37 int[] currentRestriction = restrictionList.get(i);
38 int[] nextRestriction = restrictionList.get(i + 1);
39 // Calculate potential max height between restrictions, considering the allowed increase/decrease in height
40 int maxHeightBetween = (currentRestriction[1] + nextRestriction[1] + nextRestriction[0] - currentRestriction[0]) / 2;
41 maximumHeight = Math.max(maximumHeight, maxHeightBetween);
42 }
43
44 return maximumHeight; // Return the maximum height found
45 }
46}
47
1#include <vector>
2#include <algorithm>
3
4using namespace std;
5
6class Solution {
7public:
8 int maxBuilding(int n, vector<vector<int>>& restrictions) {
9
10 // Append the first restriction explicitly - starting at building 1, height is 0.
11 restrictions.push_back({1, 0});
12 sort(restrictions.begin(), restrictions.end());
13
14 // If there is no restriction for the last building, add it with maximum possible height.
15 if (restrictions.back()[0] != n) restrictions.push_back({n, n - 1});
16
17 // Update restrictions from left to right.
18 for (int i = 1; i < restrictions.size(); ++i) {
19 // The restriction height should be the minimum of its current value and the maximum height allowed by the previous restriction plus the distance to it.
20 restrictions[i][1] = min(restrictions[i][1], restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0]);
21 }
22
23 // Update restrictions from right to left.
24 for (int i = restrictions.size() - 2; i > 0; --i) {
25 // The restriction height should be the minimum of its current value and the maximum height allowed by the next restriction minus the distance to it.
26 restrictions[i][1] = min(restrictions[i][1], restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0]);
27 }
28
29 // Calculate the maximum height we can build for the entire range.
30 int maxPossibleHeight = 0; // Initialize the answer to be the maximum possible height.
31 for (int i = 0; i < restrictions.size() - 1; ++i) {
32 // This is the theoretical maximum height that can be achieved at the mid-point between two restrictions, taking both into account.
33 int peakHeight = (restrictions[i][1] + restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0]) / 2;
34 // Update the maximum possible height if the current peak is higher.
35 maxPossibleHeight = max(maxPossibleHeight, peakHeight);
36 }
37
38 // Return the maximum possible height that can be achieved.
39 return maxPossibleHeight;
40 }
41};
42
1function maxBuilding(n: number, restrictions: number[][]): number {
2 // Append the first restriction explicitly - starting at building 1, height is 0.
3 restrictions.push([1, 0]);
4 restrictions.sort((a, b) => a[0] - b[0]);
5
6 // If there is no restriction for the last building, add it with maximum possible height.
7 if (restrictions[restrictions.length - 1][0] !== n) {
8 restrictions.push([n, n - 1]);
9 }
10
11 // Update the restrictions from left to right.
12 for (let i = 1; i < restrictions.length; ++i) {
13 restrictions[i][1] = Math.min(
14 restrictions[i][1],
15 restrictions[i - 1][1] + restrictions[i][0] - restrictions[i - 1][0]
16 );
17 }
18
19 // Update the restrictions from right to left.
20 for (let i = restrictions.length - 2; i >= 0; --i) {
21 restrictions[i][1] = Math.min(
22 restrictions[i][1],
23 restrictions[i + 1][1] + restrictions[i + 1][0] - restrictions[i][0]
24 );
25 }
26
27 // Calculate the maximum height we can build for the entire range.
28 let maxPossibleHeight = 0; // Initialize the variable to keep track of the maximum possible building height.
29 for (let i = 0; i < restrictions.length - 1; ++i) {
30 // Calculate the maximum height at the midpoint between two restrictions.
31 let peakHeight =
32 (restrictions[i][1] + restrictions[i + 1][1] +
33 restrictions[i + 1][0] - restrictions[i][0]) /
34 2;
35 // Update the maximum possible height if the current peak height is higher.
36 maxPossibleHeight = Math.max(maxPossibleHeight, peakHeight);
37 }
38
39 // Return the maximum possible height that can be achieved given the restrictions.
40 return maxPossibleHeight;
41}
42
Time and Space Complexity
Time Complexity
The time complexity consists of the following parts:
- Appending initial and end restrictions:
O(1)
- Constant time operations to append two additional restrictions. - Sorting the restrictions:
O(m log m)
- Sortingm
restrictions wherem
is the number of restrictions including the two appended ones. - Forward pass to adjust the heights:
O(m)
- A single pass through the sorted restrictions to enforce that the height difference between consecutive buildings doesn't exceed the difference in their indices. - Backward pass to adjust the heights:
O(m)
- Another single pass through the sorted restrictions in the reverse direction for the same purpose as in step 3. - Finding the maximum height:
O(m)
- A final pass to find the maximum height between consecutive buildings.
Since sorting dominates the complexity, the total time complexity is O(m log m)
where m
is the number of restrictions including the added ones.
Space Complexity
The space complexity is comprised of:
- Storing the restrictions list with the two additional restrictions:
O(m)
- Wherem
is the number of restrictions including the two appended ones. - No additional significant space is used.
Thus, the total space complexity is O(m)
where m
is the number of restrictions including the added ones.
Learn more about how to find time and space complexity quickly using problem constraints.
What does the following code do?
1def f(arr1, arr2):
2 i, j = 0, 0
3 new_arr = []
4 while i < len(arr1) and j < len(arr2):
5 if arr1[i] < arr2[j]:
6 new_arr.append(arr1[i])
7 i += 1
8 else:
9 new_arr.append(arr2[j])
10 j += 1
11 new_arr.extend(arr1[i:])
12 new_arr.extend(arr2[j:])
13 return new_arr
14
1public static List<Integer> f(int[] arr1, int[] arr2) {
2 int i = 0, j = 0;
3 List<Integer> newArr = new ArrayList<>();
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.add(arr1[i]);
8 i++;
9 } else {
10 newArr.add(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.add(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.add(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
1function f(arr1, arr2) {
2 let i = 0, j = 0;
3 let newArr = [];
4
5 while (i < arr1.length && j < arr2.length) {
6 if (arr1[i] < arr2[j]) {
7 newArr.push(arr1[i]);
8 i++;
9 } else {
10 newArr.push(arr2[j]);
11 j++;
12 }
13 }
14
15 while (i < arr1.length) {
16 newArr.push(arr1[i]);
17 i++;
18 }
19
20 while (j < arr2.length) {
21 newArr.push(arr2[j]);
22 j++;
23 }
24
25 return newArr;
26}
27
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Don’t Miss This!