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^51 <= maxHeights[i] <= 2 * 10^4
Hints for Beautiful Towers II
Hint 1
Once the peak
pis 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.Hint 2
So the left part contributes
Σ min(maxHeights[j..p])forj <= p. Can you compute that for everypat once?Hint 3
With
qthe previous index whose limit is smaller thanmaxHeights[p],left[p] = left[q] + maxHeights[p] × (p - q)— a monotonic stack findsq. Do the same from the right and maximiseleft[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
- Left sweep: keep a stack of indices with strictly increasing limits. For
i, pop while the top limit is>= maxHeights[i]; withqthe remaining top (or -1), setleft[i] = (q >= 0 ? left[q] : 0) + maxHeights[i] × (i - q). - Right sweep: the mirror image, giving
right[i]= best total of the non-increasing part starting ati. - The best mountain with peak
isums toleft[i] + right[i] - maxHeights[i](the peak is counted twice). - 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