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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Beautiful Towers I

Difficulty: Medium

Problem Description

Given an array heights of n integers representing the number of bricks in n consecutive towers, your task is to remove some bricks to form a mountain-shaped tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing. Return the maximum possible sum of heights of a mountain-shaped tower arrangement.

Key Insights

  • A mountain-shaped arrangement has a peak and symmetrical sides.
  • Heights can only be reduced, not increased.
  • The peak can be at any index, requiring a local maximum approach.
  • We can calculate the left and right constraints for each tower based on neighboring heights.
  • The final height of each tower in the mountain shape is determined by the minimum of the calculated constraints.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will use an array to store the maximum allowed heights for each tower based on the constraints of the mountain shape. The algorithm involves two passes through the heights array:

  1. In the first pass (left to right), we calculate the maximum heights allowed based on the left neighbors.
  2. In the second pass (right to left), we adjust the maximum heights allowed based on the right neighbors.
  3. Finally, we calculate the total sum of the heights that can be achieved by taking the minimum of the heights at each index from the two passes.

This approach ensures we maintain a valid mountain shape while maximizing the total height.

Code Solutions

def maxMountainSum(heights):
    n = len(heights)
    if n == 0:
        return 0

    left_max = [0] * n
    right_max = [0] * n

    # Fill left_max
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = min(left_max[i - 1], heights[i])

    # Fill right_max
    right_max[n - 1] = heights[n - 1]
    for i in range(n - 2, -1, -1):
        right_max[i] = min(right_max[i + 1], heights[i])

    # Calculate the maximum possible sum of heights in mountain shape
    total_sum = 0
    for i in range(n):
        total_sum += min(left_max[i], right_max[i])

    return total_sum
← Back to All Questions