Beautiful Towers II

Medium
1411.

Beautiful Towers II

Beautiful Towers II is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Google interviews.

You will build n towers in a row; tower i must get a height heights[i] with 1 <= heights[i] <= maxHeights[i].

The arrangement is beautiful when the heights form a mountain: there is a peak index p such that heights never decrease from index 0 up to p, and never increase from p to index n - 1 (either side may be empty).

Return the largest possible sum of heights of a beautiful arrangement.

(The height bound below is tighter than the original problem's so that the answer fits in a 32-bit integer.)

Example 1

Input
maxHeights = [4,6,2,7,3]
Output
16
Explanation
Peak at index 1: `[4,6,2,2,2]`; a peak at index 3 (`[2,2,2,7,3]`) also gives 16.

Example 2

Input
maxHeights = [3,3,3]
Output
9

Example 3

Input
maxHeights = [1,5,1]
Output
7

Constraints

  • 1 <= maxHeights.length <= 10^5
  • 1 <= maxHeights[i] <= 2 * 10^4
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} maxHeights
 * @return {number}
 */
var maximumSumOfHeights = function(maxHeights) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Beautiful Towers II — Solution in Python, Java & C++

Beautiful Towers II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and stack.

Beautiful Towers II is a medium coding problem on arrays, stack and monotonic stack, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Stack, Monotonic Stack
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You will build n towers in a row; tower i must get a height heights[i] with 1 <= heights[i] <= maxHeights[i].

The arrangement is beautiful when the heights form a mountain: there is a peak index p such that heights never decrease from index 0 up to p, and never increase from p to index n - 1 (either side may be empty).

Return the largest possible sum of heights of a beautiful arrangement.

(The height bound below is tighter than the original problem's so that the answer fits in a 32-bit integer.)

Example 1

Input: maxHeights = [4,6,2,7,3]
Output: 16
Explanation: Peak at index 1: `[4,6,2,2,2]`; a peak at index 3 (`[2,2,2,7,3]`) also gives 16.

Example 2

Input: maxHeights = [3,3,3]
Output: 9

Example 3

Input: maxHeights = [1,5,1]
Output: 7

Constraints

  • 1 <= maxHeights.length <= 10^5
  • 1 <= maxHeights[i] <= 2 * 10^4

Hints for Beautiful Towers II

  1. Hint 1

    Once the peak p is fixed, the best choice is greedy: heights[p] = maxHeights[p], and walking away from the peak each tower takes the running minimum of the limits.

  2. Hint 2

    So the left part contributes Σ min(maxHeights[j..p]) for j <= p. Can you compute that for every p at once?

  3. Hint 3

    With q the previous index whose limit is smaller than maxHeights[p], left[p] = left[q] + maxHeights[p] × (p - q) — a monotonic stack finds q. Do the same from the right and maximise left[p] + right[p] - maxHeights[p].

How to solve Beautiful Towers II

For a fixed peak the optimal mountain takes running minimums outward. The left and right totals for every possible peak satisfy a simple recurrence over the previous smaller element, so two monotonic-stack sweeps price all peaks in linear time.

Approach

  1. Left sweep: keep a stack of indices with strictly increasing limits. For i, pop while the top limit is >= maxHeights[i]; with q the remaining top (or -1), set left[i] = (q >= 0 ? left[q] : 0) + maxHeights[i] × (i - q).
  2. Right sweep: the mirror image, giving right[i] = best total of the non-increasing part starting at i.
  3. The best mountain with peak i sums to left[i] + right[i] - maxHeights[i] (the peak is counted twice).
  4. Return the maximum over all i, using 64-bit sums along the way.

Why it works

With peak p, tower j < p can be no taller than any limit between j and p, and taking exactly that minimum is feasible and best, so the left total is Σ_{j<=p} min(maxHeights[j..p]). For indices j in (q, p] that minimum is maxHeights[p] itself, and for j <= q it equals the minimum over [j, q], because maxHeights[q] is smaller than everything in (q, p] — which is exactly left[q].

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Trying every peak with an O(n) walk is O(n²).
  • Subtract the peak once: both sweeps include it.
  • Intermediate totals can exceed 32 bits in the original constraints; keep 64-bit sums.

Reference solution

Python

from typing import List

def maximumSumOfHeights(maxHeights: List[int]) -> int:
    a = maxHeights
    n = len(a)
    left = [0] * n
    st = []
    for i in range(n):
        while st and a[st[-1]] >= a[i]:
            st.pop()
        q = st[-1] if st else -1
        left[i] = (left[q] if q >= 0 else 0) + a[i] * (i - q)
        st.append(i)
    right = [0] * n
    st = []
    for i in range(n - 1, -1, -1):
        while st and a[st[-1]] >= a[i]:
            st.pop()
        q = st[-1] if st else n
        right[i] = (right[q] if q < n else 0) + a[i] * (q - i)
        st.append(i)
    return max(left[i] + right[i] - a[i] for i in range(n))

Java

public static int maximumSumOfHeights(int[] maxHeights) {
    int[] a = maxHeights;
    int n = a.length;
    long[] left = new long[n], right = new long[n];
    int[] st = new int[n];
    int top = 0;
    for (int i = 0; i < n; i++) {
        while (top > 0 && a[st[top - 1]] >= a[i]) top--;
        int q = top > 0 ? st[top - 1] : -1;
        left[i] = (q >= 0 ? left[q] : 0) + (long) a[i] * (i - q);
        st[top++] = i;
    }
    top = 0;
    for (int i = n - 1; i >= 0; i--) {
        while (top > 0 && a[st[top - 1]] >= a[i]) top--;
        int q = top > 0 ? st[top - 1] : n;
        right[i] = (q < n ? right[q] : 0) + (long) a[i] * (q - i);
        st[top++] = i;
    }
    long best = 0;
    for (int i = 0; i < n; i++) best = Math.max(best, left[i] + right[i] - a[i]);
    return (int) best;
}

C++

int maximumSumOfHeights(vector<int>& maxHeights) {
    vector<int>& a = maxHeights;
    int n = a.size();
    vector<long long> left(n, 0), right(n, 0);
    vector<int> st;
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        int q = st.empty() ? -1 : st.back();
        left[i] = (q >= 0 ? left[q] : 0) + (long long)a[i] * (i - q);
        st.push_back(i);
    }
    st.clear();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.back()] >= a[i]) st.pop_back();
        int q = st.empty() ? n : st.back();
        right[i] = (q < n ? right[q] : 0) + (long long)a[i] * (q - i);
        st.push_back(i);
    }
    long long best = 0;
    for (int i = 0; i < n; i++) best = max(best, left[i] + right[i] - a[i]);
    return (int)best;
}

JavaScript

var maximumSumOfHeights = function(maxHeights) {
    var a = maxHeights, n = a.length;
    var left = new Array(n).fill(0), right = new Array(n).fill(0);
    var st = [];
    for (var i = 0; i < n; i++) {
        while (st.length > 0 && a[st[st.length - 1]] >= a[i]) st.pop();
        var q = st.length > 0 ? st[st.length - 1] : -1;
        left[i] = (q >= 0 ? left[q] : 0) + a[i] * (i - q);
        st.push(i);
    }
    st = [];
    for (var j = n - 1; j >= 0; j--) {
        while (st.length > 0 && a[st[st.length - 1]] >= a[j]) st.pop();
        var r = st.length > 0 ? st[st.length - 1] : n;
        right[j] = (r < n ? right[r] : 0) + a[j] * (r - j);
        st.push(j);
    }
    var best = 0;
    for (var k = 0; k < n; k++) best = Math.max(best, left[k] + right[k] - a[k]);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure