Beautiful Towers I

Beautiful Towers I

What is this problem about?

The "Beautiful Towers I interview question" is an optimization problem involving heights. You are given an array of "maximum heights" for a row of towers. You need to assign an actual height to each tower such that:

1. $0 < height[i] \leq maxHeight[i]$.
2. The towers form a "mountain" shape. This means there is a peak at index $i$, and heights decrease (or stay equal) as you move away from the peak to both the left and right. Your goal is to find the maximum possible sum of all tower heights.

Why is this asked in interviews?

Meta and Salesforce ask the "Beautiful Towers I coding problem" to evaluate a candidate's ability to handle array traversals and optimization. While the first version of this problem allows for a simpler $O(n^2)$ solution, it sets the stage for more advanced "Monotonic Stack interview pattern" techniques used in the harder variation.

Algorithmic pattern used

For the "Easy/Medium" version, we use an Exhaustive Peak Search.

1. Iterate through every possible peak: Assume each index $i$ is the highest point of the mountain.
2. Left Expansion: Starting from the peak, move left. Each tower's height is the minimum of its maxHeight and the height of the tower to its right.
3. Right Expansion: Starting from the peak, move right. Each tower's height is the minimum of its maxHeight and the height of the tower to its left.
4. Sum and Compare: Calculate the total sum for this peak and keep track of the maximum sum found across all indices.

Example explanation

maxHeights = [5, 3, 4, 1, 1]

• If peak is at index 2 (value 4):
  • Right: 1, 1 (limited by 1).
  • Left: 3, 3 (limited by 3).
  • Arrangement: [3, 3, 4, 1, 1]. Sum = 12.
• If peak is at index 0 (value 5):
  • Right: 3, 3, 1, 1 (limited by subsequent smaller values).
  • Arrangement: [5, 3, 3, 1, 1]. Sum = 13. The maximum sum is 13.

Common mistakes candidates make

• Violating constraints: Setting a height that is greater than the allowed maxHeight for that position.
• Incorrect mountain logic: Forgetting that heights must be non-increasing as you move away from the peak (meaning they can stay the same, but not go up).
• Inefficient summing: Recalculating the whole sum inside nested loops unnecessarily.

Interview preparation tip

Mountain-array problems are very common. Always start by identifying the "peak." If the constraints are small, a "try every peak" strategy is acceptable. For larger constraints, you'll need to pre-calculate prefix and suffix sums using a monotonic stack.