We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximum Building Height

Number: 1968

Difficulty: Hard

Paid? No

Companies: Dataminr

Problem Description

We are given n buildings in a row (indexed 1 to n) with the following requirements:

  • Building 1 must have a height of 0.
  • The difference in height between any two adjacent buildings cannot be more than 1.
  • Some buildings have an additional restriction (via a restrictions array) specifying that the building’s height must be at most a given value. The goal is to determine the maximum possible height (the height of the tallest building) that can be achieved while satisfying all the conditions.

Key Insights

  • Add a restriction for building 1 with height 0 and one for building n (with a theoretical limit of n-1) to account for edge cases.
  • Sort the restrictions by the building id.
  • Propagate the restrictions forward (left-to-right) to adjust each building’s allowed maximum height based on its predecessor.
  • Propagate backward (right-to-left) to further adjust the restrictions based on successors.
  • For each pair of consecutive restrictions, determine the maximum possible peak height in the interval using the formula: • peak = (height_left + height_right + gap) // 2, where gap = (id_right - id_left).
  • The answer will be the maximum of these calculated peaks and the final adjusted restriction values.

Space and Time Complexity

Time Complexity: O(m log m) where m is the number of restrictions (due to sorting) plus O(m) for the two propagation passes. Space Complexity: O(m) to store the adjusted restrictions.

Solution

We first ensure that building 1 with height 0 and building n (with a theoretical max height of n-1, since height can increment/decrement by at most 1 per building) are included in our restrictions list. After sorting the list based on building id, we perform two passes:

  1. Left-to-right pass to ensure that for any building, its maximum allowed height is not more than the previous building’s height plus the distance between them.
  2. Right-to-left pass to enforce the constraint from the opposite direction.

Once the restrictions are “tightened” from both directions, we examine each adjacent pair. For a gap between two restricted buildings, we can “raise” the height in the middle by taking advantage of the allowed increments and decrements. The highest attainable peak within the gap is given by (left_height + right_height + distance) // 2. The overall answer is the maximum height encountered among all such segments.

This algorithm smartly uses greedy propagation of constraints and a simple math formula to compute the maximum possible height in an interval.

Code Solutions

# Python solution for Maximum Building Height

def maxBuilding(n: int, restrictions: list) -> int:
    # Append building1 restriction and building n restriction
    restrictions.append([1, 0])
    restrictions.append([n, n - 1])
    # Sort restrictions by building id
    restrictions.sort(key=lambda x: x[0])
    
    # Left-to-right propagation:
    for i in range(1, len(restrictions)):
        # Calculate how much the allowed height can be increased due to distance gap
        id_prev, height_prev = restrictions[i - 1]
        id_curr, height_curr = restrictions[i]
        allowed_height = height_prev + (id_curr - id_prev)
        # Update current height to be the minimum of its restriction and the allowed value
        restrictions[i][1] = min(height_curr, allowed_height)
    
    # Right-to-left propagation:
    for i in range(len(restrictions) - 2, -1, -1):
        id_next, height_next = restrictions[i + 1]
        id_curr, height_curr = restrictions[i]
        allowed_height = height_next + (id_next - restrictions[i][0])
        # Update current height constraint based on the neighbor to the right
        restrictions[i][1] = min(height_curr, allowed_height)
    
    max_height = 0
    # Calculate maximum possible height in each segment between adjacent restrictions
    for i in range(len(restrictions) - 1):
        id_left, height_left = restrictions[i]
        id_right, height_right = restrictions[i + 1]
        # gap between the two restricted positions
        gap = id_right - id_left
        # The maximum possible peak in the gap
        local_max = (height_left + height_right + gap) // 2
        max_height = max(max_height, local_max)
    
    return max_height

# Example usage
#print(maxBuilding(5, [[2,1],[4,1]]))  # Expected output: 2
← Back to All Questions