LeetCode 3301 - Maximize the Total Height of Unique Towers

LeetCode Problem 3301

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting

Solution

Problem Understanding

We are given an array maximumHeight where maximumHeight[i] represents the largest height that tower i is allowed to have.

Our goal is to assign an actual height to every tower such that:

• Every assigned height is a positive integer.
• The assigned height of tower i is at most maximumHeight[i].
• All assigned heights are distinct.

Among all valid assignments, we want the one with the largest possible total sum of heights.

If no valid assignment exists, we must return -1.

The important detail is that the towers themselves do not have any required ordering. We only care about choosing one unique height for each tower within its allowed limit. Since heights must be distinct and positive, the challenge is to maximize the sum while avoiding collisions.

The constraints are large:

• Up to 10^5 towers.
• Each maximum height can be as large as 10^9.

These limits immediately rule out any approach that tries to explicitly test many possible height assignments. We need an algorithm that is roughly O(n log n) or better.

Several edge cases are important:

• Multiple towers may have the same maximum allowed height.
• Many towers may have very small maximum heights, making uniqueness impossible.
• A single tower is always solvable if its maximum height is at least 1.
• Large values up to 10^9 require careful handling of sums, especially in Go where int64 should be used.

Approaches

Brute Force

A brute force approach would try to assign heights to towers while checking all possible combinations.

For each tower, we could choose any value between 1 and maximumHeight[i], then verify whether all chosen heights are unique and compute the total sum. Among all valid assignments, we would keep the maximum.

This approach is correct because it explores the entire solution space and therefore cannot miss the optimal assignment.

However, it is completely infeasible. A tower may have up to 10^9 possible heights, and there can be 10^5 towers. The number of possible assignments is astronomically large.

Therefore, we need a more efficient strategy.

Key Insight

To maximize the total sum, every tower should receive the largest height possible while still preserving uniqueness.

Consider sorting the maximum heights in descending order.

Suppose we process towers from the largest maximum height to the smallest. When assigning a height to the current tower, the best choice is the largest value that:

• Does not exceed its maximum allowed height.
• Is strictly smaller than the height assigned to the previous larger tower.

Why is this optimal?

Because larger maximum heights have the most flexibility and contribute the most to the final sum. Whenever we process a tower, choosing anything smaller than the largest feasible value would only reduce the total sum and cannot help future towers, since future towers already have smaller maximum limits.

This creates a simple greedy rule:

• Sort descending.
• Let prev be the previously assigned height.
• For each maximum height h, assign

assigned = min(h, prev - 1)

for all towers except the first one.

If at any point the assigned value becomes 0 or negative, a valid assignment is impossible because heights must be positive.

This greedy strategy always maximizes the sum.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Tries all possible assignments
Optimal Greedy + Sorting	O(n log n)	O(1) extra, ignoring sort space	Assign largest feasible unique height after sorting

Algorithm Walkthrough

1. Sort maximumHeight in descending order.

This allows us to process towers with the largest allowable heights first. These towers have the greatest flexibility and should receive the largest heights. 2. Assign the first tower its maximum height.

Since no previous assignment exists, giving it its largest allowed value is always optimal. 3. Maintain the previously assigned height.

Let previousHeight store the last assigned value. 4. For each remaining tower:

Compute

currentHeight = min(maximumHeight[i], previousHeight - 1)

This is the largest height that remains unique. 5. Check validity.

If currentHeight <= 0, then no positive distinct height can be assigned to this tower. Return -1. 6. Add the assigned height to the answer.

Since we always choose the largest feasible value, we maximize the contribution of each tower. 7. Update previousHeight.

Set it to currentHeight and continue. 8. After processing all towers, return the accumulated sum.

Why it works

After sorting in descending order, every future tower has a maximum height less than or equal to the current one. When assigning a height, the only restriction needed to preserve uniqueness is that it must be strictly smaller than the previous assigned height. Choosing the largest feasible value maximizes the current contribution without reducing any future options. Therefore, the greedy choice is always optimal, and repeating it for every tower yields the maximum possible total sum.

Python Solution

from typing import List

class Solution:
    def maximumTotalSum(self, maximumHeight: List[int]) -> int:
        maximumHeight.sort(reverse=True)

        total_sum = 0
        previous_height = float("inf")

        for height in maximumHeight:
            assigned_height = min(height, previous_height - 1)

            if assigned_height <= 0:
                return -1

            total_sum += assigned_height
            previous_height = assigned_height

        return total_sum

The implementation begins by sorting the array in descending order. This ensures that towers with the largest allowable heights are processed first.

The variable previous_height tracks the most recently assigned height. It is initialized to infinity so that the first tower can receive its full maximum height.

For each tower, we compute the largest valid unique height using:

assigned_height = min(height, previous_height - 1)

This guarantees both constraints:

• It does not exceed the tower's maximum.
• It remains strictly smaller than the previous assigned height.

If the resulting value becomes zero or negative, no valid assignment exists, so the function immediately returns -1.

Otherwise, the assigned height is added to the running total, and previous_height is updated for the next iteration.

After all towers have been processed successfully, the accumulated sum is returned.

Go Solution

package main

import "sort"

func maximumTotalSum(maximumHeight []int) int64 {
	sort.Sort(sort.Reverse(sort.IntSlice(maximumHeight)))

	var totalSum int64
	prevHeight := int(1 << 60)

	for _, height := range maximumHeight {
		assignedHeight := height
		if prevHeight-1 < assignedHeight {
			assignedHeight = prevHeight - 1
		}

		if assignedHeight <= 0 {
			return -1
		}

		totalSum += int64(assignedHeight)
		prevHeight = assignedHeight
	}

	return totalSum
}

The Go implementation follows exactly the same greedy strategy. The primary difference is that the answer is accumulated in an int64 because the sum can be much larger than a 32-bit integer.

The sorted slice is processed from largest to smallest maximum height. For each tower, the largest feasible unique height is computed and validated before being added to the total.

Worked Examples

Example 1

Input

[2, 3, 4, 3]

After sorting:

[4, 3, 3, 2]

Tower	Max Height	Previous Height	Assigned Height	Running Sum
1	4	inf	4	4
2	3	4	3	7
3	3	3	2	9
4	2	2	1	10

Final answer:

10

Example 2

Input

[15, 10]

After sorting:

[15, 10]

Tower	Max Height	Previous Height	Assigned Height	Running Sum
1	15	inf	15	15
2	10	15	10	25

Final answer:

25

Example 3

Input

[2, 2, 1]

After sorting:

[2, 2, 1]

Tower	Max Height	Previous Height	Assigned Height	Running Sum
1	2	inf	2	2
2	2	2	1	3
3	1	1	0	Invalid

Since the third tower would need height 0, no valid assignment exists.

Final answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) extra, ignoring sort space	Only a few variables are maintained

The sorting step requires O(n log n) time. The subsequent greedy pass scans the array exactly once, contributing O(n) time. Therefore the overall complexity is O(n log n).

The algorithm stores only a few scalar variables in addition to the input array. Ignoring the internal memory used by the sorting implementation, the extra space usage is O(1).

Test Cases

from typing import List

s = Solution()

assert s.maximumTotalSum([2, 3, 4, 3]) == 10      # example 1
assert s.maximumTotalSum([15, 10]) == 25          # example 2
assert s.maximumTotalSum([2, 2, 1]) == -1         # example 3

assert s.maximumTotalSum([1]) == 1                # single tower
assert s.maximumTotalSum([1000000000]) == 1000000000  # large value

assert s.maximumTotalSum([3, 3, 3]) == 6          # assign 3,2,1
assert s.maximumTotalSum([1, 1]) == -1            # impossible duplicate minimums

assert s.maximumTotalSum([5, 4, 3, 2, 1]) == 15  # already unique
assert s.maximumTotalSum([5, 5, 5, 5]) == 14     # assign 5,4,3,2

assert s.maximumTotalSum([4, 1, 4]) == 8         # assign 4,3,1
assert s.maximumTotalSum([2, 1]) == 3            # smallest valid pair

assert s.maximumTotalSum([100, 100, 100, 100]) == 394  # repeated large values
assert s.maximumTotalSum([3, 2, 2, 1]) == -1     # becomes non-positive

Test Summary

Test	Why
[2,3,4,3]	Official example with duplicates
[15,10]	Official example already valid
[2,2,1]	Official impossible case
[1]	Smallest input size
[1000000000]	Maximum height value
[3,3,3]	Repeated values but still solvable
[1,1]	Small repeated values causing failure
[5,4,3,2,1]	Already uniquely assignable
[5,5,5,5]	Requires repeated decrements
[4,1,4]	Mixed large and small values
[2,1]	Small valid configuration
[100,100,100,100]	Large repeated values
[3,2,2,1]	Greedy eventually reaches zero

Edge Cases

Many Towers Share the Same Maximum Height

An input such as:

[5, 5, 5, 5]

can easily cause bugs if uniqueness is not enforced carefully. The optimal assignment is 5, 4, 3, 2. The greedy algorithm naturally produces this sequence because every new tower is forced to be strictly smaller than the previous assigned height.

Heights Eventually Reach Zero

Consider:

[2, 2, 1]

After assigning heights 2 and 1, the next tower would require height 0 to remain unique. Since only positive heights are allowed, the assignment becomes impossible. The implementation explicitly checks assigned_height <= 0 and returns -1.

Very Large Maximum Heights

Inputs such as:

[1000000000, 1000000000, 1000000000]

require handling large values safely. The greedy logic remains unchanged because it only performs comparisons and decrements. In Go, the accumulated sum is stored in int64 to avoid overflow. The Python implementation automatically supports arbitrarily large integers.

Single Tower Input

When the array contains only one tower, such as:

[7]

the answer is simply 7. The sorting and greedy logic still work correctly because the first tower receives its maximum allowed height, and no uniqueness conflicts can occur.