2866. Beautiful Towers II

MediumStackArrayMonotonic Stack
Leetcode Link

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:

  1. The height of each tower is at least 1 and at most as high as specified by its corresponding value in maxHeights.
  2. 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 to i and then decrease or stay the same after i.

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:

  1. 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.
  2. 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which of the following is equvalent to O(3*2^n + n^3 + n!+ log n)?

Solution Approach

The implementation provided uses stacks and dynamic programming to arrive at the solution by following these steps:

  1. Initialization: Create two empty stacks (stk), and two arrays left and right to store the index of the nearest higher tower to the left and right of each tower, respectively. Additionally, create arrays f and g to store the maximum sum of the tower heights from both the left and right perspectives.

  2. 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 to left[i].
    • Push the current index i onto stk.

  3. 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 to right[i].
    • Push the current index i onto stk.

  4. Dynamic Programming - Forward Pass (Calculating f):

    • Iterate over maxHeights, updating the f array.
    • For each tower, if its height is at least as much as the previous tower (indicating ascending order), update f[i] to be f[i - 1] + x (x being the height of the current tower).
    • If not, find j, the nearest higher tower to the left (from left[i]), and set f[i] to be the sum of x times the distance to j and f[j] if j is not -1.

  5. Dynamic Programming - Backward Pass (Calculating g):

    • Iterate in reverse over maxHeights, updating the g array in a similar fashion to f.
    • If the tower is at least as tall as the next one, update g[i] to be the g[i + 1] + x.
    • Otherwise, find j, the nearest higher tower to the right (from right[i]), and set g[i] to be the sum of x times the distance to j and g[j] if j is not n.

  6. Compute the Maximum Sum:

    • Use a list comprehension to calculate the sum of corresponding values in f and g 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.

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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example 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].

  1. Initialization:

    • Create empty stacks stk, and arrays left and right with the same size as maxHeights, initially filled with -1 values to denote that there's no nearest higher tower yet.
    • Arrays f and g are also created and initialized with zeros.

  2. 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) until stk 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) onto stk.
    • At the end of this step, stk contains [3, 4], left array is [-1, -1, 0, 2, -1].

  3. 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 update right[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].

  4. Dynamic Programming - Forward Pass (Calculating f):

    • Iterating over maxHeights:
      • For index (0), f[0] is just its height, so f[0] will be 3.
      • For index (1), it’s less than its predecessor, so its f[1] is just its own height 1.
      • Index (2) is taller than its left neighbor, so f[2] becomes f[1] + 4 = 5.
      • Continue this until you reach the end of the maxHeights. f array builds up as [3, 1, 5, 12, 9].

  5. Dynamic Programming - Backward Pass (Calculating g):

    • Iterate in reverse over maxHeights:
      • For index (4), g[4] is its height, so g[4] will be 5.
      • For index (3), g[3] becomes g[4] + 7 = 12.
      • Continue updating g in this manner. The g array builds up as [16, 18, 16, 12, 5].

  6. Compute the Maximum Sum:

    • Calculate the sum of corresponding values in f and g 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].

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
Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Time and Space Complexity

Time Complexity

The given code comprises several loops iterating separately over the list maxHeights.

  1. The first for loop is a single pass over maxHeights with an inner while loop that may pop elements from stk. Each element is pushed onto stk once and popped at most once. This suggests that the overall time for this loop is O(n).

  2. 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 has O(n) time complexity.

  3. The third loop calculates values for the list f. Each iteration does constant work unless the if 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 of f[j] which is constant time. Hence, this loop also runs in O(n).

  4. The fourth loop computes the g array similarly to the f array, with the same reasoning for its time complexity. So, this loop is also O(n).

  5. The last statement computes the maximum value of a + b - c for each corresponding elements of the arrays f, g, and maxHeights with the help of the zip() function. Iterating over n elements in parallel complexity is O(n).

Combining all these, we can conclude that the total time complexity is O(n).

Space Complexity

Analyzing space complexity:

  1. Three extra arrays left, right, f, and g each of length n are used, contributing 4n to the space complexity.

  2. The stk list can possibly store up to n indexes (in the worst case where the array maxHeights is sorted in ascending order). Hence, the space used by stk could be O(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.

Fast Track Your Learning with Our Quick Skills Quiz:

Which type of traversal does breadth first search do?

Recommended Readings

Stack Intro

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/Queue Intro

Monotonic Stack Deque Intro If you'd prefer a video iframe width 560 height 315 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 The word monotonic means a list or a

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫