Beautiful Towers I - Practice Coding Problems

Beautiful Towers I - Problem

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.

Input & Output

Example 1 — Basic Mountain

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

› Output: 13

💡 Note: Best mountain with peak at index 0: [3,3,3,1,1] with sum 11, or peak at index 2: [3,3,4,1,1] with sum 12, or peak at index 0: [5,3,1,1,1] with sum 11. Actually optimal is [5,3,4,1,1] → [3,3,4,1,1] = 12.

Example 2 — Single Tower

$ Input: heights = [6]

› Output: 6

💡 Note: Only one tower, so the mountain is just [6] with sum 6

Example 3 — Decreasing Array

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

› Output: 15

💡 Note: Already mountain-shaped with peak at start: [5,4,3,2,1] sum = 15

Constraints

1 ≤ heights.length ≤ 10³
1 ≤ heights[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array of tower heights [5,3,4,1,1]

Process

Try each position as peak, shape left (non-decreasing) and right (non-increasing)

Output

Maximum sum of mountain-shaped arrangement

Key Takeaway

🎯 Key Insight: Try each position as peak and calculate maximum mountain sum by shaping both sides

Asked in

G Google 25 a Amazon 20 M Microsoft 15

The key insight is to try each position as a potential mountain peak and calculate the maximum sum possible. For each peak, we can only remove bricks (not add), so heights form non-decreasing sequence to the peak and non-increasing from the peak. Best approach is Two-Pass Optimization with Time: O(n²), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Optimization	O(n²)	O(n)	Pre-calculate maximum heights from both directions for each peak
Brute Force - Try Every Peak	O(n³)	O(1)	Try each position as peak and calculate maximum mountain sum

Two-Pass Optimization — Algorithm Steps

Left pass: calculate max height reachable from left
Right pass: calculate max height reachable from right
For each peak: combine left[i] + right[i] - heights[i]
Return maximum combined sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Choose Peak

For each potential peak position

Left Sum

Calculate sum of left side with decreasing constraints

Right Sum

Calculate sum of right side with decreasing constraints

Combine

Total sum = left sum + right sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long solution(int* heights, int n) {
    if (n == 1) return heights[0];
    
    long long maxSum = 0;
    
    for (int peak = 0; peak < n; peak++) {
        // Calculate left side sums (non-decreasing to peak)
        long long leftSum = heights[peak];
        int minHeight = heights[peak];
        for (int i = peak - 1; i >= 0; i--) {
            minHeight = (minHeight < heights[i]) ? minHeight : heights[i];
            leftSum += minHeight;
        }
        
        // Calculate right side sums (non-increasing from peak)
        long long rightSum = 0;
        minHeight = heights[peak];
        for (int i = peak + 1; i < n; i++) {
            minHeight = (minHeight < heights[i]) ? minHeight : heights[i];
            rightSum += minHeight;
        }
        
        long long totalSum = leftSum + rightSum;
        if (totalSum > maxSum) {
            maxSum = totalSum;
        }
    }
    
    return maxSum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int heights[1000];
    int n = 0;
    
    char* token = strtok(line, "[],\n");
    while (token != NULL) {
        if (strlen(token) > 0 && token[0] != '[' && token[0] != ']') {
            heights[n++] = atoi(token);
        }
        token = strtok(NULL, "[],\n");
    }
    
    printf("%lld\n", solution(heights, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

Two O(n) passes to compute left/right arrays, then O(n) peaks each taking O(n) to calculate sum

⚠ Quadratic Growth

Space Complexity

O(n)

Two arrays of size n to store maximum heights from left and right

⚡ Linearithmic Space

18.5K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler