Beautiful Towers I

Medium

Beautiful Towers I

Medium

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 length of the `maxHeights` array and the value range of each element within it?
Can the `maxHeights` array contain zero values? Are negative values allowed?
If there are multiple possible beautiful towers, should I return the maximum possible sum, or can I return the sum of any valid tower?
Is the input array guaranteed to be valid, or should I handle cases where it might be null or empty?
Could you define more precisely what constitutes a 'beautiful tower'? Specifically, if the max height appears multiple times in the `maxHeights` array, which occurrence should be considered the peak?

Brute Force Solution

Approach

The brute force approach to this tower problem is simple: try every single possible tower configuration. Calculate the total beauty of each possible tower and keep track of the best one we've seen so far. By checking absolutely every option, we are guaranteed to find the most beautiful tower.

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

Consider each location as the peak of our tower, one at a time.
For each peak location, construct a tower where that location is the highest point.
To build the tower, start at the peak and work outwards, ensuring each block's height doesn't exceed the block heights provided and that the height decreases as we move away from the peak.
Calculate the total beauty of this constructed tower by adding up the heights of all its blocks.
Compare this total beauty to the beauty of the best tower we've seen so far. If it's better, update our record of the best tower.
Repeat these steps for every possible peak location.
After exhausting all possible peak locations, the tower with the highest calculated beauty is our answer.

Code Implementation

def beautiful_towers_brute_force(max_heights):
    number_of_towers = len(max_heights)
    max_beauty = 0

    for peak_index in range(number_of_towers):
        # Iterate through each index and treat it as the peak
        current_tower = [0] * number_of_towers
        current_tower[peak_index] = max_heights[peak_index]
        
        # Build to the left of the peak
        for left_index in range(peak_index - 1, -1, -1):
            current_tower[left_index] = min(max_heights[left_index], current_tower[left_index + 1])

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

        tower_beauty = sum(current_tower)
        # Update max beauty if necessary
        if tower_beauty > max_beauty:
            max_beauty = tower_beauty

    return max_beauty

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each of the n locations as a potential peak. For each peak, it constructs a tower which, in the worst case, requires examining and potentially modifying the height of every block in the array relative to the peak. This tower construction process takes O(n) time. Because this O(n) tower construction is performed for each of the n possible peaks, the overall time complexity is O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The algorithm constructs a tower for each possible peak location. To build the tower, it needs to store the heights of the blocks in a temporary array. In the worst case, this temporary array will have the same size as the input array representing the given block heights, which is N. Therefore, the auxiliary space required is proportional to N, resulting in a space complexity of O(N).

Optimal Solution

Approach

The trick to efficiently solving this problem is to consider each possible tower location as the tallest point and build outwards. For each potential tallest tower, we expand to the left and right, lowering the tower heights as necessary to meet the problem's constraints.

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

Imagine each location as the tallest tower in the entire arrangement.
For each of these tallest tower guesses, start building the towers around it.
Moving left and right from this tallest tower, make the tower heights decrease, stopping at the minimum allowed height or when you reach the edge.
Calculate the sum of heights of all the towers in each arrangement.
Pick the tower arrangement that provides the largest possible sum of heights.

Code Implementation

def beautiful_towers_i(maximum_heights):
    number_of_towers = len(maximum_heights)
    max_sum_heights = 0

    for tallest_tower_index in range(number_of_towers):
        tower_heights = [0] * number_of_towers
        tower_heights[tallest_tower_index] = maximum_heights[tallest_tower_index]
        current_sum_heights = tower_heights[tallest_tower_index]

        # Build to the left of the tallest tower.
        left_index = tallest_tower_index - 1
        while left_index >= 0:
            # Ensure the current tower is no taller than the tower to its right
            tower_heights[left_index] = min(maximum_heights[left_index], tower_heights[left_index + 1])
            current_sum_heights += tower_heights[left_index]
            left_index -= 1

        # Build to the right of the tallest tower.
        right_index = tallest_tower_index + 1
        while right_index < number_of_towers:
            # Ensure the current tower is no taller than the tower to its left
            tower_heights[right_index] = min(maximum_heights[right_index], tower_heights[right_index - 1])
            current_sum_heights += tower_heights[right_index]
            right_index += 1

        # Keep track of the largest sum found.
        max_sum_heights = max(max_sum_heights, current_sum_heights)

    return max_sum_heights

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through each element of the input array of size n, considering each as the potential peak of a tower arrangement. For each peak, it expands outwards to the left and right, potentially examining all other elements to determine the tower heights. This expansion process, in the worst case, involves traversing the entire array from the peak to both ends, requiring O(n) operations. Since this expansion is performed for each of the n potential peak positions, the overall time complexity becomes O(n * n), which simplifies to O(n²).

Space Complexity

O(N) – The described solution iterates through each location as a potential tallest tower and, for each of these locations, it builds a tower arrangement. This process requires constructing a new array of tower heights whose size is dependent on the number of input locations, N. Thus, for each possible tallest tower, we need to create temporary arrays of size N to store the tower heights, resulting in O(N) auxiliary space in each iteration. As the algorithm considers each tower in the original array, the maximum space used is proportional to the size of the input.

Edge Cases

Case	How to Handle
Empty heights array	Return 0 immediately as there are no towers to build.
Single element heights array	Return the value of the single element since it's a valid beautiful tower.
All heights are the same	The resulting beautiful tower will also have all heights the same, equal to the input height, and sum calculation will work as expected.
Heights array is strictly increasing	The maximum height will be the last element, and no modification is needed.
Heights array is strictly decreasing	The beautiful tower will be strictly decreasing as well, ending with height 1.
Heights array contains large numbers, potential for integer overflow when calculating the sum	Use a 64-bit integer type (long) to store the sum of the beautiful tower to avoid overflow.
Heights array with the maximum size allowed by the problem constraints	Ensure the chosen algorithm has a time complexity that is efficient enough to handle the maximum input size, ideally O(n) or O(n log n).
heights[i] is zero	The beautiful tower can include zero as one of its element and the solution should correctly compute the sum based on the given heights array.