Scale Engineer

Beautiful Towers I

Med
#2562Time: O(N^2), where N is the number of towers. The outer loop runs N times, and for each iteration, we perform two inner loops that together iterate through the rest of the array, taking O(N) time.Space: O(1), as we only use a few variables to store the current sum and last height, not counting the input storage.1 company
Data structures
ArrayStackMonotonic Stack
Companies
Salesforce

Prompt

You are given an array heights of n integers representing the number of bricks in n consecutive towers. Your task is to remove some bricks to form a mountain-shaped tower arrangement. In this arrangement, the tower heights are non-decreasing, reaching a maximum peak value with one or multiple consecutive towers and then non-increasing.

Return the maximum possible sum of heights of a mountain-shaped tower arrangement.

 

Example 1:

Input: heights = [5,3,4,1,1]

Output: 13

Explanation:

We remove some bricks to make heights = [5,3,3,1,1], the peak is at index 0.

Example 2:

Input: heights = [6,5,3,9,2,7]

Output: 22

Explanation:

We remove some bricks to make heights = [3,3,3,9,2,2], the peak is at index 3.

Example 3:

Input: heights = [3,2,5,5,2,3]

Output: 18

Explanation:

We remove some bricks to make heights = [2,2,5,5,2,2], the peak is at index 2 or 3.

 

Constraints:

  • 1 <= n == heights.length <= 103
  • 1 <= heights[i] <= 109

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward approach is to consider every possible tower as the peak of the mountain. For each potential peak, we can calculate the total number of bricks in the resulting mountain-shaped arrangement and keep track of the maximum sum found. This method exhaustively checks every valid mountain configuration that can be formed.

Algorithm

  • Initialize a variable maxSum to 0.
  • Iterate through each index i from 0 to n-1, considering i as the peak of the mountain.
  • For each potential peak i:
    • Initialize currentSum with the height of the peak, heights.get(i).
    • Initialize a lastHeight variable to heights.get(i).
    • Calculate the sum for the left side (non-decreasing part):
      • Iterate from j = i-1 down to 0.
      • The height at j is constrained by its original height and the height of the tower to its right. Update lastHeight = min(heights.get(j), lastHeight).
      • Add this lastHeight to currentSum.
    • Calculate the sum for the right side (non-increasing part):
      • Reset lastHeight to heights.get(i).
      • Iterate from j = i+1 up to n-1.
      • The height at j is constrained by its original height and the height of the tower to its left. Update lastHeight = min(heights.get(j), lastHeight).
      • Add this lastHeight to currentSum.
    • Update maxSum = max(maxSum, currentSum).
  • After checking all possible peaks, return maxSum.

Walkthrough

We iterate through each index i from 0 to n-1, treating heights[i] as the peak of the mountain. For each i, we calculate the sum of heights for the corresponding mountain configuration. The height of the peak tower is heights[i]. To form the non-decreasing left side (from index 0 to i-1), we iterate backwards from i-1 to 0. The height of tower j is limited by its original height heights[j] and the height of the tower to its right, new_heights[j+1]. So, new_heights[j] = min(heights[j], new_heights[j+1]). Similarly, for the non-increasing right side (from index i+1 to n-1), we iterate forwards from i+1 to n-1. The height of tower j is new_heights[j] = min(heights[j], new_heights[j-1]). We sum up the heights of all towers in this configuration. We keep a global maximum variable, updating it with the sum for each peak i if it's larger. After checking all possible peaks, the global maximum will be our answer.

import java.util.List;import java.lang.Math; class Solution {    public long maximumSumOfHeights(List<Integer> heights) {        int n = heights.size();        long maxTotalSum = 0;         for (int i = 0; i < n; i++) {            long currentSum = heights.get(i);                        // Calculate sum for the left side (non-decreasing)            long lastHeight = heights.get(i);            for (int j = i - 1; j >= 0; j--) {                lastHeight = Math.min(heights.get(j), lastHeight);                currentSum += lastHeight;            }             // Calculate sum for the right side (non-increasing)            lastHeight = heights.get(i);            for (int j = i + 1; j < n; j++) {                lastHeight = Math.min(heights.get(j), lastHeight);                currentSum += lastHeight;            }             maxTotalSum = Math.max(maxTotalSum, currentSum);        }         return maxTotalSum;    }}

Complexity

Time

O(N^2), where N is the number of towers. The outer loop runs N times, and for each iteration, we perform two inner loops that together iterate through the rest of the array, taking O(N) time.

Space

O(1), as we only use a few variables to store the current sum and last height, not counting the input storage.

Trade-offs

Pros

  • Simple to understand and implement.

  • Requires minimal extra space.

Cons

  • Inefficient for large inputs due to its quadratic time complexity. It might result in a 'Time Limit Exceeded' error on platforms with stricter time limits or larger constraints.

Solutions

class Solution {public  long maximumSumOfHeights(List<Integer> maxHeights) {    long ans = 0;    int n = maxHeights.size();    for (int i = 0; i < n; ++i) {      int y = maxHeights.get(i);      long t = y;      for (int j = i - 1; j >= 0; --j) {        y = Math.min(y, maxHeights.get(j));        t += y;      }      y = maxHeights.get(i);      for (int j = i + 1; j < n; ++j) {        y = Math.min(y, maxHeights.get(j));        t += y;      }      ans = Math.max(ans, t);    }    return ans;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem