2865. Beautiful Towers I

Problem Description

You are given an array maxHeights which consists of n integers. Imagine the responsibility of constructing n towers along a straight line where the i-th tower is positioned at coordinate i and may vary in height, up to a maximum height specified by maxHeights[i]. The goal is to build these towers in such a way that they form a beautiful configuration. A beautiful configuration is defined by two criteria:

The height of each tower (heights[i]) must be at least 1 and at most maxHeights[i].
The height sequence of the towers (heights) must form a mountain array, meaning there exists an index i in heights such that:
- For any index j less than i, heights[j] is less than or equal to heights[j+1] (ascending order).
- For any index k greater than i, heights[k] is greater than or equal to heights[k+1] (descending order).

The challenge is to find the configuration of towers that is beautiful and yields the maximal possible sum of heights across all towers.

Intuition

The approach to solve this problem involves iterating through each possible peak of the mountain (the highest point where the towers will transition from ascending to descending heights). For each potential peak position i, we determine the maximum sum of heights for a mountain configuration where the peak is at i. To achieve this, we initialize the peak tower's height with 'x' - the value given by maxHeights[i]. We then expand this peak to the left and right to construct the ascending and descending parts of the mountain.

While expanding to the left, we ensure that the heights of the towers are both less than or equal to maxHeights[j] and the height of the previous tower to maintain a non-decreasing slope. Similarly, when expanding to the right, we maintain heights that are less than or equal to maxHeights[j] and the previous tower to ensure a non-increasing slope. The total sum for this configuration is computed by accumulating the heights as we expand from the peak to both the left and right ends.

After exploring all potential peak positions, we keep track of the maximum sum of heights that we have encountered. This value represents the highest sum of tower heights for any beautiful configuration possible, and thus, is the answer we return.

Learn more about Stack and Monotonic Stack patterns.

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

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Solution Approach

The provided solution uses a straightforward brute force approach to simulate the construction of the mountain from each potential peak position. The approach does not use complex data structures or advanced algorithms; it relies on basic iteration and condition checking. Here's a step-by-step breakdown of how the solution is implemented:

The function maximumSumOfHeights begins with initializing variable ans to store the maximum sum found for any beautiful configuration, and variable n to store the number of towers (the length of the maxHeights array).
It then enters a loop to consider each element x in maxHeights as the peak of the mountain (tallest tower). The variable i refers to the index where the peak is located.
Inside the loop, two additional loops are used:
- The first inner loop decreases from the peak's index i-1 to the start of the array. We initialize y as the height of the peak tower and t as the total sum starting with the peak. For every element left of the peak (j index), we update y to the minimum of the current y and maxHeights[j] to ensure that the tower heights are non-decreasing as we move towards the peak. We then add the height y to the total sum t.
- The second inner loop increases from the peak's index i+1 to the end of the array, similarly initializing y to the height of the peak. As we iterate to the right, we update y with the minimum of the current y and maxHeights[j] to ensure the mountain array condition is maintained with non-increasing tower heights. Each y value is added to the total sum t.
After both loops, we have constructed the tallest possible mountain whose peak is at index i and we compare its total sum t with the current maximum ans, updating ans if t is greater.
Finally, after all iterations, ans contains the maximum sum that can be achieved by a beautiful configuration of towers and is returned.

Throughout the implementation, variables ans, y, and t are used to keep track of the current best answer, the height of the previous tower (to maintain a valid mountain shape), and the cumulative sum of the current configuration, respectively.

No extra data structures are used; the solution operates directly on the input array, and no sorting or other modifications are needed. The simplicity of the problem allows for a direct brute force method, exploring every possibility and comparing sums directly to find the optimal configuration.

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

Example Walkthrough

Let's walk through a small example to illustrate the solution approach using the following maxHeights array:

1maxHeights = [2, 1, 4, 3]

In this scenario, we have four positions to place towers, and we can set their heights with the constraints provided in the maxHeights array. We need to build the towers such that they form a mountain array. Let's examine the construction step-by-step by trying each position for the peak.

Trying the first position as the peak (i = 0). The peak height x = 2.
- To the left of the peak, there are no taller towers, so we can't extend in that direction.
- To the right, we need to construct descending towers. However, given the height 1 at the next position, we cannot make a descending sequence from 2.
- The sequence fails to form a mountain, and the sum here would simply be 2.
Trying the second position as the peak (i = 1). The peak height x = 1.
- Since the peak is the smallest possible tower, we cannot create a proper mountain.
- The sum for this peak would be 1.
Trying the third position as the peak (i = 2). The peak height x = 4.
- Ascending from the left, we can have the first tower at height 2, next cannot exceed 1, so it stays 1.
- Descending from the peak to the right, the next and final tower can be up to 3.
- The mountain array [2, 1, 4, 3] forms a valid, beautiful configuration with a sum of 2 + 1 + 4 + 3 = 10.
Trying the fourth position as the peak (i = 3). The peak height x = 3.
- Ascending from the left, we start with 2, can increase to 1, but then we cannot go higher because the peak is at 3.
- No towers to the right since this is the end of the array.
- The sequence [2, 1, 3] is not a valid mountain as it lacks a descending part, making this an invalid peak position.

Out of all the trials, the third position peak yields the highest sum of tower heights, which is 10. Therefore, the solution would return 10 as the maximum sum for creating a beautiful tower configuration.

The simple brute force approach worked effectively for this example by checking each possible peak and ensuring that all criteria of a mountain array are met. By calculating the sums for each valid configuration and keeping track of the maximum, we identified the optimal construction.

Solution Implementation

1class Solution:
2    def maximumSumOfHeights(self, maxHeights: List[int]) -> int:
3        # Initialize the variable to hold the maximum sum of heights
4        max_sum = 0
5      
6        # Calculate the length of the maxHeights list once as it is used multiple times
7        num_heights = len(maxHeights)
8      
9        # Iterate through each height in the maxHeights list
10        for i, current_height in enumerate(maxHeights):
11            # Initialize temporary variables for moving left and right from the current index
12            left_min_height = current_height
13            right_min_height = current_height
14          
15            # Temporary sum for current position including the current height itself
16            temp_sum = current_height
17          
18            # Move to the left of the current position and add the minimum of all
19            # encountered heights so far to the temporary sum
20            for left_index in range(i - 1, -1, -1):
21                left_min_height = min(left_min_height, maxHeights[left_index])
22                temp_sum += left_min_height
23          
24            # Move to the right of the current position and add the minimum of all
25            # encountered heights so far to the temporary sum
26            for right_index in range(i + 1, num_heights):
27                right_min_height = min(right_min_height, maxHeights[right_index])
28                temp_sum += right_min_height
29          
30            # Update the maximum sum if the temporary sum is greater than the current maximum
31            max_sum = max(max_sum, temp_sum)
32      
33        # Return the maximum sum after considering all positions
34        return max_sum
35

1class Solution {
2    // Method to calculate the maximum sum of heights, considering that each position
3    // can act as a pivot, and the sum includes the minimum height from the pivot to each side.
4    public long maximumSumOfHeights(List<Integer> maxHeightList) {
5        long maxSum = 0; // This will store the maximum sum of heights we find
6        int listSize = maxHeightList.size(); // The size of the provided list
7      
8        // Iterate through each element in the list to consider it as a potential pivot
9        for (int i = 0; i < listSize; ++i) {
10            int currentHeight = maxHeightList.get(i); // Height at the current pivot
11            long tempSum = currentHeight; // Initialize temp sum with current pivot's height
12          
13            // Calculate the sum of heights to the left of the pivot
14            for (int j = i - 1; j >= 0; --j) {
15                currentHeight = Math.min(currentHeight, maxHeightList.get(j)); // Update to the smaller height
16                tempSum += currentHeight; // Add this height to the running total for the pivot
17            }
18
19            currentHeight = maxHeightList.get(i); // Reset height for current pivot
20
21            // Calculate the sum of heights to the right of the pivot
22            for (int j = i + 1; j < listSize; ++j) {
23                currentHeight = Math.min(currentHeight, maxHeightList.get(j)); // Update to the smaller height
24                tempSum += currentHeight; // Add this height to the running total for the pivot
25            }
26
27            // Update maxSum if the sum for the current pivot is greater than the previous maximum
28            maxSum = Math.max(maxSum, tempSum);
29        }
30
31        // Return the maximum sum of heights found
32        return maxSum;
33    }
34}
35

1class Solution {
2public:
3    // Function to calculate the maximum sum of heights.
4    long long maximumSumOfHeights(vector<int>& maxHeightSequence) {
5        long long maxSum = 0; // Initialize variable to hold the maximum sum
6        int sequenceLength = maxHeightSequence.size(); // Get the length of the sequence
7
8        // Loop through the entire sequence to find the maximum sum of heights
9        for (int i = 0; i < sequenceLength; ++i) {
10            long long tempSum = maxHeightSequence[i]; // Start with the current height
11            int minHeight = maxHeightSequence[i]; // Initialize the minimum height seen so far
12
13            // Extend to the left of position 'i' and accumulate heights
14            for (int leftIndex = i - 1; leftIndex >= 0; --leftIndex) {
15                minHeight = min(minHeight, maxHeightSequence[leftIndex]); // Update the min height
16                tempSum += minHeight; // Add the minimum height to the temporary sum
17            }
18
19            // Reset minHeight for checking to the right of 'i'
20            minHeight = maxHeightSequence[i];
21
22            // Extend to the right of position 'i' and accumulate heights
23            for (int rightIndex = i + 1; rightIndex < sequenceLength; ++rightIndex) {
24                minHeight = min(minHeight, maxHeightSequence[rightIndex]); // Update the min height
25                tempSum += minHeight; // Add the minimum height to the temporary sum
26            }
27
28            // Update maxSum if the current temporary sum is greater
29            maxSum = max(maxSum, tempSum);
30        }
31
32        // Return the maximum sum found
33        return maxSum;
34    }
35};
36

1// This function calculates the maximum sum of heights based on the rules provided in the maxHeights array.
2function maximumSumOfHeights(maxHeights: number[]): number {
3    // Initialize the answer variable that holds the maximum sum of heights encountered.
4    let maximumSum = 0;
5    // Get the total number of elements in the maxHeights array.
6    const arrayLength = maxHeights.length;
7  
8    // Iterate over the maxHeights array.
9    for (let currentIndex = 0; currentIndex < arrayLength; ++currentIndex) {
10        // Get the height at the current index.
11        const currentHeight = maxHeights[currentIndex];
12        // Initialize the minimum height variables for left and right directions.
13        let minHeightToLeft = currentHeight;
14        let totalSum = currentHeight;
15      
16        // Iterate over the previous elements from the current index to calculate the sum.
17        for (let leftIndex = currentIndex - 1; leftIndex >= 0; --leftIndex) {
18            // Identify the new minimum height to the left.
19            minHeightToLeft = Math.min(minHeightToLeft, maxHeights[leftIndex]);
20            // Add the minimum height to the left to the total sum.
21            totalSum += minHeightToLeft;
22        }
23      
24        // Reinitialize the minimum height to the current height for the right direction.
25        let minHeightToRight = currentHeight;
26      
27        // Iterate over the next elements from the current index to calculate the sum.
28        for (let rightIndex = currentIndex + 1; rightIndex < arrayLength; ++rightIndex) {
29            // Identify the new minimum height to the right.
30            minHeightToRight = Math.min(minHeightToRight, maxHeights[rightIndex]);
31            // Add the minimum height to the right to the total sum.
32            totalSum += minHeightToRight;
33        }
34      
35        // Compare the current total sum with the previous maximum sum and update maximumSum if necessary.
36        maximumSum = Math.max(maximumSum, totalSum);
37    }
38    // Return the maximum sum of heights after considering all possible positions.
39    return maximumSum;
40}
41

Not Sure What to Study? Take the 2-min Quiz：

What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?

1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8

1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
5        heap.add(arr[i]);
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12

1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85

[30, 20, 10][100, 33, 30][10, 12, 20]

I don’t know

Time and Space Complexity

Time Complexity

The time complexity of the provided code is O(n^2), where n is the length of the maxHeights list. This is because for each element x in maxHeights, the code iterates over the elements to its left and then to its right in separate for-loops. Each of these nested loops runs at most n - 1 times in the worst case, leading to roughly 2 * (n - 1) operations for each of the n elements, thus the quadratic time complexity.

Space Complexity

The space complexity of the provided code is O(1) as it only uses a constant amount of extra space. Variables ans, n, i, x, y, t, and j are used for computations, but no additional space that scales with the input size is used. Therefore, the space used does not depend on the input size and remains constant.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

2865. Beautiful Towers I

Problem Description

Intuition

Solution Approach

Example Walkthrough

Solution Implementation

Time and Space Complexity

Time Complexity

Space Complexity

Recommended Readings