Beautiful Towers II - Problem

You are given a 0-indexed array maxHeights of n integers.

You are tasked with building n towers in the coordinate line. The ith tower is built at coordinate i and has a height of heights[i].

A configuration of towers is beautiful if the following conditions hold:

  • 1 <= heights[i] <= maxHeights[i]
  • heights is a mountain array

Array heights is a mountain if there exists an index i such that:

  • For all 0 < j <= i, heights[j - 1] <= heights[j]
  • For all i <= k < n - 1, heights[k + 1] <= heights[k]

Return the maximum possible sum of heights of a beautiful configuration of towers.

Input & Output

Example 1 — Basic Mountain
$ Input: maxHeights = [5,3,4,1,1]
Output: 14
💡 Note: Beautiful mountain with peak at index 2: heights = [4,4,4,1,1]. Sum = 4+4+4+1+1 = 14. This forms a valid mountain (non-decreasing to peak, non-increasing after).
Example 2 — Single Peak
$ Input: maxHeights = [6,5,3,9,2,7]
Output: 22
💡 Note: Best mountain has peak at index 3: heights = [3,5,3,9,2,2]. The left side increases where possible, right side decreases. Sum = 3+5+3+9+2+2 = 22.
Example 3 — Uniform Heights
$ Input: maxHeights = [3,2,5,5,2,3]
Output: 18
💡 Note: Mountain with peak at index 2 or 3: heights = [3,2,5,5,2,3]. Both positions give same result due to symmetry. Sum = 3+2+5+5+2+3 = 18.

Constraints

  • 1 ≤ maxHeights.length ≤ 105
  • 1 ≤ maxHeights[i] ≤ 109

Visualization

Tap to expand
Beautiful Towers II: Build Optimal MountainInput: maxHeights = [5,3,4,1,1]53411Maximum allowed heights at each positionOptimal Mountain Configuration (Peak at index 2):44411Mountain shape: increases to peak, then decreasesMaximum Sum = 4 + 4 + 4 + 1 + 1 = 14
Understanding the Visualization
1
Input
Array maxHeights = [5,3,4,1,1] defines height limits
2
Process
Try different peak positions and calculate mountain sums
3
Output
Return maximum possible sum = 14
Key Takeaway
🎯 Key Insight: For each peak position, greedily maximize heights while maintaining the mountain property to find the optimal sum
Asked in
Google 15 Microsoft 12 Amazon 8
25.0K Views
Medium Frequency
~25 min Avg. Time
890 Likes
Ln 1, Col 1
Smart Actions
💡 Explanation
AI Ready
💡 Suggestion Tab to accept Esc to dismiss
// Output will appear here after running code
Code Editor Closed
Click the red button to reopen