Leetcode 1840. Maximum Building Height

Problem Explanation

In this problem, we want to build n new buildings in a city in a line and are labeled from 1 to n. There are certain 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.

There are also 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. The goal is to return the maximum possible height of the tallest building.

Approach

The solution to this problem involves sorting to create a consistent order of the height restrictions and iterating through the sorted restrictions to find the roof height for each building. We can use the minimum function and the data structures vectors and arrays to solve this problem.

Let's walk through an example to demonstrate the approach of the solution.

Example

Suppose we have n = 5 and restrictions = [[2,1],[4,1]], we want to find the maximum possible height of the tallest building.

1. First, push the first building and the last building to the restrictions list as [[1, 0]],[[5, 4]] and sort the list A. A = [[1,0],[2,1],[4,1],[5,4]].

2. Now iterate through A to find the minimum height for each building:

   • i=1: dist = 2-1 = 1; A[1][1] = min(1,0+1) = 1
   • i=2: dist = 4-2 = 2; A[2][1] = min(1,1+2) = 1
   • i=3: dist = 5-4 = 1; A[3][1] = min(4,1+1) = 2

The new A will be [[1,0],[2,1],[4,1],[5,2]].

3. Now iterate through A in reverse order to find the minimum height for each building:

   • i=2: dist = 5-4 = 1; A[2][1] = min(1,2+1) = 1
   • i=1: dist = 4-2 = 2; A[1][1] = min(1,1+2) = 1
   • i=0: dist = 2-1 = 1; A[0][1] = min(0,1+1) = 0

The new A will be [[1,0],[2,1],[4,1],[5,2]].

4. Now iterate through the height pairs in A to find the maximum height of the tallest building:

   • ans = max(0, 1 + (2-1-abs(1-0))/2) = 1
   • ans = max(1, 1 + (4-2-abs(1-1))/2) = 1
   • ans = max(1, 2 + (5-4-abs(2-1))/2) = 2

The maximum height of the tallest building is 2.

Solution

C++ Solution

1#include<vector>
2#include<algorithm>
3
4using namespace std;
5
6class Solution {
7 public:
8  int maxBuilding(int n, vector<vector<int>>& restrictions) {
9    vector<vector<int>> A(restrictions);
10
11    A.push_back({1, 0});
12    A.push_back({n, n - 1});
13    sort(begin(A), end(A));
14
15    // Find minimum height for each building
16    for (int i = 1; i < A.size(); ++i) {
17      int dist = A[i][0] - A[i - 1][0];
18      A[i][1] = min(A[i][1], A[i - 1][1] + dist);
19    }
20
21    // Find minimum height for each building in reverse order
22    for (int i = A.size() - 2; i >= 0; --i) {
23      int dist = A[i + 1][0] - A[i][0];
24      A[i][1] = min(A[i][1], A[i + 1][1] + dist);
25    }
26
27    int ans = 0;
28
29    // Iterate through height pairs in A to find the maximum height of the tallest building
30    for (int i = 1; i < A.size(); ++i) {
31      int l = A[i - 1][0];
32      int r = A[i][0];
33      int hL = A[i - 1][1];
34      int hR = A[i][1];
35      ans = max(ans, max(hL, hR) + (r - l - abs(hL - hR)) / 2);
36    }
37
38    return ans;
39  }
40};

Python Solution

1from typing import List
2
3class Solution:
4    def maxBuilding(self, n: int, restrictions: List[List[int]]) -> int:
5        A = restrictions + [[1, 0], [n, n - 1]]
6        A.sort()
7
8        # Find minimum height for each building
9        for i in range(1, len(A)):
10            dist = A[i][0] - A[i - 1][0]
11            A[i][1] = min(A[i][1], A[i-1][1] + dist)
12
13        # Find minimum height for each building in reverse order
14        for i in range(len(A) - 2, -1, -1):
15            dist = A[i + 1][0] - A[i][0]
16            A[i][1] = min(A[i][1], A[i + 1][1] + dist)
17
18        ans = 0
19
20        # Iterate through height pairs in A to find the maximum height of the tallest building
21        for i in range(1, len(A)):
22            l, r = A[i - 1][0], A[i][0]
23            hL, hR = A[i - 1][1], A[i][1]
24            ans = max(ans, max(hL, hR) + (r - l - abs(hL - hR)) // 2)
25
26        return ans

Java Solution

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public int maxBuilding(int n, int[][] restrictions) {
7        List<int[]> A = new ArrayList<>(Arrays.asList(restrictions));
8        A.add(new int[]{1, 0});
9        A.add(new int[]{n, n - 1});
10        A.sort((o1, o2) -> Integer.compare(o1[0], o2[0]));
11
12        // Find minimum height for each building
13        for (int i = 1; i < A.size(); ++i) {
14            int dist = A.get(i)[0] - A.get(i - 1)[0];
15            A.get(i)[1] = Math.min(A.get(i)[1], A.get(i - 1)[1] + dist);
16        }
17
18        // Find minimum height for each building in reverse order
19        for (int i = A.size() - 2; i >= 0; --i) {
20            int dist = A.get(i + 1)[0] - A.get(i)[0];
21            A.get(i)[1] = Math.min(A.get(i)[1], A.get(i + 1)[1] + dist);
22        }
23
24        int ans = 0;
25
26        // Iterate through height pairs in A to find the maximum height of the tallest building
27        for (int i = 1; i < A.size(); ++i) {
28            int l = A.get(i - 1)[0];
29            int r = A.get(i)[0];
30            int hL = A.get(i - 1)[1];
31            int hR = A.get(i)[1];
32            ans = Math.max(ans, Math.max(hL, hR) + (r - l - Math.abs(hL - hR)) / 2);
33        }
34
35        return ans;
36    }
37}

With these solutions, you can find the maximum height of the tallest building in various programming languages, including C++, Python, and Java.