LeetCode 2865 - Beautiful Towers I

The problem asks us to transform an array of tower heights into a mountain-shaped arrangement while removing as few bricks as necessary.

leetcodemediumarraystackmonotonic-stack

LeetCode Problem 2865

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

Solution

Problem Understanding

The problem asks us to transform an array of tower heights into a mountain-shaped arrangement while removing as few bricks as necessary. A mountain-shaped arrangement is defined as one where tower heights first non-decrease up to a peak (or consecutive peaks of the same height) and then non-increase after the peak. We are not allowed to increase tower heights; we can only remove bricks to achieve this shape. The goal is to maximize the sum of tower heights in the resulting mountain shape.

The input is an array heights of n integers, each representing the height of a tower. The constraints indicate that n can be up to 10^3 and each height can be up to 10^9. This tells us that an O(n^2) approach may still be feasible, but anything worse will likely be too slow.

Important edge cases include arrays that are already non-increasing, non-decreasing, or have multiple possible peaks. Since we are only allowed to remove bricks, the solution must never increase any tower height. Additionally, the array could be as small as length 1, in which case the single tower is trivially a mountain.

Approaches

Brute Force

A naive approach would be to consider every possible peak position and try to adjust the left and right sides to form a valid mountain. For each peak, we iterate leftwards, reducing heights to maintain non-decreasing order, and iterate rightwards, reducing heights to maintain non-increasing order. We sum the adjusted heights and take the maximum across all peaks.

While correct, this approach requires iterating over all n possible peaks and performing O(n) work on both sides for each peak, leading to O(n^2) time. This is acceptable for n = 1000, but it can be optimized.

Optimal Approach

The key observation is that forming a valid mountain with a peak at each position is essentially computing two arrays: the maximum sum of heights for a non-increasing sequence from the left and the maximum sum of heights for a non-increasing sequence from the right. Using a monotonic stack, we can efficiently compute the maximum sum for each position by storing the cumulative contributions of each tower constrained by the previous heights. This reduces the repeated work of adjusting left and right sequences and allows us to compute the maximum possible mountain sum in linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Try each peak and adjust heights left and right
Optimal O(n) O(n) Use monotonic stacks to precompute left/right sums efficiently

Algorithm Walkthrough

  1. Initialize two arrays, left and right, of length n to store the maximum sum of heights achievable to the left and right of each index under the non-increasing constraint.
  2. Traverse the array from left to right using a monotonic increasing stack. For each tower, if the current height is smaller than the height at the top of the stack, pop from the stack. Maintain a running sum of the heights constrained by the previous minimum. Store the sum in left[i].
  3. Repeat a similar process from right to left to compute the right array.
  4. For each position i, the maximum mountain sum with a peak at i is left[i] + right[i] - heights[i] (subtract heights[i] to avoid double-counting the peak).
  5. Return the maximum value over all positions.

Why it works: The monotonic stack ensures that each tower contributes optimally to the sum under the non-increasing constraint. By computing left and right contributions separately, we can efficiently determine the maximum sum for any peak without recomputing adjusted sequences repeatedly.

Python Solution

from typing import List

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

        # Compute left sums
        stack = []
        for i in range(n):
            count = 1
            while stack and stack[-1][0] > heights[i]:
                h, c = stack.pop()
                count += c
            stack.append((heights[i], count))
            left[i] = sum(h * c for h, c in stack)

        # Compute right sums
        stack = []
        for i in range(n-1, -1, -1):
            count = 1
            while stack and stack[-1][0] > heights[i]:
                h, c = stack.pop()
                count += c
            stack.append((heights[i], count))
            right[i] = sum(h * c for h, c in stack)

        # Combine left and right sums
        max_sum = 0
        for i in range(n):
            max_sum = max(max_sum, left[i] + right[i] - heights[i])
        return max_sum

This Python implementation first computes the left sums using a monotonic stack that collapses taller towers to the current height. It repeats symmetrically for the right sums. Finally, it combines the left and right sums to compute the maximum mountain sum.

Go Solution

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

    type pair struct{ h, c int64 }

    stack := []pair{}
    for i := 0; i < n; i++ {
        count := int64(1)
        h := int64(heights[i])
        for len(stack) > 0 && stack[len(stack)-1].h > h {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            count += top.c
        }
        stack = append(stack, pair{h, count})
        sum := int64(0)
        for _, p := range stack {
            sum += p.h * p.c
        }
        left[i] = sum
    }

    stack = []pair{}
    for i := n - 1; i >= 0; i-- {
        count := int64(1)
        h := int64(heights[i])
        for len(stack) > 0 && stack[len(stack)-1].h > h {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            count += top.c
        }
        stack = append(stack, pair{h, count})
        sum := int64(0)
        for _, p := range stack {
            sum += p.h * p.c
        }
        right[i] = sum
    }

    maxSum := int64(0)
    for i := 0; i < n; i++ {
        total := left[i] + right[i] - int64(heights[i])
        if total > maxSum {
            maxSum = total
        }
    }
    return maxSum
}

In Go, we handle integer overflow by converting tower heights to int64 early. The monotonic stack logic is analogous to Python, using a slice of structs to store height and count.

Worked Examples

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

  1. Left sums: [5, 3+3, 3+3+3, 1+1+1+1, 1+1+1+1+1] = [5,6,9,12,13]
  2. Right sums: [5+3+3+1+1, 3+3+1+1, 3+1+1, 1+1, 1] = [13,8,5,2,1]
  3. Maximum mountain sum: pick peak at index 0: left[0] + right[0] - heights[0] = 5+13-5=13

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

  1. Left sums and right sums computed via monotonic stack.
  2. Maximum sum occurs with peak at index 3 (9): sum = 22.

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

  1. Maximum sum occurs with peak at index 2 or 3 (5): sum = 18.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each tower is pushed/popped at most once in the monotonic stack for left and right sums
Space O(n) Arrays left and right, plus the stack of at most n elements

Because each element interacts with the stack only once per pass, the algorithm achieves linear time and linear space.

Test Cases

# provided examples
assert Solution().maximumSumOfHeights([5,3,4,1,1]) == 13  # peak at index 0
assert Solution().maximumSumOfHeights([6,5,3,9,2,7]) == 22  # peak at index 3
assert Solution().maximumSumOfHeights([3,2,5,5,2,3]) == 18  # peak at index 2 or 3

# edge and boundary cases
assert Solution().maximumSumOfHeights([1]) == 1  # single element
assert Solution().maximumSum