Beautiful Towers II

Medium

Asked by:

40 views

Topics:

ArraysDynamic ProgrammingStacksGreedy Algorithms

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]

Return the maximum possible sum of heights of a beautiful configuration of towers.

Example 1:

Input: maxHeights = [5,3,4,1,1]
Output: 13
Explanation: One beautiful configuration with a maximum sum is heights = [5,3,3,1,1]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]  
- heights is a mountain of peak i = 0.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 13.

Example 2:

Input: maxHeights = [6,5,3,9,2,7]
Output: 22
Explanation: One beautiful configuration with a maximum sum is heights = [3,3,3,9,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 3.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 22.

Example 3:

Input: maxHeights = [3,2,5,5,2,3]
Output: 18
Explanation: One beautiful configuration with a maximum sum is heights = [2,2,5,5,2,2]. This configuration is beautiful since:
- 1 <= heights[i] <= maxHeights[i]
- heights is a mountain of peak i = 2. 
Note that, for this configuration, i = 3 can also be considered a peak.
It can be shown that there exists no other beautiful configuration with a sum of heights greater than 18.

Constraints:

1 <= n == maxHeights.length <= 10⁵
1 <= maxHeights[i] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the height values in the input array? Can they be negative or zero?
What is the maximum size of the input array?
If multiple tower arrangements yield the same maximum sum, is any one of them acceptable?
Could you define 'beautiful tower' more precisely; specifically, what happens at the peak if multiple heights are equal to the maximum height?
Is the input guaranteed to be valid; that is, will the input array always have a size of at least 1?

Brute Force Solution

Approach

To find the most beautiful arrangement of towers, the brute force way means we will explore all possible tower arrangements. We calculate the 'beauty' of each arrangement, and ultimately select the one that yields the greatest beauty. It's like trying every single option until we find the very best one.

Here's how the algorithm would work step-by-step:

First, consider building the tallest tower at the very first position.
Then, consider building the tallest tower at the second position, and so on until the last position. Each of these positions is considered the 'peak'.
For each peak position, imagine building towers to the left and to the right of the peak, making sure the tower heights don't increase as you move away from the peak. In other words, the height of the towers should be non-decreasing when going towards the peak and non-increasing when going away from the peak.
Calculate the total beauty of this specific arrangement (the sum of the heights of all towers).
Repeat this process for every possible peak position.
Compare the beauty of all the arrangements we made, each with a different peak position.
Choose the arrangement that gave us the highest total beauty. That's the most beautiful tower arrangement.

Code Implementation

def beautiful_towers_brute_force(maximum_heights):
    number_of_towers = len(maximum_heights)
    maximum_beauty = 0

    for peak_index in range(number_of_towers):
        # Iterate through all possible peak positions.

        tower_heights = [0] * number_of_towers
        tower_heights[peak_index] = maximum_heights[peak_index]

        # Build towers to the left of the peak.
        for left_index in range(peak_index - 1, -1, -1):
            tower_heights[left_index] = min(maximum_heights[left_index], tower_heights[left_index + 1])

        # Build towers to the right of the peak.
        for right_index in range(peak_index + 1, number_of_towers):
            tower_heights[right_index] = min(maximum_heights[right_index], tower_heights[right_index - 1])

        current_beauty = sum(tower_heights)
        # Calculate beauty for arrangement

        maximum_beauty = max(maximum_beauty, current_beauty)

    return maximum_beauty

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each possible peak position in the array of size n. For each peak position, it constructs a tower arrangement, which involves iterating through the array again to calculate tower heights based on the peak. This nested iteration results in approximately n * n operations. Therefore, the time complexity is O(n²).

Space Complexity

O(N) – The described algorithm iterates through each position as a potential peak. For each peak, it implicitly constructs a temporary array of size N to represent the tower heights for that peak configuration, where N is the number of tower positions. The 'beauty' calculation and comparison also happen within this iteration, using a similar data structure of size N. Therefore, the auxiliary space required scales linearly with the input size N because of the storage for the tower heights for each peak arrangement.

Optimal Solution

Approach

The problem asks us to minimize the overall 'cost' of building towers given height limits. Instead of trying every possible tower arrangement, we find the best arrangement by focusing on the lowest point in each possible tower sequence. This lets us efficiently compute the optimal arrangement using precomputed information.

Here's how the algorithm would work step-by-step:

First, consider each possible location as the lowest point (the peak) of a tower sequence.
For each possible peak, we need to know the maximum height we can build to the left of the peak without exceeding the allowed heights.
Similarly, we need to know the maximum height we can build to the right of the peak without exceeding the allowed heights.
To do this efficiently, precompute the maximum heights allowed to the left and right of each position.
These precomputed left and right limits help you simulate the effect of choosing that position as the peak, and calculating the tower heights to the left and right.
For a given peak, the height of each tower is the minimum of the precomputed height for that position on that side, and the actual tower limit for that tower.
Calculate the sum of tower heights for each peak position. The lowest sum is the solution.

Code Implementation

def beautiful_towers_two(maximum_heights):
    number_of_towers = len(maximum_heights)
    left_max_heights = [0] * number_of_towers
    right_max_heights = [0] * number_of_towers

    left_max_heights[0] = maximum_heights[0]
    for i in range(1, number_of_towers):
        left_max_heights[i] = min(maximum_heights[i], left_max_heights[i - 1] + 1)

    right_max_heights[number_of_towers - 1] = maximum_heights[number_of_towers - 1]
    for i in range(number_of_towers - 2, -1, -1):
        right_max_heights[i] = min(maximum_heights[i], right_max_heights[i + 1] + 1)

    min_sum_heights = float('inf')

    # Iterate through each tower as a potential peak.
    for peak_index in range(number_of_towers):
        current_sum_heights = 0
        
        # Precomputed heights allow simulating tower heights.
        for i in range(peak_index, -1, -1):
            current_sum_heights += min(left_max_heights[i], right_max_heights[i])

        for i in range(peak_index + 1, number_of_towers):
            current_sum_heights += min(left_max_heights[i], right_max_heights[i])

        # Find the smallest sum.
        min_sum_heights = min(min_sum_heights, current_sum_heights - min(left_max_heights[peak_index], right_max_heights[peak_index]))

    return min_sum_heights

Big(O) Analysis

Time Complexity

O(n) – The algorithm precomputes left and right maximum heights for each tower position, which takes O(n) time each. Then it iterates through each possible peak position, calculating the sum of tower heights based on the precomputed left and right limits, also taking O(n) time. The precomputation steps are each O(n) and the peak-finding iteration is O(n), and since these are done sequentially, the overall time complexity is O(n).

Space Complexity

O(N) – The algorithm precomputes the maximum allowed heights to the left and right of each position, resulting in two arrays of size N, where N is the number of towers. Additionally, the algorithm calculates and stores the sum of tower heights for each peak position, which could require another array of size N in the worst-case implementation, although the problem description does not explicitly state this needs to be fully stored. Regardless, auxiliary space scales linearly with the input size N due to the precomputed height arrays, giving a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty base heights array	Return 0 since no towers can be built.
Base heights array with only one element	The beautiful tower will only consist of that element, so return the element's value.
All base heights are the same	The peak will be that same height, and the sum will be that height times the number of towers.
Base heights are strictly increasing	The peak will be the last element, and the tower's height will just be the base heights.
Base heights are strictly decreasing	The peak will be the first element, and each tower's height will match its base height.
Maximum allowed array size reached	Ensure the algorithm's time and space complexity are efficient enough to handle large arrays without exceeding resource limits (e.g., O(n) time, O(n) space).
Integer overflow when calculating the sum of tower heights	Use a larger data type (e.g., long) to store the sum of tower heights to prevent overflow.
Input array contains very large base heights	Check for potential integer overflow during height calculations and use appropriate data types.

Null or empty base heights array

How to Handle:

Return 0 since no towers can be built.

Base heights array with only one element

How to Handle:

The beautiful tower will only consist of that element, so return the element's value.

All base heights are the same

How to Handle:

The peak will be that same height, and the sum will be that height times the number of towers.

Base heights are strictly increasing

How to Handle:

The peak will be the last element, and the tower's height will just be the base heights.

Base heights are strictly decreasing

How to Handle:

The peak will be the first element, and each tower's height will match its base height.

Maximum allowed array size reached

How to Handle:

Ensure the algorithm's time and space complexity are efficient enough to handle large arrays without exceeding resource limits (e.g., O(n) time, O(n) space).

Integer overflow when calculating the sum of tower heights

How to Handle:

Use a larger data type (e.g., long) to store the sum of tower heights to prevent overflow.

Input array contains very large base heights

How to Handle:

Check for potential integer overflow during height calculations and use appropriate data types.