LeetCode 2866 - Beautiful Towers II

Difficulty: 🟡 Medium
Topics: Array, Stack, Monotonic Stack

Solution

Problem Understanding

The problem asks us to build a series of towers along a coordinate line, where each tower has a height constrained by a given maxHeights array. The resulting configuration must form a mountain array, meaning there is a single peak somewhere in the array, with tower heights non-decreasing up to the peak and non-increasing after the peak. Each tower's height must also be at least 1 and at most its corresponding maximum height from maxHeights.

The goal is to maximize the sum of all tower heights while respecting the mountain shape and individual height constraints. The output is therefore a single integer, the maximum possible sum achievable under these rules.

The constraints tell us that n can be up to 10^5, and the heights themselves can be up to 10^9. This immediately indicates that any naive solution that tries all possible mountain peaks and permutations of heights is infeasible. We need a method that operates in linear or near-linear time.

Edge cases that could be tricky include arrays that are strictly increasing, strictly decreasing, contain repeated maximum heights, or have minimum height values (1). The problem guarantees that each maxHeights[i] >= 1, so we never need to worry about zero or negative heights.

Approaches

Brute Force

A naive approach would be to try every index as a potential mountain peak. For each peak, you would attempt to propagate heights to the left, making them non-decreasing toward the peak and no larger than their respective maximums. Similarly, propagate heights to the right, making them non-increasing from the peak while staying under the maximums. After building each possible mountain, sum the heights and track the maximum sum seen.

This approach is correct but inefficient. For each of n potential peaks, building the left and right sequences requires O(n) work, resulting in an overall O(n^2) complexity. Given n can reach 10^5, this is far too slow.

Optimal Approach

The key observation is that the height of each tower is limited not only by its maxHeights but also by the adjacent towers to maintain the mountain property. This is a classic monotonic sequence problem. We can precompute the maximum valid height sum from the left and from the right for each position using a monotonic stack, which ensures we respect the increasing and decreasing constraints efficiently.

By calculating two auxiliary arrays: leftSum[i] representing the maximum sum of a valid increasing sequence ending at i, and rightSum[i] representing the maximum sum of a valid decreasing sequence starting at i, we can combine them at each potential peak. This yields the maximum sum for a mountain peaked at i in O(n) time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Try each index as a peak, propagate left/right heights, sum heights.
Optimal	O(n)	O(n)	Use monotonic stack to compute left/right max sums and combine at each peak.

Algorithm Walkthrough

Initialize two arrays, left and right, both of size n, which will store the maximum height achievable for each position when growing a mountain from the left and from the right, respectively.
Traverse the array from left to right. For each tower, the maximum height it can take is the minimum of maxHeights[i] and the previous tower's height plus 1 (to maintain non-decreasing property). Store these values in left.
Traverse the array from right to left. Similarly, calculate the maximum valid height from the right, ensuring non-increasing property, and store them in right.
Initialize maxSum = 0. For each index i, compute the mountain sum if i is the peak as follows: take the minimum of left[i] and right[i] as the peak height, then adjust the left and right sequences accordingly to compute the total sum.
Return maxSum.

Why it works: The monotonic stack ensures that each tower's height is maximized given the constraints of neighboring towers, both for the increasing part of the mountain and the decreasing part. By combining the precomputed left and right maximum sequences, we guarantee that the configuration for each potential peak is optimal.

Python Solution

from typing import List

class Solution:
    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
        n = len(maxHeights)
        left = [0] * n
        right = [0] * n

        # Compute left max heights
        for i in range(n):
            if i == 0:
                left[i] = maxHeights[i]
            else:
                left[i] = min(maxHeights[i], left[i - 1] + 1)

        # Compute right max heights
        for i in range(n - 1, -1, -1):
            if i == n - 1:
                right[i] = maxHeights[i]
            else:
                right[i] = min(maxHeights[i], right[i + 1] + 1)

        # Find maximum sum mountain
        maxSum = 0
        for i in range(n):
            peak = min(left[i], right[i])

            # Expand to left
            total = peak
            for j in range(i - 1, -1, -1):
                peak = min(peak, left[j])
                total += peak

            # Reset peak for right expansion
            peak = min(left[i], right[i])
            for j in range(i + 1, n):
                peak = min(peak, right[j])
                total += peak

            maxSum = max(maxSum, total)

        return maxSum

Explanation: First, we precompute maximum allowed heights from left and right respecting monotonicity. Then, for each potential peak, we compute the full mountain sum by expanding to both sides and adjusting each step to not exceed either the left/right constraints. This guarantees that we maximize the sum for that peak.

Go Solution

func maximumSumOfHeights(maxHeights []int) int64 {
    n := len(maxHeights)
    left := make([]int, n)
    right := make([]int, n)

    for i := 0; i < n; i++ {
        if i == 0 {
            left[i] = maxHeights[i]
        } else {
            if left[i-1]+1 < maxHeights[i] {
                left[i] = left[i-1] + 1
            } else {
                left[i] = maxHeights[i]
            }
        }
    }

    for i := n - 1; i >= 0; i-- {
        if i == n-1 {
            right[i] = maxHeights[i]
        } else {
            if right[i+1]+1 < maxHeights[i] {
                right[i] = right[i+1] + 1
            } else {
                right[i] = maxHeights[i]
            }
        }
    }

    var maxSum int64 = 0
    for i := 0; i < n; i++ {
        peak := left[i]
        if right[i] < peak {
            peak = right[i]
        }

        total := peak
        p := peak
        for j := i - 1; j >= 0; j-- {
            if left[j] < p {
                p = left[j]
            }
            total += p
        }

        p = peak
        for j := i + 1; j < n; j++ {
            if right[j] < p {
                p = right[j]
            }
            total += p
        }

        if total > maxSum {
            maxSum = total
        }
    }

    return maxSum
}

Explanation: Go implementation mirrors Python, handling integer overflow by using int64 for sums. The arrays left and right capture the same maximum height constraints and expansions are performed similarly.

Worked Examples

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

Left max heights: [5,3,4,1,1]
Right max heights: [5,3,3,1,1]
Peak at index 0 gives maximum sum 5+3+3+1+1 = 13

Example 2: maxHeights = [6,5,3,9,2,7]

Left max: [6,5,3,4,2,3]
Right max: [3,3,3,9,2,2]
Peak at index 3 gives sum 3+3+3+9+2+2 = 22

Example 3: maxHeights = [3,2,5,5,2,3]

Left max: [3,3,5,5,2,3]
Right max: [3,2,5,5,2,2]
Peak at index 2 gives sum 2+2+5+5+2+2 = 18

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Because we expand left and right for each peak, in worst case n peaks * n expansions.
Space	O(n)	Two arrays of size n are used to store