How do you solve Beautiful Towers I on LeetCode?

Beautiful Towers I (LeetCode #2865) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: The peak can be any index, and the heights must decrease on both sides.

What is the brute force solution for Beautiful Towers I?

The brute force approach for Beautiful Towers I is Brute Force, with O(n²) time complexity and O(1) space complexity. We can try every possible index as a peak and adjust the heights of the towers accordingly. This means we will check each peak and calculate the maximum sum of heights for that configuration. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Beautiful Towers I?

Beautiful Towers I uses the following concepts: Array, Stack, Monotonic Stack. The recommended patterns to study are: Monotonic Stack, Dynamic Programming.

What are the interview tips for Beautiful Towers I?

Always consider edge cases, such as arrays with only one or two elements. Explain your thought process clearly while coding, as it helps the interviewer understand your approach.

What are common mistakes when solving Beautiful Towers I?

Not restoring the original heights after each peak check in the brute force approach. Overcomplicating the logic for adjusting heights.

#2865

Beautiful Towers I

Medium

ArrayStackMonotonic StackMonotonic StackDynamic Programming

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

We can efficiently calculate the maximum mountain sum by using two passes to determine the left and right limits for each tower. This way, we can directly compute the mountain heights without needing to adjust the array multiple times.

⚙️

Algorithm

4 steps

1Step 1: Create two arrays, left and right, to store the maximum heights for each tower when considering the peak.
2Step 2: Fill the left array by iterating from left to right, ensuring each tower does not exceed the height of the previous tower.
3Step 3: Fill the right array by iterating from right to left in a similar manner.
4Step 4: Calculate the total height for each peak by taking the minimum of the left and right arrays at that index and summing them up.

solution.py14 lines

1def maxMountainSum(heights):
2    n = len(heights)
3    left = [0] * n
4    right = [0] * n
5    left[0] = heights[0]
6    for i in range(1, n):
7        left[i] = min(left[i - 1], heights[i])
8    right[n - 1] = heights[n - 1]
9    for i in range(n - 2, -1, -1):
10        right[i] = min(right[i + 1], heights[i])
11    max_sum = 0
12    for i in range(n):
13        max_sum += min(left[i], right[i])
14    return max_sum

ℹ

Complexity note: The time complexity is O(n) because we make three passes through the array (one for left, one for right, and one for summation). The space complexity is O(n) due to the additional arrays used to store left and right limits.

1The peak can be any index, and the heights must decrease on both sides.
2Using two passes allows us to efficiently calculate the limits for each tower.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.