What is the time complexity of Beautiful Towers II?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Beautiful Towers II?

This problem uses Array, Stack, Monotonic Stack. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Beautiful Towers II?

Insight 1: The core idea is to iterate through each possible peak in the `maxHeights` array and calculate the sum of heights assuming that index is the peak. Insight 2: To efficiently calculate the sum for a given peak, we can precompute prefix and suffix sums that represent the sum of heights increasing up to that index (prefix) and decreasing down from that index (suffix).

Which companies ask LeetCode 2866. Beautiful Towers II in interviews?

This problem is frequently asked at Salesforce.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Beautiful Towers II - LeetCode 2866 Solution

Q: How to solve Beautiful Towers II?

The solution uses a dynamic programming approach aided by monotonic stacks to efficiently calculate the maximum sum of heights. It calculates two arrays: `prefix_sum` and `suffix_sum`. `prefix_sum[i]` stores the maximum possible sum of heights for towers from index 0 to `i` such that the heights are increasing up to index `i` (or staying the same), where `maxHeights[i]` is the height of tower at index `i`. `suffix_sum[i]` stores the maximum possible sum of heights for towers from index `i` to `n-1` such that the heights are decreasing from index `i` (or staying the same), where `maxHeights[i]` is the height of tower at index `i`. We iterate through each index `i` as a potential peak, and the total sum for that peak is calculated as `prefix_sum[i] + suffix_sum[i] - maxHeights[i]`. The maximum of these sums across all possible peaks is then returned.

Beautiful Towers II - Complete Solution Guide

Beautiful Towers II is LeetCode problem 2866, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

You are given a 0-indexed array maxHeights of n integers. You are tasked with building n towers in the coordinate line. The i th tower is built at coordinate i and has a height of heights[i] . A configuration of towers is beautiful if the following conditions hold: 1 <= heights[i] <= maxHeights[i] heights is a mountain array. Array heights is a mountain if there exists an index i such that: For all 0 < j <= i , heights[j - 1] <= heights[j] For all i <= k < n - 1 , heights[k + 1] <= heights[k] Re

Detailed Explanation

The problem asks us to find the maximum possible sum of heights of 'beautiful' towers. We're given an array `maxHeights` where `maxHeights[i]` represents the maximum possible height for the tower at index `i`. A configuration of towers is considered beautiful if two conditions are met: (1) the height of each tower `heights[i]` must be between 1 and `maxHeights[i]` (inclusive), and (2) the `heights` array must be a mountain array. A mountain array is one that strictly increases up to a peak and then strictly decreases (or remains constant) after the peak. The goal is to find a beautiful configuration of tower heights such that the sum of the tower heights is maximized.

Solution Approach

The solution uses a dynamic programming approach aided by monotonic stacks to efficiently calculate the maximum sum of heights. It calculates two arrays: `prefix_sum` and `suffix_sum`. `prefix_sum[i]` stores the maximum possible sum of heights for towers from index 0 to `i` such that the heights are increasing up to index `i` (or staying the same), where `maxHeights[i]` is the height of tower at index `i`. `suffix_sum[i]` stores the maximum possible sum of heights for towers from index `i` to `n-1` such that the heights are decreasing from index `i` (or staying the same), where `maxHeights[i]` is the height of tower at index `i`. We iterate through each index `i` as a potential peak, and the total sum for that peak is calculated as `prefix_sum[i] + suffix_sum[i] - maxHeights[i]`. The maximum of these sums across all possible peaks is then returned.

Step-by-Step Algorithm

Step 1: Initialize `prefix_sum` and `suffix_sum` arrays of size `n` with all elements set to 0.
Step 2: Calculate the `prefix_sum` array using a monotonic stack. Iterate from left to right. For each index `i`, pop elements from the stack that are greater than or equal to `maxHeights[i]`. If the stack is empty after popping, it means that `maxHeights[i]` is the smallest element encountered so far, and `prefix_sum[i]` is `(i + 1) * maxHeights[i]`. Otherwise, `prefix_sum[i]` is the sum up to previous element in stack `prefix_sum[stack[-1]] + (i - stack[-1]) * maxHeights[i]`.
Step 3: Calculate the `suffix_sum` array using a monotonic stack. Iterate from right to left. For each index `i`, pop elements from the stack that are greater than or equal to `maxHeights[i]`. If the stack is empty after popping, it means that `maxHeights[i]` is the smallest element encountered so far, and `suffix_sum[i]` is `(n - i) * maxHeights[i]`. Otherwise, `suffix_sum[i]` is the sum down from next element in stack `suffix_sum[stack[-1]] + (stack[-1] - i) * maxHeights[i]`.
Step 4: Iterate through the array and for each `i`, calculate `total_sum = prefix_sum[i] + suffix_sum[i] - maxHeights[i]`. This removes double counting `maxHeights[i]`.
Step 5: Keep track of the maximum `total_sum` and return it.

Key Insights

Insight 1: The core idea is to iterate through each possible peak in the `maxHeights` array and calculate the sum of heights assuming that index is the peak.
Insight 2: To efficiently calculate the sum for a given peak, we can precompute prefix and suffix sums that represent the sum of heights increasing up to that index (prefix) and decreasing down from that index (suffix).
Insight 3: Monotonic stack can be used to determine the height of towers to the left and right of a considered peak, so that `height[i] <= height[i+1]` before peak and `height[i] >= height[i+1]` after peak.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Stack, Monotonic Stack.

Companies

Asked at: Salesforce.

Beautiful Towers II | LeetCode 2866

Medium

Array Stack Monotonic Stack

Time: O(n)Space: O(n)

Solution Code

Available in:

import java.util.List;
import java.util.Stack;

class Solution {
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        
        long[] prefixSum = new long[n];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= maxHeights.get(i)) {
                stack.pop();
            }
            
            if (stack.isEmpty()) {
                prefixSum[i] = (long) (i + 1) * maxHeights.get(i);
            } else {
                int prevIdx = stack.peek();
                prefixSum[i] = prefixSum[prevIdx] + (long) (i - prevIdx) * maxHeights.get(i);
            }
            
            stack.push(i);
        }
        
        long[] suffixSum = new long[n];
        stack = new Stack<>();
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && maxHeights.get(stack.peek()) >= maxHeights.get(i)) {
                stack.pop();
            }
            
            if (stack.isEmpty()) {
                suffixSum[i] = (long) (n - i) * maxHeights.get(i);
            } else {
                int nextIdx = stack.peek();
                suffixSum[i] = suffixSum[nextIdx] + (long) (nextIdx - i) * maxHeights.get(i);
            }
            
            stack.push(i);
        }
        
        long maxSum = 0;
        for (int i = 0; i < n; i++) {
            long totalSum = prefixSum[i] + suffixSum[i] - maxHeights.get(i);
            if (totalSum > maxSum) {
                maxSum = totalSum;
            }
        }
        
        return maxSum;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 2866: Beautiful Towers II - Detailed explanation and solution approaches.

Topics

Array Stack Monotonic Stack

Companies

Salesforce

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:2866

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Initialize `prefix_sum` and `suffix_sum` arrays of size `n` with all elements set to 0.
2
Step 2: Calculate the `prefix_sum` array using a monotonic stack. Iterate from left to right. For each index `i`, pop elements from the stack that are greater than or equal to `maxHeights[i]`. If the stack is empty after popping, it means that `maxHeights[i]` is the smallest element encountered so far, and `prefix_sum[i]` is `(i + 1) * maxHeights[i]`. Otherwise, `prefix_sum[i]` is the sum up to previous element in stack `prefix_sum[stack[-1]] + (i - stack[-1]) * maxHeights[i]`.
3
Step 3: Calculate the `suffix_sum` array using a monotonic stack. Iterate from right to left. For each index `i`, pop elements from the stack that are greater than or equal to `maxHeights[i]`. If the stack is empty after popping, it means that `maxHeights[i]` is the smallest element encountered so far, and `suffix_sum[i]` is `(n - i) * maxHeights[i]`. Otherwise, `suffix_sum[i]` is the sum down from next element in stack `suffix_sum[stack[-1]] + (stack[-1] - i) * maxHeights[i]`.
4
Step 4: Iterate through the array and for each `i`, calculate `total_sum = prefix_sum[i] + suffix_sum[i] - maxHeights[i]`. This removes double counting `maxHeights[i]`.
5
Step 5: Keep track of the maximum `total_sum` and return it.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The monotonic stack operations (push and pop) are amortized O(1) because each element is pushed and popped at most once. The loops iterating through the input array are all O(n). Therefore, the overall time complexity is O(n). The space complexity is dominated by the `prefix_sum`, `suffix_sum` arrays and stack, each using O(n) space.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Brute Force

Try all possible mountain configurations and compute the sum of heights for each. For each index `i`, consider it as the peak. Then iterate through all possible heights from 1 to `maxHeights[i]`. For each height, generate the heights array such that it increases until index `i` with heights less than or equal to the respective `maxHeights` values and decreases after index `i` with heights less than or equal to the respective `maxHeights` values. Then compute the sum of the heights. Take the maximum among all sums.

Time: O(n * m^n), where n is length of the array, and m is the maximum value of the arraySpace: O(n)

Trade-offs: This approach is very inefficient and would time out for large input arrays. The main solution is much faster.

✨

Key Insights

1Insight 1: The core idea is to iterate through each possible peak in the `maxHeights` array and calculate the sum of heights assuming that index is the peak.
2Insight 2: To efficiently calculate the sum for a given peak, we can precompute prefix and suffix sums that represent the sum of heights increasing up to that index (prefix) and decreasing down from that index (suffix).
3Insight 3: Monotonic stack can be used to determine the height of towers to the left and right of a considered peak, so that `height[i] <= height[i+1]` before peak and `height[i] >= height[i+1]` after peak.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Edge Cases

Edge case 1: When the `maxHeights` array is already a mountain array. The algorithm correctly calculates the sum. The use of prefix and suffix sums accounts for this.
Edge case 2: When the `maxHeights` array is monotonically increasing or decreasing. The algorithm still works correctly because the monotonic stacks correctly compute the prefix and suffix sums. The empty stack condition properly handles these cases.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not correctly calculating the prefix and suffix sums. The monotonic stack is crucial to ensuring that the heights are non-decreasing before the peak and non-increasing after the peak.

✗Common mistake 2: Double-counting the peak height. Remember to subtract `maxHeights[i]` when calculating the total sum for a given peak index `i` because it's been included in both the prefix and suffix sums.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Optimizing resource allocation in a network where each node has a maximum capacity. The 'beautiful towers' constraint can model the flow restrictions within the network.

🏦Real-world scenario 2: Designing terrains for a game where you want to find the terrain configuration with the maximum possible land area, subject to constraints on maximum height at each point and the overall terrain shape (mountain-like).

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: November 14, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What problems are best solved with a stack?

Stacks excel at: matching problems (parentheses validation), next greater/smaller element, expression evaluation, backtracking, and undo operations. The key pattern is LIFO (Last In, First Out) - when you need to access the most recently added element.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Beautiful Towers II"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether stack techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?