Skip to main content
Talentd

Beautiful Towers II - Solution & Explanation

MediumArrayStackMonotonic Stack20 min readAsked at: Salesforce
Practice this problem

Problem Statement

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. 1 <= heights[i] <= maxHeights[i]
  2. 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.

 

Example 1:

Input: maxHeights = [5,3,4,1,1]
Output: 13
Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]  
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.

Example 2:

Input: maxHeights = [6,5,3,9,2,7]
Output: 22
Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.

Example 3:

Input: maxHeights = [3,2,5,5,2,3]
Output: 18
Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.

 

Constraints:

  • 1 <= n == maxHeights.length <= 105
  • 1 <= maxHeights[i] <= 109

Approach Overview

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.

Approach 1: Greedy Two-Pass Approach

The key idea of this approach is to use a greedy strategy with two passes across the array. In the first pass, construct a potential upward slope where each height is limited to the corresponding maxHeights value. In the second pass, adjust the heights to ensure a downward slope, ensuring that none of the heights exceed what was set in the greedy pass.

By ensuring that we respect the mountain property during both passes and not violate the maximum height constraint, we accomplish obtaining the maximum beautiful tower configuration.

This C implementation employs a two-pass approach to enforce increasing and then decreasing conditions on the heights array. It calculates the maximum possible sum while respecting the maxHeights constraint.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), as we traverse the list twice.
Space Complexity: O(n), due to the heights array.

Try this approach in the editor →

Approach 2: Binary Search Approach

This approach explores using a binary search methodology to find the peak of the mountain that satisfies all constraints. By searching for the maximum possible peak, we iteratively check for valid mountain configurations and adjust the search bounds accordingly. This allows constructing a potentially optimal height configuration for maximum sum.

Explanation for binary approach in C. To be implemented...

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n).
Space Complexity: O(n). To be specified...

Try this approach in the editor →

Approach 3: Dynamic Programming + Monotonic Stack

We define f[i] to represent the height sum of the beautiful tower scheme with the last tower as the tallest tower among the first i+1 towers. We can get the following state transition equation:

$ f[i]= \begin{cases} f[i-1]+heights[i],&if heights[i]geq heights[i-1]\ heights[i]times(i-j)+f[j],&if heights[i]<heights[i-1] \end{cases}

Where j is the index of the first tower to the left of the last tower with a height less than or equal to heights[i]. We can use a monotonic stack to maintain this index.

We can use a similar method to find g[i], which represents the height sum of the beautiful tower scheme from right to left with the ith tower as the tallest tower. The final answer is the maximum value of f[i]+g[i]-heights[i].

The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array maxHeights$.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Greedy Two-Pass Approach

Time Complexity: O(n), as we traverse the list twice.
Space Complexity: O(n), due to the heights array.

Binary Search Approach

Time Complexity: O(n log n).
Space Complexity: O(n). To be specified...

Dynamic Programming + Monotonic Stack—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Greedy Two-Pass Monotonic StackO(n)O(n)Best general solution. Computes contributions for every peak efficiently.
Binary Search Peak ExpansionO(n log n)O(n)Useful when reasoning with boundaries and prefix constraints instead of stacks.

Video Solution

Leetcode weekly contest 364 | Beautiful Tower 1 & Beautiful tower 2 | Hindi Explanation • Pawan Kumar Giri • 5,301 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Beautiful Towers II easy or hard?
Beautiful Towers II is generally classified as a Medium difficulty problem. The challenge comes from recognizing the monotonic stack pattern and computing segment contributions efficiently instead of simulating every possible peak.
Beautiful Towers II Python/Java solution
Python and Java implementations follow the same logic: maintain a monotonic stack while computing prefix contributions from both directions. Arrays store the cumulative sums for left and right expansions, and the maximum combined value across all peaks is returned.
How to solve Beautiful Towers II in O(n)?
Use a monotonic increasing stack to process the array from left to right and compute the maximum valid contribution ending at each index. Repeat the process from right to left to compute the symmetric contribution. For every index as a peak, add left and right sums and subtract the peak once to avoid double counting.
What is the best approach for Beautiful Towers II?
The optimal approach uses a greedy two-pass algorithm with a monotonic stack. One pass computes the best contribution from the left side and another from the right side while maintaining decreasing height constraints. Combining both values for every index gives the best peak configuration in O(n) time and O(n) space.
Is Beautiful Towers II asked at Google/Amazon/Meta?
Problems involving monotonic stacks and range constraints frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying pattern—using stacks to maintain monotonic sequences and compute range contributions—is a common interview topic.
What data structure is used in Beautiful Towers II?
The core data structure is a monotonic stack. It keeps indices in increasing height order so the algorithm can quickly determine where a decreasing constraint breaks and recompute segment contributions efficiently.
What is the time complexity of Beautiful Towers II?
The optimal solution runs in O(n) time using a monotonic stack. Each index is pushed and popped at most once during the left and right passes. The space complexity is O(n) for storing stack indices and prefix contribution arrays.

Ready to solve this problem?

Practice Beautiful Towers II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Maximum Number of Books You Can Take

Next

Minimum Number of Removals to Make Mountain Array