Beautiful Towers II - Solution & Explanation

Problem Overview: You are given an array maxHeights. You must build tower heights such that one index acts as a peak and heights decrease (or stay equal) as you move away from the peak in both directions, while never exceeding maxHeights[i]. The goal is to maximize the total sum of the chosen heights.

Approach 1: Greedy Two-Pass with Monotonic Stack (O(n) time, O(n) space)

The optimal solution treats every index as a potential peak and computes the best possible contribution from the left and right sides. The key observation: once the peak is fixed, heights must monotonically decrease outward. A monotonic increasing stack efficiently determines how far a height can extend before hitting a smaller constraint. During the left pass, iterate from left to right while maintaining a stack of indices whose heights are increasing; when a smaller value appears, pop until the constraint is satisfied and update the segment contribution. A symmetric pass from right to left computes right-side contributions. Combine the two prefix sums for each index to evaluate the total mountain height. This approach processes every element at most twice, giving O(n) time and O(n) space. It heavily relies on monotonic stack patterns commonly used in array range problems.

Approach 2: Binary Search Peak Expansion (O(n log n) time, O(n) space)

An alternative idea fixes a peak and determines how far heights can extend while maintaining the decreasing constraint. For each index, expand left and right while ensuring the chosen height never exceeds both the previous height and the allowed maxHeights. Prefix information can be used with binary search to find the nearest valid boundary where the decreasing rule breaks. Each expansion requires a log n search, producing O(n log n) total time. While slower than the stack method, it is easier to reason about if you think in terms of boundaries and prefix sums rather than maintaining a stack structure.

The greedy stack approach essentially converts the problem into a sequence of constrained segments. Each time a smaller height appears, previous segments collapse into a new segment with that smaller height. This avoids recomputing sums repeatedly and is the reason the algorithm stays linear.

Recommended for interviews: The O(n) greedy solution using a stack is the expected approach. Interviewers want to see recognition of the monotonic stack pattern and the ability to compute range contributions efficiently. Discussing the naive or boundary-search idea first shows problem understanding, but implementing the linear-time stack solution demonstrates strong algorithmic skill.