3301. Maximize the Total Height of Unique Towers

Problem Description

You are given an array maximumHeight, where maximumHeight[i] denotes the maximum height the i-th tower can be assigned.

Your task is to assign a height to each tower so that:

The height of the i-th tower is a positive integer and does not exceed maximumHeight[i].
No two towers have the same height.

Return the maximum possible total sum of the tower heights. If it's not possible to assign heights, return -1.

Intuition

The core challenge in this problem is to assign heights to the towers such that no two towers have the same height, and the sum of the heights is maximized. The approach utilizes a greedy strategy, combined with sorting, to achieve these goals.

First, sort the array maximumHeight in ascending order. This allows us to start assigning the maximum possible heights to the tallest towers, gradually reducing the height to ensure uniqueness as we proceed.

Next, iterate over the sorted list from the largest possible height decrementing by one-to-one mx, initialized to infinity, to ensure that each assigned height is unique. For each tower, assign it the smaller value between its maximum allowable height and mx - 1. This ensures that each height is both valid and distinct. If, at any point, the required height becomes less than or equal to zero, we determine that the assignment isn't possible and return -1. Otherwise, keep adding the chosen height to a running total answer.

This approach effectively balances maximizing each tower's height while respecting the constraints of uniqueness and positivity. After processing all heights, return the total maximum sum.

Learn more about Greedy and Sorting patterns.

Solution Approach

Solution 1: Sorting + Greedy

The solution adopts a sorting and greedy strategy to efficiently allocate distinct heights to the towers.

Sorting: Begin by sorting the maximumHeight array. This sorting step organizes the data so we can assign heights systematically, from the smallest to the largest maximum allowed height at each step.
Iterative Assignment: Initialize an answer variable ans to store the total sum of assigned heights and a variable mx set to positive infinity inf to keep track of the latest maximum allowed height.
Reverse Iteration: Traverse the sorted maximumHeight array from the end to the start (i.e., from the tallest potential to the shortest). This backward traversal ensures the tallest possible towers get the highest distinct numbers:
- For each tower, calculate the assignable height as min(x, mx - 1), choosing the smaller value between the tower's maximum potential height x and one less than our current maximum permissible height mx.
- If the computed height x is less than or equal to zero, there's no valid, positive height left to assign; in such cases, return -1.
- Otherwise, add this valid, unique height x to ans and update mx to this newly assigned height x to ensure the next assigned height is lower.
Return Result: After iterating through all towers, the sum ans represents the maximum possible total sum of distinct tower heights.

This approach capitalizes on the sorted order of heights to handle constraints systematically, ensuring optimal height usage while respecting uniqueness and positivity conditions.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider a small example to illustrate the solution approach. Suppose we have the array maximumHeight = [3, 5, 4].

Step-by-Step Solution:

Sorting: First, sort the maximumHeight array. After sorting, we get [3, 4, 5].
Iterative Assignment: Initialize ans = 0 to keep the running total of assigned heights. Set mx = inf as the initial "previous height limit" for assignment.
Reverse Iteration: Traverse the sorted list from the end to the start:
- Last Element (5):
  - Calculate the height to be assigned as min(5, mx - 1) = min(5, inf - 1) = 5.
  - Assign height 5 since it's valid and positive.
  - Add 5 to ans, making ans = 5.
  - Update mx = 5.
- Middle Element (4):
  - Calculate the height to be assigned as min(4, mx - 1) = min(4, 5 - 1) = 4.
  - Assign height 4.
  - Add 4 to ans, making ans = 9.
  - Update mx = 4.
- First Element (3):
  - Calculate the height to be assigned as min(3, mx - 1) = min(3, 4 - 1) = 3.
  - Assign height 3.
  - Add 3 to ans, making ans = 12.
  - Update mx = 3.
Final Result: After processing all elements, the maximum possible sum of distinct assigned heights is 12. Hence, the algorithm returns 12.

This example demonstrates how the greedy approach effectively assigns the maximum valid heights while ensuring all heights are distinct and within limits.

Solution Implementation

1from typing import List
2import sys
3
4class Solution:
5    def maximumTotalSum(self, maximumHeight: List[int]) -> int:
6        # Sort the list to process the maximum heights in ascending order
7        maximumHeight.sort()
8        # Initialize the total sum and the maximum possible height with infinity
9        ans, mx = 0, sys.maxsize
10      
11        # Iterate over the maximumHeight list in reverse order
12        for x in reversed(maximumHeight):
13            # Adjust x to be at most mx - 1 to ensure no height is repeated when possible
14            x = min(x, mx - 1)
15            # If x becomes negative or zero, it's impossible to have a positive height
16            if x <= 0:
17                return -1
18            # Add the current valid height to the total sum
19            ans += x
20            # Update mx to the current height
21            mx = x
22      
23        # Return the computed maximum total sum
24        return ans
25

1import java.util.Arrays;
2
3class Solution {
4    public long maximumTotalSum(int[] maximumHeight) {
5        long totalSum = 0; // Initialize the sum of maximum heights
6        int maxAllowedValue = 1 << 30; // Set the initial maximum value as 2^30
7
8        // Sort the maximumHeight array in ascending order
9        Arrays.sort(maximumHeight);
10
11        // Traverse the sorted array from the largest to the smallest element
12        for (int i = maximumHeight.length - 1; i >= 0; --i) {
13            // Get the minimum of maximumHeight[i] and maxAllowedValue - 1
14            int currentHeight = Math.min(maximumHeight[i], maxAllowedValue - 1);
15
16            // If currentHeight is less than or equal to zero, return -1 as it's invalid
17            if (currentHeight <= 0) {
18                return -1;
19            }
20
21            // Add the currentHeight to totalSum
22            totalSum += currentHeight;
23
24            // Update the maxAllowedValue for the next iteration
25            maxAllowedValue = currentHeight;
26        }
27
28        // Return the final total sum
29        return totalSum;
30    }
31}
32

1#include <vector>
2#include <algorithm> // For sort and min functions
3
4class Solution {
5public:
6    long long maximumTotalSum(std::vector<int>& maximumHeight) {
7        // Sort maximumHeight in descending order
8        std::sort(maximumHeight.begin(), maximumHeight.end(), std::greater<int>());
9
10        long long answer = 0;
11        // Assign maximum value using left shift
12        int maxLimit = 1 << 30;
13
14        for (int height : maximumHeight) {
15            // Limit the current height to be less than maxLimit
16            height = std::min(height, maxLimit - 1);
17
18            // If height is non-positive, return -1 as the result
19            if (height <= 0) {
20                return -1;
21            }
22
23            // Add the current height to the total sum
24            answer += height;
25            // Update maxLimit for the next iteration
26            maxLimit = height;
27        }
28
29        return answer;
30    }
31};
32

1function maximumTotalSum(maximumHeight: number[]): number {
2    // Sort the heights in descending order
3    maximumHeight.sort((a, b) => b - a);
4
5    let ans: number = 0;  // To hold the sum of maximum possible heights
6    let mx: number = Infinity;  // Track the maximum allowed height for the current position
7
8    // Iterate through each height in the sorted array
9    for (let height of maximumHeight) {
10        // Determine the largest possible height for the current position
11        height = Math.min(height, mx - 1);
12      
13        // If the height is non-positive, return -1 indicating an invalid result
14        if (height <= 0) {
15            return -1;
16        }
17
18        // Add the adjusted height to the total sum
19        ans += height;
20
21        // Update the maximum allowed height for the next position
22        mx = height;
23    }
24
25    // Return the total maximum sum of heights
26    return ans;
27}
28

Time and Space Complexity

The time complexity of the code is O(n \times \log n). This arises from sorting the maximumHeight list, which takes O(n \times \log n) time, where n is the length of the list. The subsequent for loop iterating through the list contributes O(n) time, but the sorting dominates the overall time complexity.

The space complexity is O(1). Although the reference answer suggests O(\log n), this accounts for the internal stack space used by a typical sorting algorithm like quicksort or mergesort. However, the direct auxiliary space used specifically for storing variables in the code remains constant, or O(1).

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

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: