Watch 10 video solutions for Beautiful Towers I, a medium level problem involving Array, Stack, Monotonic Stack. This walkthrough by codingMohan has 3,183 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |