Beautiful Towers II

Med

#2563Time: O(N). Calculating `leftSum` takes O(N), `rightSum` takes O(N), and the final pass to combine them takes O(N). Each element is pushed and popped from the stack at most once.Space: O(N), for storing the `leftSum` and `rightSum` arrays, and for the stack which can grow up to size N in the worst case.1 company

Data structures

Array Stack Monotonic Stack

Companies

Salesforce

Prompt

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 <= heights[i] <= maxHeights[i]
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.

Example 1:

Input: maxHeights = [5,3,4,1,1]
Output: 13
Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]  
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.

Example 2:

Input: maxHeights = [6,5,3,9,2,7]
Output: 22
Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.

Example 3:

Input: maxHeights = [3,2,5,5,2,3]
Output: 18
Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.

Constraints:

1 <= n == maxHeights.length <= 10⁵
1 <= maxHeights[i] <= 10⁹

Approaches

2 approaches with complexity analysis and trade-offs.

The O(N^2) brute-force approach is slow because it repeatedly calculates sums for overlapping subarrays. We can optimize this by pre-calculating these sums. The key insight is that the total sum for a mountain with a peak at i can be decomposed into two independent subproblems: the maximum sum of a non-decreasing sequence ending at i and the maximum sum of a non-increasing sequence starting at i. These two sets of sums (for all i) can be computed efficiently in O(N) time using a monotonic stack. After pre-computation, we can find the maximum total sum in a final O(N) pass.

Algorithm

Define two arrays, leftSum and rightSum, of size n to store precomputed sums.
Calculate leftSum: leftSum[i] will store the maximum sum of a valid non-decreasing sequence of towers on maxHeights[0...i] with i as the peak.
- Use a monotonic stack (storing indices of maxHeights with increasing values) and iterate from i = 0 to n-1.
- For each i, pop from the stack while maxHeights[stack.peek()] >= maxHeights[i].
- The sum leftSum[i] can then be calculated in O(1) using the previously computed sum for the new stack top (leftSum[p]) and the value maxHeights[i].
Calculate rightSum: rightSum[i] will store the maximum sum of a valid non-increasing sequence of towers on maxHeights[i...n-1] with i as the peak.
- This is symmetric to the leftSum calculation. Use a monotonic stack and iterate from i = n-1 down to 0.
Combine Results: The maximum sum for a mountain with peak i is leftSum[i] + rightSum[i] - maxHeights[i] (subtracting maxHeights[i] because it's included in both sums).
Iterate through all i from 0 to n-1, calculate this combined sum, and find the maximum value. This will be the final answer.

Walkthrough

This approach is based on dynamic programming and a monotonic stack. We pre-calculate two arrays:

leftSum[i]: The maximum sum of a beautiful tower configuration for the prefix maxHeights[0...i] where the heights are non-decreasing (i.e., i is the peak of this prefix). We can compute this for all i in O(N) time. We iterate from left to right, maintaining a monotonic stack of indices where maxHeights values are increasing. For each i, we find the previous index p where maxHeights[p] < maxHeights[i]. All towers between p and i will have height maxHeights[i]. The total sum leftSum[i] can be derived from leftSum[p].
rightSum[i]: Similarly, this is the maximum sum for the suffix maxHeights[i...n-1] where heights are non-increasing. This is calculated symmetrically by iterating from right to left.

Once both leftSum and rightSum arrays are populated, we can find the maximum possible sum for a mountain with a peak at index i by the formula: leftSum[i] + rightSum[i] - maxHeights.get(i). We subtract maxHeights.get(i) because it was counted in both leftSum[i] and rightSum[i]. The final answer is the maximum value of this expression over all i from 0 to n-1.

1import java.util.List;2import java.util.Stack;3 4class Solution {5    public long maximumSumOfHeights(List<Integer> maxHeights) {6        int n = maxHeights.size();7        8        long[] leftSum = new long[n];9        Stack<Integer> stack = new Stack<>();10        for (int i = 0; i < n; i++) {11            long currentMaxHeight = maxHeights.get(i);12            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= currentMaxHeight) {13                stack.pop();14            }15            16            if (stack.isEmpty()) {17                leftSum[i] = (long)(i + 1) * currentMaxHeight;18            } else {19                int prevSmallerIndex = stack.peek();20                leftSum[i] = leftSum[prevSmallerIndex] + (long)(i - prevSmallerIndex) * currentMaxHeight;21            }22            stack.push(i);23        }24        25        long[] rightSum = new long[n];26        stack.clear();27        for (int i = n - 1; i >= 0; i--) {28            long currentMaxHeight = maxHeights.get(i);29            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= currentMaxHeight) {30                stack.pop();31            }32            33            if (stack.isEmpty()) {34                rightSum[i] = (long)(n - i) * currentMaxHeight;35            } else {36                int nextSmallerIndex = stack.peek();37                rightSum[i] = rightSum[nextSmallerIndex] + (long)(nextSmallerIndex - i) * currentMaxHeight;38            }39            stack.push(i);40        }41        42        long maxTotalSum = 0;43        for (int i = 0; i < n; i++) {44            maxTotalSum = Math.max(maxTotalSum, leftSum[i] + rightSum[i] - maxHeights.get(i));45        }46        47        return maxTotalSum;48    }49}

Complexity

Time

O(N). Calculating `leftSum` takes O(N), `rightSum` takes O(N), and the final pass to combine them takes O(N). Each element is pushed and popped from the stack at most once.

Space

O(N), for storing the `leftSum` and `rightSum` arrays, and for the stack which can grow up to size N in the worst case.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Passes the given constraints with ease.

Cons

More complex to understand and implement correctly compared to the brute-force approach.
Requires knowledge of the monotonic stack data structure and its application.

This approach directly translates the problem definition into a solution. We consider every possible index as the peak of the mountain. For each potential peak, we construct the optimal heights array and calculate its sum. The optimal construction for a fixed peak i involves setting heights[i] = maxHeights[i] and then greedily choosing the largest possible heights for the towers to the left and right while satisfying the mountain and maxHeights constraints. The final answer is the maximum sum found among all possible peak choices.

Algorithm

Initialize a variable maxTotalSum to 0.
Iterate through each index i from 0 to n-1, considering it as the potential peak of the mountain array.
For each i, calculate the sum of heights for a beautiful configuration with i as the peak.
- Initialize currentSum with maxHeights[i], as the peak tower will have its maximum possible height.
- Initialize a variable prevHeight to maxHeights[i].
- Iterate backwards from j = i - 1 to 0 to calculate the sum of the left side (non-decreasing part).
  - The height at j is min(maxHeights[j], prevHeight).
  - Add this height to currentSum and update prevHeight.
- Reset prevHeight to maxHeights[i].
- Iterate forwards from k = i + 1 to n-1 to calculate the sum of the right side (non-increasing part).
  - The height at k is min(maxHeights[k], prevHeight).
  - Add this height to currentSum and update prevHeight.
After calculating the currentSum for the peak i, update maxTotalSum = max(maxTotalSum, currentSum).
After iterating through all possible peaks, maxTotalSum will hold the result.

Walkthrough

The core idea is to iterate through all possible indices i from 0 to n-1 and assume each one is the peak of the mountain. When i is the peak, to maximize the total sum, we should set heights[i] to its maximum possible value, which is maxHeights.get(i).

For the left side of the peak (j < i), the heights must be non-decreasing, i.e., heights[j] <= heights[j+1]. To maximize the sum, we set heights[j] to the largest value possible, which is min(maxHeights.get(j), heights[j+1]). We can calculate these heights and their sum by iterating from i-1 down to 0.

Similarly, for the right side of the peak (k > i), the heights must be non-increasing, i.e., heights[k] <= heights[k-1]. We set heights[k] = min(maxHeights.get(k), heights[k-1]) and calculate the sum by iterating from i+1 up to n-1.

The sum for a given peak i is the sum of all these calculated heights. We keep track of the maximum sum found across all iterations.

1import java.util.List;2 3class Solution {4    public long maximumSumOfHeights(List<Integer> maxHeights) {5        int n = maxHeights.size();6        long maxTotalSum = 0;7 8        for (int i = 0; i < n; i++) {9            long currentSum = maxHeights.get(i);10            11            // Calculate sum for the left side (non-decreasing)12            long prevHeight = maxHeights.get(i);13            for (int j = i - 1; j >= 0; j--) {14                long currentHeight = Math.min(maxHeights.get(j), prevHeight);15                currentSum += currentHeight;16                prevHeight = currentHeight;17            }18 19            // Calculate sum for the right side (non-increasing)20            prevHeight = maxHeights.get(i);21            for (int k = i + 1; k < n; k++) {22                long currentHeight = Math.min(maxHeights.get(k), prevHeight);23                currentSum += currentHeight;24                prevHeight = currentHeight;25            }26 27            maxTotalSum = Math.max(maxTotalSum, currentSum);28        }29 30        return maxTotalSum;31    }32}

Complexity

Time

O(N^2), where N is the number of towers. The outer loop runs N times for each potential peak, and the inner loops for calculating left and right sums take O(N) time in total for each peak.

Space

O(1) extra space, as we only use a few variables to store the current sums and heights during calculation.

Trade-offs

Pros

Simple to understand and implement.
It correctly solves the problem for smaller input sizes.

Cons

This approach is too slow for the given constraints (n up to 10^5) and will likely result in a Time Limit Exceeded (TLE) error.

Solutions

Solution

1class Solution {2public3  long maximumSumOfHeights(List<Integer> maxHeights) {4    int n = maxHeights.size();5    Deque<Integer> stk = new ArrayDeque<>();6    int[] left = new int[n];7    int[] right = new int[n];8    Arrays.fill(left, -1);9    Arrays.fill(right, n);10    for (int i = 0; i < n; ++i) {11      int x = maxHeights.get(i);12      while (!stk.isEmpty() && maxHeights.get(stk.peek()) > x) {13        stk.pop();14      }15      if (!stk.isEmpty()) {16        left[i] = stk.peek();17      }18      stk.push(i);19    }20    stk.clear();21    for (int i = n - 1; i >= 0; --i) {22      int x = maxHeights.get(i);23      while (!stk.isEmpty() && maxHeights.get(stk.peek()) >= x) {24        stk.pop();25      }26      if (!stk.isEmpty()) {27        right[i] = stk.peek();28      }29      stk.push(i);30    }31    long[] f = new long[n];32    long[] g = new long[n];33    for (int i = 0; i < n; ++i) {34      int x = maxHeights.get(i);35      if (i > 0 && x >= maxHeights.get(i - 1)) {36        f[i] = f[i - 1] + x;37      } else {38        int j = left[i];39        f[i] = 1L * x * (i - j) + (j >= 0 ? f[j] : 0);40      }41    }42    for (int i = n - 1; i >= 0; --i) {43      int x = maxHeights.get(i);44      if (i < n - 1 && x >= maxHeights.get(i + 1)) {45        g[i] = g[i + 1] + x;46      } else {47        int j = right[i];48        g[i] = 1L * x * (j - i) + (j < n ? g[j] : 0);49      }50    }51    long ans = 0;52    for (int i = 0; i < n; ++i) {53      ans = Math.max(ans, f[i] + g[i] - maxHeights.get(i));54    }55    return ans;56  }57}

1class Solution {2public:3  long long maximumSumOfHeights(vector<int> &maxHeights) {4    int n = maxHeights.size();5    stack<int> stk;6    vector<int> left(n, -1);7    vector<int> right(n, n);8    for (int i = 0; i < n; ++i) {9      int x = maxHeights[i];10      while (!stk.empty() && maxHeights[stk.top()] > x) {11        stk.pop();12      }13      if (!stk.empty()) {14        left[i] = stk.top();15      }16      stk.push(i);17    }18    stk = stack<int>();19    for (int i = n - 1; ~i; --i) {20      int x = maxHeights[i];21      while (!stk.empty() && maxHeights[stk.top()] >= x) {22        stk.pop();23      }24      if (!stk.empty()) {25        right[i] = stk.top();26      }27      stk.push(i);28    }29    long long f[n], g[n];30    for (int i = 0; i < n; ++i) {31      int x = maxHeights[i];32      if (i && x >= maxHeights[i - 1]) {33        f[i] = f[i - 1] + x;34      } else {35        int j = left[i];36        f[i] = 1LL * x * (i - j) + (j != -1 ? f[j] : 0);37      }38    }39    for (int i = n - 1; ~i; --i) {40      int x = maxHeights[i];41      if (i < n - 1 && x >= maxHeights[i + 1]) {42        g[i] = g[i + 1] + x;43      } else {44        int j = right[i];45        g[i] = 1LL * x * (j - i) + (j != n ? g[j] : 0);46      }47    }48    long long ans = 0;49    for (int i = 0; i < n; ++i) {50      ans = max(ans, f[i] + g[i] - maxHeights[i]);51    }52    return ans;53  }54};

1class Solution:2    def maximumSumOfHeights(self, maxHeights: List[int]) -> int: n = len(maxHeights) stk = [] left = [- 1] * n for i, x in enumerate(maxHeights): while stk and maxHeights[stk[- 1]] > x: stk . pop() if stk: left[i] = stk[- 1] stk . append(i) stk = [] right = [n] * n for i in range(n - 1, - 1, - 1): x = maxHeights[i] while stk and maxHeights[stk[- 1]] >= x: stk . pop() if stk: right[i] = stk[- 1] stk . append(i) f = [0] * n for i, x in enumerate(maxHeights): if i and x >= maxHeights[i - 1]: f[i] = f[i - 1] + x else: j = left[i] f[i] = x * (i - j) + (f[j] if j != - 1 else 0) g = [0] * n for i in range(n - 1, - 1, - 1): if i < n - 1 and maxHeights[i] >= maxHeights[i + 1]: g[i] = g[i + 1] + maxHeights[i] else: j = right[i] g[i] = maxHeights[i] * (j - i) + (g[j] if j != n else 0) return max(a + b - c for a, b, c in zip(f, g, maxHeights))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem