2866. Beautiful Towers II LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2866. Beautiful Towers II LeetCode Solution with the best time and space complexity. The solution to Beautiful Towers II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Beautiful Towers II solution in C++
Beautiful Towers II solution in Java
Beautiful Towers II solution in Python
Additional Resources

2866. Beautiful Towers II LeetCode Solution image

Problem Statement of Beautiful Towers II

You are given a 0-indexed array maxHeights of n integers.
You are tasked with building n towers in the coordinate line. The ith 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 <= 105
1 <= maxHeights[i] <= 109

Complexity Analysis

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

2866. Beautiful Towers II LeetCode Solution in C++

class Solution {
 public:
  // Same as 2865. Beautiful Towers I
  long long maximumSumOfHeights(vector<int>& maxHeights) {
    const int n = maxHeights.size();
    vector<long> maxSum(n);  // maxSum[i] := the maximum sum with peak i

    stack<int> stack{{-1}};
    long summ = 0;

    for (int i = 0; i < n; ++i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] = summ;
    }

    stack = std::stack<int>{{n}};
    summ = 0;

    for (int i = n - 1; i >= 0; --i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] += summ - maxHeights[i];
    }

    return ranges::max(maxSum);
  }

 private:
  long process(stack<int>& stack, vector<int>& maxHeights, int i, long summ) {
    while (stack.size() > 1 && maxHeights[stack.top()] > maxHeights[i]) {
      int j = stack.top();
      stack.pop();
      // The last abs(j - stack.top()) heights are maxHeights[j].
      summ -= abs(j - stack.top()) * static_cast<long>(maxHeights[j]);
    }
    // Put abs(i - stack.top()) * maxHeights[i] in `heights`.
    summ += abs(i - stack.top()) * static_cast<long>(maxHeights[i]);
    stack.push(i);
    return summ;
  }
};
/* code provided by PROGIEZ */

2866. Beautiful Towers II LeetCode Solution in Java

class Solution {
  // Same as 2865. Beautiful Towers I
  public long maximumSumOfHeights(List<Integer> maxHeights) {
    final int n = maxHeights.size();
    long[] maxSum = new long[n]; // maxSum[i] := the maximum sum with peak i

    Deque<Integer> stack = new ArrayDeque<>(List.of(-1));
    stack.push(-1);
    long summ = 0;

    for (int i = 0; i < n; ++i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] = summ;
    }

    stack = new ArrayDeque<>(List.of(n));
    summ = 0;

    for (int i = n - 1; i >= 0; --i) {
      summ = process(stack, maxHeights, i, summ);
      maxSum[i] += summ - maxHeights.get(i);
    }

    return Arrays.stream(maxSum).max().getAsLong();
  }

  private long process(Deque<Integer> stack, List<Integer> maxHeights, int i, long summ) {
    while (stack.size() > 1 && maxHeights.get(stack.peek()) > maxHeights.get(i)) {
      final int j = stack.pop();
      // The last abs(j - stack.peek()) heights are maxHeights.get(j).
      summ -= Math.abs(j - stack.peek()) * (long) maxHeights.get(j);
    }
    // Put abs(i - stack.peek()) `maxHeights.get(i)` in heights.
    summ += Math.abs(i - stack.peek()) * (long) maxHeights.get(i);
    stack.push(i);
    return summ;
  }
}
// code provided by PROGIEZ

2866. Beautiful Towers II LeetCode Solution in Python

class Solution:
  # Same as 2865. Beautiful Towers I
  def maximumSumOfHeights(self, maxHeights: list[int]) -> int:
    n = len(maxHeights)
    maxSum = [0] * n  # maxSum[i] := the maximum sum with peak i

    def process(stack: list[int], i: int, summ: int) -> int:
      while len(stack) > 1 and maxHeights[stack[-1]] > maxHeights[i]:
        j = stack.pop()
        # The last abs(j - stack[-1]) heights are maxHeights[j].
        summ -= abs(j - stack[-1]) * maxHeights[j]
      # Put abs(i - stack[-1]) `maxHeight` in heights.
      summ += abs(i - stack[-1]) * maxHeights[i]
      stack.append(i)
      return summ

    stack = [-1]
    summ = 0
    for i in range(len(maxHeights)):
      summ = process(stack, i, summ)
      maxSum[i] = summ

    stack = [n]
    summ = 0
    for i in range(n - 1, -1, -1):
      summ = process(stack, i, summ)
      maxSum[i] += summ - maxHeights[i]

    return max(maxSum)
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents