2865. Beautiful Towers I

Problem Description

You are given an array heights of n integers representing the heights of consecutive towers. Your task is to remove some bricks (i.e., decrease the height of the towers) such that the modified array forms a beautiful mountain-shaped configuration. A mountain-shaped configuration is defined by the following criteria:

There exists an index i (0 ≤ i < n) such that:
- For all indices j < i: heights[j] ≤ heights[j+1] (non-decreasing towards the peak)
- For all indices j ≥ i: heights[j] ≥ heights[j+1] (non-increasing from the peak)
The modified height of each tower must be at least 1

Return the maximum possible sum of the modified tower heights.

Intuition

The key insight is to consider each position as a potential mountain peak. For each candidate peak i, we greedily:

Make towers to the left non-decreasing (towards i)
Make towers to the right non-increasing (away from i)

While ensuring no tower exceeds its original height. This approach guarantees we find the maximum possible sum for that peak configuration.

Why it works: By fixing each position as the peak and expanding left/right while respecting height constraints, we systematically explore all possible mountain configurations. Comparing sums from all peaks gives the global maximum.

Solution Approach

Approach

Iterate through each potential peak (every index in the array)
Left expansion: For each peak i, process towers from i-1 to 0:
- At each step j, the maximum allowed height is min(original height, previous tower's adjusted height)
Right expansion: Process towers from i+1 to n-1:
- At each step j, the maximum allowed height is min(original height, previous tower's adjusted height)
Calculate total sum for the current peak configuration and track the maximum sum

Complexity Analysis

Time Complexity: O(n²) - For each of the n peaks, we process up to n-1 elements in each direction
Space Complexity: O(1) - Only uses constant extra space

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Input: heights = [5, 3, 4, 1, 1]
Output: 13
Explanation:

Let's examine the peak at index 0 (height 5):

Left of peak: No towers (already at start)
Right of peak:
- Index 1: Can be at most min(3, 5) = 3
- Index 2: min(4, 3) = 3
- Index 3: min(1, 3) = 1
- Index 4: min(1, 1) = 1
Configuration: [5, 3, 3, 1, 1] → Sum = 5+3+3+1+1 = 13

Other peaks yield smaller sums:

Peak at index 2 (original height 4) gives sum 12
Peak at index 4 gives sum 9

Solution Implementation

1class Solution:
2    def maximumSumOfHeights(self, heights: List[int]) -> int:
3        max_sum = 0
4        n = len(heights)
5        
6        for i in range(n):
7            current_height = heights[i]
8            total = current_height
9            
10            # Process left side
11            min_h = current_height
12            for j in range(i-1, -1, -1):
13                min_h = min(min_h, heights[j])
14                total += min_h
15            
16            # Process right side
17            min_h = current_height
18            for j in range(i+1, n):
19                min_h = min(min_h, heights[j])
20                total += min_h
21            
22            max_sum = max(max_sum, total)
23        
24        return max_sum
25

1class Solution {
2    public long maximumSumOfHeights(List<Integer> heights) {
3        long maxSum = 0;
4        int n = heights.size();
5        
6        for (int i = 0; i < n; i++) {
7            int current = heights.get(i);
8            long total = current;
9            
10            // Process left
11            int minH = current;
12            for (int j = i-1; j >= 0; j--) {
13                minH = Math.min(minH, heights.get(j));
14                total += minH;
15            }
16            
17            // Process right
18            minH = current;
19            for (int j = i+1; j < n; j++) {
20                minH = Math.min(minH, heights.get(j));
21                total += minH;
22            }
23            
24            maxSum = Math.max(maxSum, total);
25        }
26        
27        return maxSum;
28    }
29}
30

1class Solution {
2public:
3    long long maximumSumOfHeights(vector<int>& heights) {
4        long long maxSum = 0;
5        int n = heights.size();
6        
7        for (int i = 0; i < n; ++i) {
8            int current = heights[i];
9            long long total = current;
10            
11            // Left expansion
12            int minH = current;
13            for (int j = i-1; j >= 0; --j) {
14                minH = min(minH, heights[j]);
15                total += minH;
16            }
17            
18            // Right expansion
19            minH = current;
20            for (int j = i+1; j < n; ++j) {
21                minH = min(minH, heights[j]);
22                total += minH;
23            }
24            
25            maxSum = max(maxSum, total);
26        }
27        
28        return maxSum;
29    }
30};
31

1function maximumSumOfHeights(heights: number[]): number {
2    let maxSum = 0;
3    const n = heights.length;
4    
5    for (let i = 0; i < n; i++) {
6        const current = heights[i];
7        let total = current;
8        
9        // Left processing
10        let minH = current;
11        for (let j = i-1; j >= 0; j--) {
12            minH = Math.min(minH, heights[j]);
13            total += minH;
14        }
15        
16        // Right processing
17        minH = current;
18        for (let j = i+1; j < n; j++) {
19            minH = Math.min(minH, heights[j]);
20            total += minH;
21        }
22        
23        maxSum = Math.max(maxSum, total);
24    }
25    
26    return maxSum;
27}
28

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.

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

Which of the following problems can be solved with backtracking (select multiple)

Generating subsets

Generating random numbers

Generating permutations

Sorting integers