Problem Description

You are given an array maximumHeight where each element maximumHeight[i] represents the maximum allowed height for the i-th tower.

Your task is to assign a positive integer height to each tower following these rules:

1. Each tower's height must be a positive integer (greater than 0) and cannot exceed its corresponding maximumHeight[i] value
2. All towers must have unique heights (no two towers can have the same height)

The goal is to maximize the total sum of all tower heights. If it's impossible to assign valid heights to all towers while satisfying both conditions, return -1.

For example, if maximumHeight = [2, 3, 4], you could assign heights [2, 3, 4] or [1, 2, 4] or [1, 3, 4], etc. The maximum sum would be 2 + 3 + 4 = 9.

The solution uses a greedy approach by sorting the towers by their maximum allowed heights and assigning the highest possible valid height to each tower. Starting from the tower with the highest maximum allowed height, it assigns heights in descending order, ensuring each subsequent tower gets a height at least 1 less than the previous one. This guarantees uniqueness while maximizing the sum.

Intuition

To maximize the total sum, we want to assign the highest possible heights to towers. The key insight is that if we have multiple towers, we should prioritize giving higher heights to towers that have higher maximum limits.

Think about it this way: if we have two towers with maximum heights [5, 10], we want to assign height 10 to the second tower and height 5 (or less) to the first tower. If we did it the other way around (giving 5 to the second tower and something less to the first), we'd get a smaller sum.

This naturally leads us to sort the towers by their maximum heights. But here's the clever part: we process them from highest to lowest. Why? Because when we assign heights in descending order, we can ensure uniqueness while maximizing each tower's contribution.

Starting from the tower with the highest maximum limit, we assign it the highest possible height. For the next tower, we need to ensure uniqueness, so we assign it at most previous_height - 1. This creates a descending sequence of heights.

The variable mx tracks the maximum height we can assign to the current tower (considering the uniqueness constraint from previously assigned towers). For each tower, we take the minimum of its maximum allowed height and mx - 1. This ensures we respect both the tower's limit and the uniqueness requirement.

If at any point we need to assign a height of 0 or less (which happens when we have too many towers with low maximum heights), it becomes impossible to satisfy all constraints, so we return -1.

This greedy strategy works because assigning the maximum possible height at each step (while maintaining uniqueness) guarantees the optimal sum - there's no benefit to "saving" height capacity for later towers.

Learn more about Greedy and Sorting patterns.

Solution Approach

The implementation follows a sorting and greedy strategy:

1. Sort the array in ascending order: We start by sorting maximumHeight array. This allows us to process towers from those with smaller maximum limits to those with larger limits when we iterate in reverse.

2. Process towers from highest to lowest: We iterate through the sorted array in reverse order using maximumHeight[::-1]. This ensures we handle towers with higher maximum limits first, allowing us to assign them the highest possible heights.

3. Track the maximum assignable height: We initialize a variable mx to infinity (inf) to track the maximum height we can assign to the current tower. This variable ensures we maintain the uniqueness constraint - each tower must have a height at least 1 less than the previous tower's height.

4. Assign heights greedily: For each tower with maximum height x:

   • Calculate the actual height to assign: x = min(x, mx - 1). This takes the minimum of the tower's maximum allowed height and one less than the previously assigned height.
   • Check if assignment is valid: If x <= 0, it means we cannot assign a positive height to this tower while maintaining uniqueness, so we return -1.
   • Add the assigned height to the answer: ans += x
   • Update the maximum for the next tower: mx = x

5. Return the total sum: After successfully assigning heights to all towers, return the accumulated sum ans.

The algorithm runs in O(n log n) time due to sorting, where n is the number of towers. The space complexity is O(1) if we don't count the space used for sorting.

Example walkthrough with maximumHeight = [2, 5, 3]:

• After sorting: [2, 3, 5]
• Process in reverse: [5, 3, 2]
• Tower with max 5: assign height 5 (min(5, inf-1)), mx = 5, sum = 5
• Tower with max 3: assign height 3 (min(3, 4)), mx = 3, sum = 8
• Tower with max 2: assign height 2 (min(2, 2)), mx = 2, sum = 10
• Return 10

Example Walkthrough

Let's walk through the solution with maximumHeight = [2, 5, 3, 1]:

Step 1: Sort the array

• Original: [2, 5, 3, 1]
• After sorting: [1, 2, 3, 5]

Step 2: Process towers in reverse order We'll process [5, 3, 2, 1] and track our running sum and the maximum height we can assign next (mx).

Initial state:

• ans = 0 (total sum)
• mx = infinity (no restrictions yet)

Processing tower with max height 5:

• Can assign: min(5, mx - 1) = min(5, inf - 1) = 5
• Valid? Yes, 5 > 0 ✓
• Update: ans = 0 + 5 = 5, mx = 5
• Heights assigned so far: [5]

Processing tower with max height 3:

• Can assign: min(3, mx - 1) = min(3, 5 - 1) = min(3, 4) = 3
• Valid? Yes, 3 > 0 ✓
• Update: ans = 5 + 3 = 8, mx = 3
• Heights assigned so far: [5, 3]

Processing tower with max height 2:

• Can assign: min(2, mx - 1) = min(2, 3 - 1) = min(2, 2) = 2
• Valid? Yes, 2 > 0 ✓
• Update: ans = 8 + 2 = 10, mx = 2
• Heights assigned so far: [5, 3, 2]

Processing tower with max height 1:

• Can assign: min(1, mx - 1) = min(1, 2 - 1) = min(1, 1) = 1
• Valid? Yes, 1 > 0 ✓
• Update: ans = 10 + 1 = 11, mx = 1
• Heights assigned so far: [5, 3, 2, 1]

Result: Return 11

The final assignment gives towers heights [1, 5, 3, 2] (mapping back to original order), which are all unique, positive, and within their maximum limits. The sum is maximized at 11.

Example of impossible case: If maximumHeight = [1, 1, 1]:

• After sorting: [1, 1, 1]
• Process first tower (max=1): assign height 1
• Process second tower (max=1): need height ≤ 0 (since previous was 1)
• Return -1 because we can't assign positive unique heights

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array maximumHeight. This is dominated by the sorting operation maximumHeight.sort(), which uses a comparison-based sorting algorithm (typically Timsort in Python) that has O(n × log n) time complexity. The subsequent loop that iterates through the sorted array in reverse order takes O(n) time, but this is overshadowed by the sorting cost.

The space complexity is O(log n). While the sorting operation is performed in-place and doesn't require additional space proportional to the input size, the sorting algorithm itself uses O(log n) space for the recursion stack during the sorting process (in the case of Timsort, this is for the merge operations). The reverse iteration maximumHeight[::-1] creates a reversed view but doesn't create a new list in modern Python implementations, and the few variables used (ans, mx, x) only require O(1) additional space.

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

Common Pitfalls

Pitfall 1: Not Handling the Impossible Case Correctly

The Problem: A common mistake is forgetting to check if it's impossible to assign valid heights. This happens when we have too many towers with low maximum heights. For example, with maximumHeight = [1, 1, 1, 1], we need to assign 4 different positive heights, but the maximum any tower can be is 1, making it impossible.

Why It Happens: Developers might focus on the greedy assignment logic but overlook the validation that ensures all towers can receive positive, unique heights.

The Solution: Always check if the assigned height becomes zero or negative:

if assigned_height <= 0:
    return -1

Pitfall 2: Incorrect Order of Processing

The Problem: Processing towers in the wrong order (from smallest to largest maximum height) leads to suboptimal solutions. For example, with maximumHeight = [5, 2, 4], if we process in ascending order [2, 4, 5], we might assign heights [2, 3, 4] = 9, but the optimal is [1, 4, 5] = 10.

Why It Happens: The intuition might be to handle constrained towers first, but this actually limits our choices for towers with higher maximum heights.

The Solution: Always sort first, then process in descending order:

maximumHeight.sort()
for max_height in maximumHeight[::-1]:  # Process from largest to smallest

Pitfall 3: Off-by-One Error in Height Assignment

The Problem: Forgetting to subtract 1 when calculating the next available height, which would allow duplicate heights. Using max_allowed_height instead of max_allowed_height - 1 violates the uniqueness constraint.

Why It Happens: The uniqueness requirement is easy to overlook when focusing on maximizing the sum.

The Solution: Ensure each tower gets a height strictly less than the previous:

assigned_height = min(max_height, max_allowed_height - 1)

Pitfall 4: Integer Overflow with Initial Value

The Problem: Using a very large integer like 10^9 as the initial maximum might seem sufficient, but if the first tower has a maximum height larger than this value, it would be incorrectly capped.

Why It Happens: Hardcoding large values instead of using infinity can create edge cases.

The Solution: Use float('inf') or math.inf for the initial value:

max_allowed_height = inf  # Not 10**9 or other arbitrary large number