#3301

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Maximize the Total Height of Unique Towers

Assign heights to towers ensuring each height is unique and the total sum is maximized using greedy sorting techniques.

Problem Statement

You are given an array maximumHeight where maximumHeight[i] represents the maximum allowed height of the ith tower. Your goal is to assign an integer height to each tower such that no two towers share the same height.

Return the maximum possible total sum of the tower heights under these constraints. If it is impossible to assign heights uniquely while respecting the maximumHeight limits, return -1.

Examples

Example 1

Input: maximumHeight = [2,3,4,3]

Output: 10

We can assign heights in the following way: [1, 2, 4, 3] .

Example 2

Input: maximumHeight = [15,10]

Output: 25

We can assign heights in the following way: [15, 10] .

Example 3

Input: maximumHeight = [2,2,1]

Output: -1

It's impossible to assign positive heights to each index so that no two towers have the same height.

Constraints

1 <= maximumHeight.length <= 105
1 <= maximumHeight[i] <= 109

Solution Approach

Sort and Greedy Assignment

Sort the maximumHeight array in descending order to prioritize taller towers first. Assign each tower the largest possible height that is strictly less than any previously assigned height to maintain uniqueness.

Invariant Validation

After each assignment, ensure the chosen height does not exceed maximumHeight[i] and is unique. If at any step no valid height exists, immediately return -1 to indicate failure.

Sum Calculation

Accumulate the heights assigned to each tower during the greedy process. The final sum after successful assignment represents the maximum total height achievable under the constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting takes O(n log n), and greedy assignment scans the array once in O(n). Overall time complexity is O(n log n), and space complexity is O(n) to store the sorted array and assigned heights.

What Interviewers Usually Probe

Candidate considers sorting maximumHeight in descending order to enable greedy height assignment.
Candidate validates each assignment to ensure the uniqueness invariant is maintained.
Candidate handles impossible cases early by returning -1 when constraints cannot be satisfied.

Common Pitfalls or Variants

Common pitfalls

Failing to check uniqueness when assigning heights, leading to duplicate tower heights.
Assigning a height larger than maximumHeight[i], violating the problem constraints.
Not handling impossible scenarios, resulting in incorrect sums instead of returning -1.

Follow-up variants

Allow repeated heights but penalize duplicates in total sum calculation.
Maximize total height while minimizing the difference between tallest and shortest tower.
Restrict assignments to a continuous range starting from 1 instead of any positive integers.

FAQ

What is the best approach to maximize the total height of unique towers?

Sort maximumHeight in descending order and assign each tower the largest available unique height less than the previous one.

Why might a valid assignment be impossible?

If the maximumHeight constraints do not allow unique positive heights for all towers, no valid assignment exists.

How does sorting help in this problem?

Sorting ensures taller towers get priority for higher heights, enabling a greedy approach that maximizes total sum while respecting uniqueness.

What is the time complexity of the solution?

Sorting is O(n log n) and the greedy assignment scan is O(n), giving overall O(n log n) time complexity.

Which pattern does this problem illustrate?

It demonstrates a greedy choice plus invariant validation pattern, ensuring each tower's height is unique and valid.

terminal

Solution

Solution 1: Sorting + Greedy

We can sort the maximum heights of the towers in descending order, then allocate the heights one by one starting from the maximum height. Use a variable $mx$ to record the current maximum allocated height.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def maximumTotalSum(self, maximumHeight: List[int]) -> int:
        maximumHeight.sort()
        ans, mx = 0, inf
        for x in maximumHeight[::-1]:
            x = min(x, mx - 1)
            if x <= 0:
                return -1
            ans += x
            mx = x
        return ans

Continue Practicing

#3281 maximize score of numbers in ranges #3273 minimum amount of damage dealt to bob #3362 zero array transformation iii