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 II

Number: 3113

Difficulty: Medium

Paid? No

Companies: Amazon, Salesforce

Problem Description

Given an array maxHeights of length n, we want to assign heights for n towers (at coordinates 0 to n–1) such that for every index i, the tower height is in the range [1, maxHeights[i]]. Moreover, the heights array must form a mountain – that is, there should be some peak index such that to the left the heights are non‐decreasing and to the right they are non‐increasing. The goal is to choose the heights (subject to the bounds and mountain property) so that the sum of heights is maximized.

Key Insights

  • The optimal configuration (for a fixed peak) is obtained by “pushing down” from the peak: on the left, each tower’s height is the minimum between its max allowed height and the tower immediately to its right (starting from the peak), and similarly on the right.
  • For each index i as the candidate peak, the best achievable left segment is determined (from 0 to i) by greedily taking heights[j] = min(maxHeights[j], height[j+1]) going backwards.
  • Similarly, the right segment (from i to n – 1) is determined by moving rightwards.
  • We can precompute these optimal “left sums” and “right sums” for every index using a monotonic stack. This is similar to “range minimization” problems where the idea is to partition the array into segments bounded by a smaller value.
  • Finally, for every index i, the total sum with i chosen as peak is leftSum[i] + rightSum[i] – maxHeights[i] (subtracting the peak once since it is counted in both parts).
  • The maximum among all these candidate peaks is the answer.

Space and Time Complexity

Time Complexity: O(n) – each of the two passes (left and right) uses a monotonic stack, taking linear time. Space Complexity: O(n) – for storing auxiliary arrays and stacks.

Solution

The solution makes two passes:

  1. A left-to-right pass computes for each index i the maximum achievable sum from index 0 to i if i were the peak (using a monotonic stack to “merge” segments that are limited by a small maxHeights value).
  2. A right-to-left pass computes the optimal sum from i to n–1. For each index i, we then combine these sums (subtracting maxHeights[i] once because it appears in both computations) to get the maximum possible sum when i is the peak.

Key data structures include:

  • Monotonic stacks (one for left and another for right) to efficiently backtrack segments where the current maxHeights limits previous sums.
  • Arrays to store cumulative optimal sums from the left and right side.

This algorithm uses the “water‐fill” idea: once a lower barrier is encountered, it controls the values over an interval. This is the key trick that allows consolidation of the sum in O(n) time.

Code Solutions

# Python solution for Beautiful Towers II
from typing import List

class Solution:
    def maximumSum(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        left_sum = [0] * n   # left_sum[i]: best sum for indices 0..i if i is the right end (peak side)
        right_sum = [0] * n  # right_sum[i]: best sum for indices i..n-1 if i is the left end (peak side)

        # Compute left_sum using a monotonic stack (stores indices)
        stack = []
        for i in range(n):
            # Pop elements that are greater than current
            while stack and maxHeights[stack[-1]] > maxHeights[i]:
                stack.pop()
            if not stack:
                # If no element to the left is smaller, we can assign the current value 
                # to all positions from 0 to i
                left_sum[i] = maxHeights[i] * (i + 1)
            else:
                # Let j be the index of the last element that is less or equal.
                j = stack[-1]
                left_sum[i] = left_sum[j] + maxHeights[i] * (i - j)
            stack.append(i)

        # Compute right_sum using a monotonic stack (iterate from right to left)
        stack = []
        for i in range(n - 1, -1, -1):
            # Pop elements that are greater than current value
            while stack and maxHeights[stack[-1]] > maxHeights[i]:
                stack.pop()
            if not stack:
                # From i to n-1, we can assign the current value
                right_sum[i] = maxHeights[i] * (n - i)
            else:
                j = stack[-1]
                right_sum[i] = right_sum[j] + maxHeights[i] * (j - i)
            stack.append(i)

        # Combine left_sum and right_sum using each index as the peak.
        max_total = 0
        for i in range(n):
            # Subtract maxHeights[i] once because peak is counted twice
            current_total = left_sum[i] + right_sum[i] - maxHeights[i]
            max_total = max(max_total, current_total)
        return max_total

# Example usage:
# sol = Solution()
# print(sol.maximumSum([5,3,4,1,1]))  # Output: 13
← Back to All Questions