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

Beautiful Towers I

Number: 3114

Difficulty: Medium

Paid? No

Companies: Salesforce

Problem Description

Given an array of tower heights, you are allowed to remove (i.e. reduce) some bricks so that the final arrangement forms a mountain shape. This means that there is a peak (which can extend over consecutive towers) where the heights are non-decreasing from the left up to the peak and non-increasing from the peak to the right. Each tower’s new height must be no greater than its original height. Return the maximum possible sum of the tower heights in such an arrangement.

Key Insights

  • The final arrangement has a peak index j such that:
    • For indices i in [0, j], the heights are determined by going backwards from j: h'[i] = min(heights[i], h'[i+1]), ensuring non-decreasing order when read from left to peak.
    • For indices i in [j, n-1], the heights are determined by going forwards from j: h'[i] = min(heights[i], h'[i-1]), ensuring non-increasing order from the peak.
  • The transformation is done by “removing” (reducing) bricks but never adding, so every tower’s new height is at most its original height.
  • By considering each index as a potential peak and computing the best possible left and right arrangements, we can compute a candidate total sum and pick the maximum.

Space and Time Complexity

Time Complexity: O(n^2) in the worst case since for each candidate peak, we potentially traverse left and right. Space Complexity: O(1) auxiliary space (ignoring input storage).

Solution

The solution iterates over all indices treating each as the peak of the mountain. For a fixed candidate peak index j:

  1. Compute the maximum possible sum on the left side (from index 0 to j) by traversing backwards. Start with the peak’s height, and for each index i going from j-1 to 0, update the current allowed height as the minimum of heights[i] and the height from i+1.
  2. Compute the maximum possible sum on the right side (from index j to n-1) by traversing forwards. Start with the peak’s height, and for each index i going from j+1 to n-1, update the current allowed height as the minimum of heights[i] and the height from i-1.
  3. Since the peak is counted in both left and right sums, subtract the peak’s height once.
  4. Keep track of the maximum mountain sum computed over all candidate peaks.

The key idea is working backwards (and forwards) from the peak, which naturally satisfies the non-decreasing (or non-increasing) property of the mountain shape while ensuring that we never exceed the original tower heights.

Code Solutions

# Python solution with detailed comments.
def maximumMountainSum(heights):
    n = len(heights)
    max_sum = 0

    # Consider each index as a candidate peak.
    for peak in range(n):
        # Build the left part (from 0 to peak) while moving backwards.
        left_sum = heights[peak]
        current_height = heights[peak]
        # Traverse backwards from the peak to index 0.
        for i in range(peak - 1, -1, -1):
            # Allowed height is min(current tower height, height from right).
            current_height = min(heights[i], current_height)
            left_sum += current_height

        # Build the right part (from peak to n-1) while moving forwards.
        right_sum = heights[peak]
        current_height = heights[peak]
        # Traverse forwards from the peak to the end.
        for i in range(peak + 1, n):
            current_height = min(heights[i], current_height)
            right_sum += current_height

        # Subtract the peak height once as it is counted twice.
        candidate_sum = left_sum + right_sum - heights[peak]
        max_sum = max(max_sum, candidate_sum)

    return max_sum

# Example usage:
print(maximumMountainSum([5,3,4,1,1]))  # Output: 13
print(maximumMountainSum([6,5,3,9,2,7]))  # Output: 22
print(maximumMountainSum([3,2,5,5,2,3]))  # Output: 18
← Back to All Questions