2866. Beautiful Towers II
Problem Description
You are given an array of integers called maxHeights
which is 0-indexed and denotes the maximum possible heights of n
towers that you can build on a coordinate line, where each tower's position corresponds to its index in the array maxHeights
. The goal is to determine a configuration of tower heights (an array heights
with heights[i]
being the height of the tower at coordinate i
) that is considered beautiful. A configuration is defined as beautiful if:
- The height of each tower is at least 1 and at most as high as specified by its corresponding value in
maxHeights
. - The array of tower heights forms a mountain array, which means there must be some peak index
i
at which the heights of the towers increase up toi
and then decrease or stay the same afteri
.
The task is to compute the maximum possible sum of heights of the towers in such a beautiful configuration.
Intuition
To solve this problem, the primary task is to find an optimal "peak" for the mountain array, because once the peak is determined, the towers to the left of the peak should increase in height up to the peak, and those to the right should decrease or stay constant. The heights should also respect the maximum heights in maxHeights
.
One way to think about this problem is to perform a two-pass scan over the maxHeights
array, considering both the left and right side contributions for each potential peak:
- For each tower, find the nearest tower to its left which has a height greater than or equal to its own (this could become the peak for all towers to its right). Store this information for later use.
- Similarly, for each tower, find the nearest tower to its right which has a height greater than its own (this could become the peak for all towers to its left).
With these two pieces of information (formatted as left
and right
arrays in the code), one can compute what the optimal left side contribution and the right side contribution for every tower if it were chosen to be the peak.
The solution iteratively computes the best possible sum of heights for each tower considering it as the peak of the mountain.
The provided solution does this in four major steps:
- It uses a stack to find the left limits for tower heights.
- It then uses a stack to find the right limits.
- It calculates the optimal height array assuming each tower is the peak from left to right, storing the result in an array
f
. - It calculates the optimal height array assuming each tower is the peak from right to left, storing the result in an array
g
.
Finally, the maximum sum of heights is found by taking the maximum value obtained by summing corresponding elements from f
and g
and deducting the height of the tower being considered as the peak to avoid double-counting.
Learn more about Stack and Monotonic Stack patterns.
Solution Approach
The implementation provided uses stacks and dynamic programming to arrive at the solution by following these steps:
-
Initialization: Create two empty stacks (
stk
), and two arraysleft
andright
to store the index of the nearest higher tower to the left and right of each tower, respectively. Additionally, create arraysf
andg
to store the maximum sum of the tower heights from both the left and right perspectives. -
Finding Left Limits:
- Iterate over
maxHeights
array. - For each tower, pop elements from
stk
while the top element of the stack (the last tower added) has a height greater than the current tower's height. - If the stack is not empty, assign the index of the top element of
stk
toleft[i]
. - Push the current index
i
ontostk
.
- Iterate over
-
Finding Right Limits:
- Similar to the left limits, iterate over
maxHeights
array in reverse. - For each tower, pop elements from
stk
while the top element has a height greater than or equal to the current tower's height. - If the stack is not empty, assign the index of the top element of
stk
toright[i]
. - Push the current index
i
ontostk
.
- Similar to the left limits, iterate over
-
Dynamic Programming - Forward Pass (Calculating
f
):- Iterate over
maxHeights
, updating thef
array. - For each tower, if its height is at least as much as the previous tower (indicating ascending order), update
f[i]
to bef[i - 1] + x
(x
being the height of the current tower). - If not, find
j
, the nearest higher tower to the left (fromleft[i]
), and setf[i]
to be the sum ofx
times the distance toj
andf[j]
ifj
is not-1
.
- Iterate over
-
Dynamic Programming - Backward Pass (Calculating
g
):- Iterate in reverse over
maxHeights
, updating theg
array in a similar fashion tof
. - If the tower is at least as tall as the next one, update
g[i]
to be theg[i + 1] + x
. - Otherwise, find
j
, the nearest higher tower to the right (fromright[i]
), and setg[i]
to be the sum ofx
times the distance toj
andg[j]
ifj
is notn
.
- Iterate in reverse over
-
Compute the Maximum Sum:
- Use a list comprehension to calculate the sum of corresponding values in
f
andg
while subtracting the height of the current tower to prevent double-counting. - The maximum of these sums gives the maximum sum of heights for a beautiful configuration.
- Use a list comprehension to calculate the sum of corresponding values in
The algorithm cleverly combines the Lookup Pattern (to find potential peak heights to the left and right of each tower), and Dynamic Programming (to calculate the optimal heights with summing partial solutions) to construct the solution in an efficient way.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a small example to illustrate the solution approach. Assume we are given the array maxHeights
as [3, 1, 4, 7, 5]
.
-
Initialization:
- Create empty stacks
stk
, and arraysleft
andright
with the same size asmaxHeights
, initially filled with-1
values to denote that there's no nearest higher tower yet. - Arrays
f
andg
are also created and initialized with zeros.
- Create empty stacks
-
Finding Left Limits:
- Start iterating over
maxHeights
:- For the first element (3), the stack is empty, so push its index (0) onto
stk
. - Move to the second element (1), a smaller height, nothing will be popped. Push its index (1) onto
stk
. - The third element (4) is taller than the top of
stk
, so pop elements (indices 1 and 0) untilstk
is empty or the top is taller, and then push index (2).left[2]
now is 0, the index of the last taller height. - The fourth element (7) follows the same logic. Pop elements until the top is taller (index 2 gets popped), then push index (3).
left[3]
would be 2. - Finally, the fifth element (5) is smaller than the top of
stk
, so push its index (4) ontostk
.
- For the first element (3), the stack is empty, so push its index (0) onto
- At the end of this step,
stk
contains [3, 4],left
array is[-1, -1, 0, 2, -1]
.
- Start iterating over
-
Finding Right Limits:
- Iterate over
maxHeights
in reverse:- Start with the last element (5), the stack is empty again, so push index (4).
- For the fourth element (7), nothing will be popped from the stack. Push index (3).
- The third element (4) is smaller, so pop the top of
stk
, which is 3, and now the top is (4), which is taller. Push index (2) and updateright[2]
with 4. - The second element (1) is smaller, pop both 2 and 4 from
stk
since they're taller,right[2]
remains as the index 4. - For the first element (3), pop index (1) and push index (0), as the index (4) is taller. Update
right[0]
with 4.
- At the end of this step,
stk
contains [3, 0],right
array is[4, -1, 4, -1, -1]
.
- Iterate over
-
Dynamic Programming - Forward Pass (Calculating
f
):- Iterating over
maxHeights
:- For index (0),
f[0]
is just its height, sof[0]
will be 3. - For index (1), it’s less than its predecessor, so its
f[1]
is just its own height1
. - Index (2) is taller than its left neighbor, so
f[2]
becomesf[1] + 4 = 5
. - Continue this until you reach the end of the
maxHeights
.f
array builds up as[3, 1, 5, 12, 9]
.
- For index (0),
- Iterating over
-
Dynamic Programming - Backward Pass (Calculating
g
):- Iterate in reverse over
maxHeights
:- For index (4),
g[4]
is its height, sog[4]
will be 5. - For index (3),
g[3]
becomesg[4] + 7 = 12
. - Continue updating
g
in this manner. Theg
array builds up as[16, 18, 16, 12, 5]
.
- For index (4),
- Iterate in reverse over
-
Compute the Maximum Sum:
- Calculate the sum of corresponding values in
f
andg
while subtracting the height of the current tower (to avoid double-counting):sums = [f[i] + g[i] - maxHeights[i] for i in range(len(maxHeights))]
. - For our example,
sums
becomes[16, 18, 17, 17, 9]
. - The maximum value in
sums
is 18, which would be our result, the maximum sum of heights for a beautiful configuration given the input array[3, 1, 4, 7, 5]
.
- Calculate the sum of corresponding values in
Solution Implementation
1from typing import List
2
3class Solution:
4 def maximumSumOfHeights(self, max_heights: List[int]) -> int:
5 n = len(max_heights)
6 stack = []
7 left_indices = [-1] * n # Initialize list to store left boundaries
8
9 # Find the index of the previous smaller element for each element
10 for i, height in enumerate(max_heights):
11 while stack and max_heights[stack[-1]] > height:
12 stack.pop()
13 if stack:
14 left_indices[i] = stack[-1]
15 stack.append(i)
16
17 stack.clear() # Clear the stack for the next loop
18 right_indices = [n] * n # Initialize list to store right boundaries
19
20 # Find the index of the next smaller element for each element
21 for i in range(n - 1, -1, -1):
22 while stack and max_heights[stack[-1]] >= max_heights[i]:
23 stack.pop()
24 if stack:
25 right_indices[i] = stack[-1]
26 stack.append(i)
27
28 forward_sums = [0] * n # Initialize list to store forward sums
29
30 # Calculate forward sums of heights following increasing order
31 for i, height in enumerate(max_heights):
32 if i and height >= max_heights[i - 1]:
33 forward_sums[i] = forward_sums[i - 1] + height
34 else:
35 left_index = left_indices[i]
36 forward_sums[i] = height * (i - left_index) + (forward_sums[left_index] if left_index != -1 else 0)
37
38 backward_sums = [0] * n # Initialize list to store backward sums
39
40 # Calculate backward sums of heights following increasing order
41 for i in range(n - 1, -1, -1):
42 if i < n - 1 and max_heights[i] >= max_heights[i + 1]:
43 backward_sums[i] = backward_sums[i + 1] + max_heights[i]
44 else:
45 right_index = right_indices[i]
46 backward_sums[i] = max_heights[i] * (right_index - i) + (backward_sums[right_index] if right_index != n else 0)
47
48 # Find the max sum by combining forward and backward sums for each height
49 max_sum = max(
50 forward_sum + backward_sum - height
51 for forward_sum, backward_sum, height in zip(forward_sums, backward_sums, max_heights))
52
53 return max_sum
54
1import java.util.Deque;
2import java.util.ArrayDeque;
3import java.util.List;
4import java.util.Arrays;
5
6class Solution {
7
8 public long maximumSumOfHeights(List<Integer> maxHeights) {
9 int n = maxHeights.size(); // size of the maxHeights list
10 Deque<Integer> stack = new ArrayDeque<>(); // stack to keep track of indices
11 int[] left = new int[n]; // stores indices of the previous smaller element
12 int[] right = new int[n]; // stores indices of the next smaller element
13 Arrays.fill(left, -1); // initialize the left array with -1
14 Arrays.fill(right, n); // initialize the right array with n (size of maxHeights)
15
16 // Calculate previous smaller elements
17 for (int i = 0; i < n; ++i) {
18 int currentHeight = maxHeights.get(i);
19 while (!stack.isEmpty() && maxHeights.get(stack.peek()) > currentHeight) {
20 stack.pop();
21 }
22 if (!stack.isEmpty()) {
23 left[i] = stack.peek();
24 }
25 stack.push(i);
26 }
27 stack.clear(); // clear stack for reuse
28
29 // Calculate next smaller elements
30 for (int i = n - 1; i >= 0; --i) {
31 int currentHeight = maxHeights.get(i);
32 while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= currentHeight) {
33 stack.pop();
34 }
35 if (!stack.isEmpty()) {
36 right[i] = stack.peek();
37 }
38 stack.push(i);
39 }
40 long[] prefixSum = new long[n]; // cumulative sum from the left
41 long[] suffixSum = new long[n]; // cumulative sum from the right
42
43 // Calculate prefix sums
44 for (int i = 0; i < n; ++i) {
45 int currentHeight = maxHeights.get(i);
46 if (i > 0 && currentHeight >= maxHeights.get(i - 1)) {
47 prefixSum[i] = prefixSum[i - 1] + currentHeight;
48 } else {
49 int j = left[i];
50 prefixSum[i] = 1L * currentHeight * (i - j) + (j >= 0 ? prefixSum[j] : 0);
51 }
52 }
53 // Calculate suffix sums
54 for (int i = n - 1; i >= 0; --i) {
55 int currentHeight = maxHeights.get(i);
56 if (i < n - 1 && currentHeight >= maxHeights.get(i + 1)) {
57 suffixSum[i] = suffixSum[i + 1] + currentHeight;
58 } else {
59 int j = right[i];
60 suffixSum[i] = 1L * currentHeight * (j - i) + (j < n ? suffixSum[j] : 0);
61 }
62 }
63
64 long maxSum = 0; // variable to store the maximum sum
65 // Compute the maximum sum by combining prefix and suffix sums
66 for (int i = 0; i < n; ++i) {
67 maxSum = Math.max(maxSum, prefixSum[i] + suffixSum[i] - maxHeights.get(i));
68 }
69
70 return maxSum; // return the maximum sum
71 }
72}
73
1class Solution {
2public:
3 long long maximumSumOfHeights(vector<int>& max_heights) {
4 // Get the number of elements in the vector
5 int n = max_heights.size();
6
7 // Stack to keep track of indices while finding next smaller element
8 stack<int> stk;
9
10 // Vectors to store the nearest smaller element on the left and right for each element
11 vector<int> nearest_smaller_left(n, -1);
12 vector<int> nearest_smaller_right(n, n);
13
14 // Find the nearest smaller element on the left for each element
15 for (int i = 0; i < n; ++i) {
16 int height = max_heights[i];
17 while (!stk.empty() && max_heights[stk.top()] > height) {
18 stk.pop();
19 }
20 if (!stk.empty()) {
21 nearest_smaller_left[i] = stk.top();
22 }
23 stk.push(i);
24 }
25
26 // Clear the stack for the next iteration
27 stk = stack<int>();
28
29 // Find the nearest smaller element on the right for each element
30 for (int i = n - 1; i >= 0; --i) {
31 int height = max_heights[i];
32 while (!stk.empty() && max_heights[stk.top()] >= height) {
33 stk.pop();
34 }
35 if (!stk.empty()) {
36 nearest_smaller_right[i] = stk.top();
37 }
38 stk.push(i);
39 }
40
41 // Vectors to store the sum of heights traversing left and right
42 vector<long long> sum_left(n, 0);
43 vector<long long> sum_right(n, 0);
44
45 // Calculate the sum of heights going left from each element
46 for (int i = 0; i < n; ++i) {
47 int height = max_heights[i];
48 if (i > 0 && height >= max_heights[i - 1]) {
49 sum_left[i] = sum_left[i - 1] + height;
50 } else {
51 int j = nearest_smaller_left[i];
52 sum_left[i] = static_cast<long long>(height) * (i - j) + (j != -1 ? sum_left[j] : 0);
53 }
54 }
55
56 // Calculate the sum of heights going right from each element
57 for (int i = n - 1; i >= 0; --i) {
58 int height = max_heights[i];
59 if (i < n - 1 && height >= max_heights[i + 1]) {
60 sum_right[i] = sum_right[i + 1] + height;
61 } else {
62 int j = nearest_smaller_right[i];
63 sum_right[i] = static_cast<long long>(height) * (j - i) + (j != n ? sum_right[j] : 0);
64 }
65 }
66
67 // Variable to keep track of the maximum sum of heights
68 long long max_sum = 0;
69
70 // Calculate the maximum sum of heights for each element
71 for (int i = 0; i < n; ++i) {
72 max_sum = max(max_sum, sum_left[i] + sum_right[i] - max_heights[i]);
73 }
74
75 // Return the maximum sum of heights
76 return max_sum;
77 }
78};
79
1function maximumSumOfHeights(maxHeights: number[]): number {
2 const n: number = maxHeights.length;
3 const stack: number[] = [];
4 const left: number[] = new Array(n).fill(-1);
5 const right: number[] = new Array(n).fill(n);
6
7 // Calculate the left boundary for each element
8 for (let i = 0; i < n; ++i) {
9 while (stack.length && maxHeights[stack[stack.length - 1]] > maxHeights[i]) {
10 stack.pop();
11 }
12 if (stack.length) {
13 left[i] = stack[stack.length - 1];
14 }
15 stack.push(i);
16 }
17
18 // Reset stack for right boundary calculation
19 stack.length = 0;
20
21 // Calculate the right boundary for each element
22 for (let i = n - 1; i >= 0; --i) {
23 while (stack.length && maxHeights[stack[stack.length - 1]] >= maxHeights[i]) {
24 stack.pop();
25 }
26 if (stack.length) {
27 right[i] = stack[stack.length - 1];
28 }
29 stack.push(i);
30 }
31
32 // Precompute the sum of heights to the left of each element
33 const prefixSumLeft: number[] = new Array(n).fill(0);
34 // Precompute the sum of heights to the right of each element
35 const prefixSumRight: number[] = new Array(n).fill(0);
36
37 for (let i = 0; i < n; ++i) {
38 if (i && maxHeights[i] >= maxHeights[i - 1]) {
39 prefixSumLeft[i] = prefixSumLeft[i - 1] + maxHeights[i];
40 } else {
41 const boundaryLeft = left[i];
42 prefixSumLeft[i] = maxHeights[i] * (i - boundaryLeft) + (boundaryLeft >= 0 ? prefixSumLeft[boundaryLeft] : 0);
43 }
44 }
45
46 // Similarly, process heights from right to left
47 for (let i = n - 1; i >= 0; --i) {
48 if (i + 1 < n && maxHeights[i] >= maxHeights[i + 1]) {
49 prefixSumRight[i] = prefixSumRight[i + 1] + maxHeights[i];
50 } else {
51 const boundaryRight = right[i];
52 prefixSumRight[i] = maxHeights[i] * (boundaryRight - i) + (boundaryRight < n ? prefixSumRight[boundaryRight] : 0);
53 }
54 }
55
56 // Find the maximum sum of heights by combining left and right sums
57 let maxSum = 0;
58 for (let i = 0; i < n; ++i) {
59 maxSum = Math.max(maxSum, prefixSumLeft[i] + prefixSumRight[i] - maxHeights[i]);
60 }
61
62 return maxSum;
63}
64
Time and Space Complexity
Time Complexity
The given code comprises several loops iterating separately over the list maxHeights
.
-
The first
for
loop is a single pass overmaxHeights
with an inner while loop that may pop elements fromstk
. Each element is pushed ontostk
once and popped at most once. This suggests that the overall time for this loop isO(n)
. -
The second pass is similar to the first, but it moves in the opposite direction (reverse). It also follows a similar logic with pushing and popping from
stk
, and thus also hasO(n)
time complexity. -
The third loop calculates values for the list
f
. Each iteration does constant work unless theif
condition is met. If the height is not greater than or equal to the previous one, the calculation involves a difference and a potential lookup off[j]
which is constant time. Hence, this loop also runs inO(n)
. -
The fourth loop computes the
g
array similarly to thef
array, with the same reasoning for its time complexity. So, this loop is alsoO(n)
. -
The last statement computes the maximum value of
a + b - c
for each corresponding elements of the arraysf
,g
, andmaxHeights
with the help of thezip()
function. Iterating overn
elements in parallel complexity isO(n)
.
Combining all these, we can conclude that the total time complexity is O(n)
.
Space Complexity
Analyzing space complexity:
-
Three extra arrays
left
,right
,f
, andg
each of lengthn
are used, contributing4n
to the space complexity. -
The
stk
list can possibly store up ton
indexes (in the worst case where the arraymaxHeights
is sorted in ascending order). Hence, the space used bystk
could beO(n)
.
Add all of these together, and the space complexity totals to O(n)
since the constants are dropped in Big O notation.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Stack Intro Imagine you have a pile of books on your desk If you want to add a new book you place it on top If you want to read a book you take it from the top And if you simply want to see which book is on the top you
Monotonic Stack Deque Intro If you'd prefer a video div class responsive iframe iframe src https www youtube com embed Dq_ObZwTY_Q title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe div The word monotonic means a list or
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.