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 <= 1031 <= heights[i] <= 109Problem Overview: You are given an array maxHeights where each element represents the maximum height allowed at that position. You must build towers such that heights form a mountain shape around a chosen peak (non‑increasing when moving away from the peak) while staying ≤ maxHeights[i]. The goal is to maximize the total sum of tower heights.
Approach 1: Using Sorting (O(n log n) time, O(n) space)
This approach treats each index as a potential peak candidate but processes them in descending order of maxHeights using sorting. By considering taller peaks first, you attempt to expand left and right while ensuring the mountain constraint (heights cannot increase when moving away from the peak). A structure such as a balanced set or boundary tracking helps identify where expansion stops when a smaller tower limits growth. The sum is updated by assigning the minimum possible height while moving outward. Sorting costs O(n log n), and expansion logic keeps overall complexity near O(n log n) with O(n) auxiliary space.
Approach 2: Linear Scan with Monotonic Stack (O(n) time, O(n) space)
The optimal strategy computes the best contribution when each index acts as the peak. Use a monotonic stack to calculate the maximum valid sum extending left and right while maintaining non‑increasing heights. During the left pass, maintain a stack of indices with increasing heights and accumulate valid prefix sums by limiting each tower with the nearest smaller element. Repeat the same logic from right to left to compute suffix contributions. For each index i, combine left[i] + right[i] - maxHeights[i] to avoid double counting the peak. The stack ensures every element is pushed and popped once, giving O(n) time and O(n) space.
Recommended for interviews: The monotonic stack solution is what interviewers typically expect because it reduces the naive peak expansion idea to O(n). Discussing the simpler peak expansion or sorted candidate idea first shows understanding, but implementing the stack-based optimization demonstrates strong knowledge of array processing and stack patterns used in many range‑constraint problems.
This approach involves sorting the input array and then applying the logic to find the desired result. Sorting helps in simplifying certain problems by bringing the elements into a predictable order, which can be useful for easier comparisons or aggregation of results.
Python: The solution starts by sorting the array using Python's built-in sort function, which is O(n log n). After sorting, the smallest pair can be found directly by accessing the first two elements of the sorted list. These elements form the smallest possible pair.
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) if we ignore the input array space, otherwise O(n) due to sorting if a new array is created.
This approach involves scanning the array in a single pass to identify the two smallest elements. It maintains two variables to track the smallest and second smallest items encountered so far.
Python: This solution initializes two variables to infinity. As we iterate over the list, we update these variables to keep track of the minimum and second minimum elements. After traversing the list, we return these values as the smallest pair. This ensures an O(n) time complexity.
Time Complexity: O(n) as it requires a single scan through the list.
Space Complexity: O(1) due to constant space usage.
We can enumerate each tower as the tallest tower, each time expanding to the left and right, calculating the height of each other position, and then accumulating to get the height sum t. The maximum of all height sums is the answer.
The time complexity is O(n^2), and the space complexity is O(1). Here, n is the length of the array maxHeights.
Python
Java
C++
Go
TypeScript
Solution 1 is sufficient to pass this problem, but the time complexity is relatively high. We can use "Dynamic Programming + Monotonic Stack" to optimize the enumeration process.
We define f[i] to represent the height sum of the beautiful tower scheme with the last tower as the tallest tower among the first i+1 towers. We can get the following state transition equation:
$
f[i]=
\begin{cases}
f[i-1]+heights[i],&if heights[i]geq heights[i-1]\
heights[i]times(i-j)+f[j],&if heights[i]<heights[i-1]
\end{cases}
Where j is the index of the first tower to the left of the last tower with a height less than or equal to heights[i]. We can use a monotonic stack to maintain this index.
We can use a similar method to find g[i], which represents the height sum of the beautiful tower scheme from right to left with the ith tower as the tallest tower. The final answer is the maximum value of f[i]+g[i]-heights[i].
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array maxHeights$.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Sorting | Time Complexity: O(n log n) due to sorting. |
| Approach 2: Linear Scan | Time Complexity: O(n) as it requires a single scan through the list. |
| Enumeration | — |
| Dynamic Programming + Monotonic Stack | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting Peak Candidates | O(n log n) | O(n) | Useful when exploring candidate peaks by height priority or when combining with ordered data structures. |
| Linear Scan with Monotonic Stack | O(n) | O(n) | Best general solution. Efficient for large arrays and common in interviews involving nearest smaller element constraints. |
2865. Beautiful Towers I | 2866. Beautiful Towers II | Weekly Leetcode 364 • codingMohan • 3,183 views views
Watch 9 more video solutions →Practice Beautiful Towers I with our built-in code editor and test cases.
Practice on FleetCode