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 II

Difficulty: Medium

Problem Description

You are given a 0-indexed array maxHeights of n integers. You are tasked with building n towers in the coordinate line. The i-th tower is built at coordinate i and has a height of heights[i]. A configuration of towers is beautiful if the following conditions hold:

  1. 1 <= heights[i] <= maxHeights[i]
  2. heights is a mountain array.

Array heights is a mountain if there exists an index i such that:

  • For all 0 < j <= i, heights[j - 1] <= heights[j]
  • For all i <= k < n - 1, heights[k + 1] <= heights[k]

Return the maximum possible sum of heights of a beautiful configuration of towers.

Key Insights

  • The heights of towers must form a mountain shape, meaning there is a peak and heights must increase to that peak and then decrease.
  • We can utilize the maxHeights array to determine the maximum heights allowed for each tower and ensure constraints are met.
  • The problem requires careful consideration of potential peak positions to maximize the sum of tower heights while adhering to the mountain shape constraint.

Space and Time Complexity

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

Solution

To solve the problem, we can use a two-pass approach:

  1. First, traverse from left to right to determine the maximum possible heights for the ascending part of the mountain. This involves calculating the minimum between the current max height and the height of the previous tower plus one.
  2. Next, traverse from right to left to determine the maximum possible heights for the descending part of the mountain using a similar logic.
  3. Finally, calculate the heights array by taking the minimum of heights from both passes and summing them up to get the maximum sum of heights.

We can use simple arrays to track the heights during the two passes.

Code Solutions

def maxSumOfHeights(maxHeights):
    n = len(maxHeights)
    left_heights = [0] * n
    right_heights = [0] * n

    # First pass: left to right
    left_heights[0] = min(maxHeights[0], 1)
    for i in range(1, n):
        left_heights[i] = min(maxHeights[i], left_heights[i - 1] + 1)

    # Second pass: right to left
    right_heights[n - 1] = min(maxHeights[n - 1], 1)
    for i in range(n - 2, -1, -1):
        right_heights[i] = min(maxHeights[i], right_heights[i + 1] + 1)

    # Combine the results to get the final heights
    total_sum = 0
    for i in range(n):
        total_sum += min(left_heights[i], right_heights[i])

    return total_sum
← Back to All Questions