#1840

Hard

LeetCode Problem Workspace

Maximum Building Height

Find the maximum building height in a city given height restrictions for specific buildings.

Problem Statement

You are tasked with building n new buildings in a city, with building heights restricted by certain rules. The buildings are numbered 1 to n, and each building may have a restriction on its maximum height. You are given a 2D array of restrictions where each entry contains the building index and its maximum allowed height. Your goal is to determine the tallest possible building height for all buildings in the city, while adhering to the restrictions.

The restrictions specify the maximum allowed height for certain buildings, and the goal is to find the maximum possible height for all buildings that do not have a restriction. The buildings are arranged in a sequence, and you need to determine how high you can build the buildings while ensuring that no building exceeds the restrictions set in place. The key challenge is to manage the height distribution efficiently using mathematical and sorting strategies.

Examples

Example 1

Input: n = 5, restrictions = [[2,1],[4,1]]

Output: 2

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

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

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

Solution Approach

Sort Restrictions and Compute Maximum Heights

First, sort the building restrictions based on the building index. Then, compute the maximum height that can be assigned to each building while respecting the height constraints. Consider adjacent restrictions and calculate the heights by leveraging the space between the restricted buildings.

Leverage Height Differences and Gaps

After sorting the restrictions, calculate the height difference between adjacent restricted buildings and use this gap to distribute the maximum height across the unrestricted buildings. This step is key to finding the tallest building that satisfies all constraints.

Iterate Through the Buildings and Find the Maximum

Once you have calculated the maximum possible heights for each building, iterate through all the buildings and determine the tallest one. This requires checking the height values and ensuring they meet the constraints for all restricted buildings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of this solution depends on the sorting step, which is O(m log m) where m is the number of restrictions. The space complexity is O(m) due to the storage of sorted restrictions and the required computations.

What Interviewers Usually Probe

Candidate can efficiently use sorting to handle restrictions.
Candidate shows understanding of how to calculate height differences between buildings.
Candidate demonstrates problem-solving ability by iterating through the buildings correctly.

Common Pitfalls or Variants

Common pitfalls

Failing to handle cases where there are no restrictions.
Incorrectly calculating the height difference between adjacent buildings.
Overlooking edge cases where restrictions are placed on buildings at the ends of the sequence.

Follow-up variants

Consider larger values for n and test performance optimizations.
Vary the number of restrictions and test edge cases like no restrictions or all buildings restricted.
Modify the problem by allowing multiple restrictions per building and determining how that affects the maximum height calculation.

FAQ

How do I handle the maximum building height when no restrictions are provided?

Without restrictions, the maximum height for each building increases sequentially. You simply assign heights based on the building index.

What pattern should I use to approach the Maximum Building Height problem?

This problem follows the 'Array plus Math' pattern, combining sorting with mathematical reasoning to distribute building heights.

How do I calculate the tallest building in the city given restrictions?

By calculating the maximum height that can be assigned to each building while respecting the restrictions and height differences, you can determine the tallest building.

What is the time complexity of the Maximum Building Height solution?

The time complexity is O(m log m), where m is the number of restrictions. Sorting the restrictions dominates the complexity.

How do I handle edge cases in this problem?

Edge cases include scenarios with no restrictions, restrictions on buildings at the ends, or multiple restrictions on the same building. These need special handling during the calculation of the maximum building heights.

terminal

Solution

Solution 1: Sorting + Mathematics

First, we sort all the constraints by the building number in ascending order.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#1878 get biggest three rhombus sums in a grid #1686 stone game vi #1998 gcd sort of an array