2865. Beautiful Towers I LeetCode Solution

Last updated: March 5, 2025

In this guide, you will get 2865. Beautiful Towers I LeetCode Solution with the best time and space complexity. The solution to Beautiful Towers I 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 I solution in C++
Beautiful Towers I solution in Java
Beautiful Towers I solution in Python
Additional Resources

2865. Beautiful Towers I LeetCode Solution image

Problem Statement of Beautiful Towers I

You are given an array heights of n integers representing the number of bricks in n consecutive towers. Your task is to remove some bricks to form a mountain-shaped tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing.
Return the maximum possible sum of heights of a mountain-shaped tower arrangement.

Example 1:

Input: heights = [5,3,4,1,1]
Output: 13
Explanation:
We remove some bricks to make heights = [5,3,3,1,1], the peak is at index 0.

Example 2:

Input: heights = [6,5,3,9,2,7]
Output: 22
Explanation:
We remove some bricks to make heights = [3,3,3,9,2,2], the peak is at index 3.

Example 3:

Input: heights = [3,2,5,5,2,3]
Output: 18
Explanation:
We remove some bricks to make heights = [2,2,5,5,2,2], the peak is at index 2 or 3.

Constraints:

1 <= n == heights.length <= 103
1 <= heights[i] <= 109

Complexity Analysis

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

2865. Beautiful Towers I LeetCode Solution in C++

class Solution {
 public:
  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 */

2865. Beautiful Towers I LeetCode Solution in Java

class Solution {
  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

2865. Beautiful Towers I LeetCode Solution in Python

class Solution:
  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