Beautiful Towers II

Beautiful Towers II

What is this problem about?

The "Beautiful Towers II interview question" is the optimized version of the mountain-height problem. Like the first version, you must find a peak index such that the sum of heights (limited by maxHeight and forming a mountain shape) is maximized. However, the constraints are much larger ($n = 10^5$), requiring a linear $O(n)$ solution instead of the $O(n^2)$ brute force.

Why is this asked in interviews?

Companies like Salesforce and Amazon use the "Beautiful Towers II coding problem" to test a candidate's mastery of the Monotonic Stack. It requires pre-calculating the "cost" of making a mountain to the left and to the right for every single index. It evaluates advanced "Array interview pattern" skills and the ability to handle cumulative sums with stack-based boundaries.

Algorithmic pattern used

This problem is a classic application of the Monotonic Stack and Dynamic Programming patterns.

1. Prefix Sum (Left side): Use a stack to find the nearest smaller element to the left.
   • dp_left[i] stores the max sum of a non-decreasing sequence ending at i.
   • If stack is empty, all previous towers are limited by maxHeight[i].
   • If stack has index j, then towers from j+1 to i are limited by maxHeight[i], and we add dp_left[j].
2. Suffix Sum (Right side): Do the same logic from right to left to calculate dp_right[i].
3. Combine: The total sum for a peak at $i$ is dp_left[i] + dp_right[i] - maxHeight[i].
4. Result: The answer is the maximum of these combined sums.

Example explanation

maxHeights = [6, 5, 3, 9, 2]

1. To calculate dp_left[2] (value 3):
   • Nearest smaller to the left of 3 is none.
   • All 3 towers (6, 5, 3) become 3. dp_left[2] = 3 * 3 = 9.
2. To calculate dp_left[3] (value 9):
   • Nearest smaller is 3 at index 2.
   • Tower 3 stays 9. dp_left[3] = dp_left[2] + 9 = 18.
3. Repeat for the right side and find the best peak.

Common mistakes candidates make

• Stack implementation: Using the stack to store values instead of indices, making it impossible to calculate the "width" of the area limited by the current height.
• Double Counting the Peak: Forgetting to subtract the peak height once when adding the left and right DP arrays.
• Integer Overflow: Forgetting that the sum of $10^5$ heights can easily exceed a 32-bit integer.

Interview preparation tip

Master the "Nearest Smaller Element" pattern using a monotonic stack. It is the secret weapon for many linear-time array problems. Practice "Largest Rectangle in Histogram" and "Sum of Subarray Minimums" to build this intuition.