Problem Description

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.

A mountain-shaped arrangement means:

• The tower heights are non-decreasing from left until reaching a peak
• The peak can be one or multiple consecutive towers with the same maximum height
• After the peak, the tower heights are non-increasing toward the right

You can only remove bricks from towers (reduce their heights), not add bricks. The goal is to find the maximum possible sum of all tower heights after forming a valid mountain shape.

For example, if you have towers [5, 3, 4, 1, 1], one possible mountain arrangement could be [3, 3, 3, 1, 1] where the peak is at height 3, giving a sum of 11. Another arrangement could be [1, 1, 1, 1, 1] with sum 5. The algorithm needs to find the arrangement that maximizes this sum.

The solution approach enumerates each position as a potential peak of the mountain. For each potential peak position i, it:

1. Starts with the height at position i as the peak height
2. Expands leftward, ensuring each tower height doesn't exceed the previous one (maintaining non-decreasing property toward peak)
3. Expands rightward, ensuring each tower height doesn't exceed the previous one (maintaining non-increasing property from peak)
4. Calculates the total sum for this configuration
5. Tracks the maximum sum across all possible peak positions

Intuition

The key insight is that every valid mountain must have a peak somewhere, and once we decide where the peak is, the rest of the arrangement is determined by a greedy strategy.

Think about it this way: if we fix position i as our peak with height maxHeights[i], what's the best we can do? Moving left from the peak, each tower can be at most as tall as the one to its right (to maintain the non-decreasing property toward the peak). So at each position going left, we take the minimum of the current tower's original height and the height we just assigned to its right neighbor. The same logic applies going right from the peak - each tower can be at most as tall as its left neighbor.

This greedy approach works because once we fix the peak, we want to maximize the height at every other position. The constraint is that we can't exceed the original height (we can only remove bricks) and we must maintain the mountain property. Taking the minimum at each step gives us the tallest possible height that satisfies both constraints.

Since we don't know which position should be the peak beforehand, we try all possibilities. For each position i from 0 to n-1, we assume it's the peak and calculate the maximum sum possible with that assumption. The answer is the maximum among all these sums.

The time complexity is O(n²) because for each of the n positions, we potentially scan all n positions to build the mountain. While this might seem expensive, it's acceptable for reasonable input sizes and guarantees we find the optimal solution.

Learn more about Stack and Monotonic Stack patterns.

Solution Approach

The implementation uses a brute force enumeration approach where we try each position as the potential peak of the mountain.

Here's how the algorithm works step by step:

1. Initialize variables: We set ans = 0 to track the maximum sum found, and n = len(maxHeights) to store the array length.

2. Enumerate each peak position: We iterate through each index i and its corresponding height x using enumerate(maxHeights). This position i will be treated as the peak of our mountain.

3. Calculate the mountain sum for peak at position i:

   • Initialize y = x (current height limit) and t = x (total sum starting with peak height)

4. Expand leftward from the peak (indices i-1 down to 0):

   for j in range(i - 1, -1, -1):
       y = min(y, maxHeights[j])
       t += y

   • We maintain y as the maximum allowed height for the current position
   • At each step, y = min(y, maxHeights[j]) ensures we don't exceed the original height and maintain non-decreasing property toward the peak
   • We add this height to our running sum t

5. Expand rightward from the peak (indices i+1 to n-1):

   y = x  # Reset y to peak height
   for j in range(i + 1, n):
       y = min(y, maxHeights[j])
       t += y

   • Reset y back to the peak height x
   • Apply the same logic going right: each position gets min(y, maxHeights[j])
   • This maintains the non-increasing property from the peak

6. Update the maximum: After calculating the sum t for peak at position i, we update ans = max(ans, t).

7. Return the result: After trying all positions as potential peaks, return ans.

The algorithm essentially implements the greedy strategy for each fixed peak position - once we choose a peak, we greedily assign the maximum possible height to each other position while respecting the mountain constraints. By trying all possible peaks, we guarantee finding the optimal solution.

Example Walkthrough

Let's walk through the algorithm with maxHeights = [5, 3, 4, 1, 1].

We'll try each position as the peak and calculate the resulting mountain sum.

Peak at index 0 (height = 5):

• Start with peak: [5, _, _, _, _], sum = 5
• Expand left: (no elements to the left)
• Expand right from index 1:
  • Index 1: min(5, 3) = 3 → [5, 3, _, _, _]
  • Index 2: min(3, 4) = 3 → [5, 3, 3, _, _]
  • Index 3: min(3, 1) = 1 → [5, 3, 3, 1, _]
  • Index 4: min(1, 1) = 1 → [5, 3, 3, 1, 1]
• Total sum = 5 + 3 + 3 + 1 + 1 = 13

Peak at index 1 (height = 3):

• Start with peak: [_, 3, _, _, _], sum = 3
• Expand left from index 0:
  • Index 0: min(3, 5) = 3 → [3, 3, _, _, _]
• Expand right from index 2:
  • Index 2: min(3, 4) = 3 → [3, 3, 3, _, _]
  • Index 3: min(3, 1) = 1 → [3, 3, 3, 1, _]
  • Index 4: min(1, 1) = 1 → [3, 3, 3, 1, 1]
• Total sum = 3 + 3 + 3 + 1 + 1 = 11

Peak at index 2 (height = 4):

• Start with peak: [_, _, 4, _, _], sum = 4
• Expand left from index 1:
  • Index 1: min(4, 3) = 3 → [_, 3, 4, _, _]
  • Index 0: min(3, 5) = 3 → [3, 3, 4, _, _]
• Expand right from index 3:
  • Index 3: min(4, 1) = 1 → [3, 3, 4, 1, _]
  • Index 4: min(1, 1) = 1 → [3, 3, 4, 1, 1]
• Total sum = 3 + 3 + 4 + 1 + 1 = 12

Peak at index 3 (height = 1):

• Start with peak: [_, _, _, 1, _], sum = 1
• Expand left from index 2:
  • Index 2: min(1, 4) = 1 → [_, _, 1, 1, _]
  • Index 1: min(1, 3) = 1 → [_, 1, 1, 1, _]
  • Index 0: min(1, 5) = 1 → [1, 1, 1, 1, _]
• Expand right from index 4:
  • Index 4: min(1, 1) = 1 → [1, 1, 1, 1, 1]
• Total sum = 1 + 1 + 1 + 1 + 1 = 5

Peak at index 4 (height = 1):

• Start with peak: [_, _, _, _, 1], sum = 1
• Expand left from index 3:
  • Index 3: min(1, 1) = 1 → [_, _, _, 1, 1]
  • Index 2: min(1, 4) = 1 → [_, _, 1, 1, 1]
  • Index 1: min(1, 3) = 1 → [_, 1, 1, 1, 1]
  • Index 0: min(1, 5) = 1 → [1, 1, 1, 1, 1]
• Total sum = 1 + 1 + 1 + 1 + 1 = 5

Maximum sum = 13 (achieved with peak at index 0, resulting in [5, 3, 3, 1, 1])

Solution Implementation

Time and Space Complexity

The time complexity of this algorithm is O(n²), where n is the length of the maxHeights array.

This is because:

• The outer loop iterates through each element in maxHeights, running n times
• For each position i, there are two inner loops:
  • The first inner loop iterates from i-1 down to 0, which can be up to i iterations
  • The second inner loop iterates from i+1 to n-1, which can be up to n-i-1 iterations
• In the worst case, when i is in the middle, the total iterations for both inner loops is approximately n-1
• Therefore, the overall time complexity is O(n) × O(n) = O(n²)

The space complexity is O(1) as the algorithm only uses a constant amount of extra space:

• Variables ans, n, i, x, y, t, and j are all scalar values
• No additional data structures are created that scale with the input size
• The algorithm modifies values in-place without requiring auxiliary space proportional to n

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

Common Pitfalls

Pitfall 1: Misunderstanding the Mountain Shape Definition

The Problem: A common misunderstanding is thinking that the mountain must have a single peak tower, when in fact multiple consecutive towers can share the same peak height. Developers might incorrectly implement strict inequality checks (heights must strictly increase then strictly decrease) instead of allowing plateaus at the peak.

Example of Incorrect Implementation:

# WRONG: Enforcing strict increase/decrease
for j in range(peak_idx - 1, -1, -1):
    current_height = min(current_height - 1, maxHeights[j])  # Forces decrease
    total_sum += current_height

Correct Approach:

# CORRECT: Allowing equal heights (plateau)
for j in range(peak_idx - 1, -1, -1):
    current_height = min(current_height, maxHeights[j])  # Allows plateau
    total_sum += current_height

Pitfall 2: Not Resetting the Current Height Between Left and Right Expansions

The Problem: After building the left side of the mountain, forgetting to reset current_height back to peak_height before building the right side. This causes the right side to start with the wrong height value.

Example of Incorrect Implementation:

# Building left side
current_height = peak_height
for j in range(peak_idx - 1, -1, -1):
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

# WRONG: Forgot to reset current_height
# current_height is now the leftmost tower's height, not peak_height!
for j in range(peak_idx + 1, n):
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

Correct Approach:

# Building left side
current_height = peak_height
for j in range(peak_idx - 1, -1, -1):
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

# CORRECT: Reset to peak height before building right side
current_height = peak_height
for j in range(peak_idx + 1, n):
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

Pitfall 3: Off-by-One Errors in Range Iterations

The Problem: Using incorrect range boundaries when iterating left or right from the peak, potentially missing towers or including the peak tower twice.

Example of Incorrect Implementation:

# WRONG: Including peak_idx in left iteration
for j in range(peak_idx, -1, -1):  # This includes peak_idx again!
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

# WRONG: Starting from peak_idx instead of peak_idx + 1
for j in range(peak_idx, n):  # This includes peak_idx again!
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

Correct Approach:

# CORRECT: Start from peak_idx - 1 for left side
for j in range(peak_idx - 1, -1, -1):
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

# CORRECT: Start from peak_idx + 1 for right side
for j in range(peak_idx + 1, n):
    current_height = min(current_height, maxHeights[j])
    total_sum += current_height

Pitfall 4: Trying to Optimize Prematurely with Incorrect Assumptions

The Problem: Attempting to optimize by assuming the peak should always be at the tallest tower in the array, or making other incorrect assumptions about where the optimal peak must be located.

Example of Incorrect Optimization:

# WRONG: Only checking the tallest tower as peak
max_height_idx = maxHeights.index(max(maxHeights))
# Only calculate sum for this single peak position

Why This Fails: The optimal peak might not be at the tallest tower. For example, with maxHeights = [1, 5, 2, 5, 1], the optimal solution uses index 2 (height 2) as the peak, giving [1, 2, 2, 2, 1] with sum 8, rather than using either height-5 tower as the peak.

Correct Approach: Check all positions as potential peaks, as the original solution does. The O(n²) complexity is necessary for correctness in this brute-force approach.