Maximize the Total Height of Unique Towers: Greedy Solution in Python

Maximize the Total Height of Unique Towers (LeetCode 3301) gives you a maximum height for each tower. You must assign every tower a positive integer height that does not exceed its maximum, with all heights different. Return the largest possible total height, or -1 if it can't be done. A greedy approach after sorting solves it in O(n log n).

The problem

You're given an array maximumHeight, where maximumHeight[i] is the highest tower i may be. Choose height[i] so that:

• 1 <= height[i] <= maximumHeight[i]
• all height[i] values are distinct

Return the maximum possible sum, or -1 if no valid assignment exists.

Examples:

The idea

To make the total large, you want every tower as tall as possible. Heights must be distinct, so think about the order: the tallest allowed tower should get the biggest value, the next one the biggest value below that, and so on.

1. Sort the maximums in descending order.
2. Give the first tower its full maximum.
3. For each next tower, assign min(its maximum, previous height - 1).
4. If an assigned height drops to 0 or below, there's no valid assignment, so return -1.
5. Add up the heights.

def maximum_total_sum(maximum_height):
    total = 0
    limit = float("inf")
    for m in sorted(maximum_height, reverse=True):
        h = min(m, limit - 1)
        if h <= 0:
            return -1
        total += h
        limit = h
    return total

Trace on [2,3,4,3]: sorted descending is [4,3,3,2]. Heights: 4, then min(3, 3) = 3, then min(3, 2) = 2, then min(2, 1) = 1. Sum is 10.

Why the greedy works

An exchange argument shows it. Suppose an optimal solution gives a lower height to a tower with a larger maximum than to one with a smaller maximum. Swapping the two heights keeps both within their limits, because the tower with the larger maximum can take any value the smaller one could, and the sum doesn't change. So some optimal solution assigns heights in the same order as the sorted maximums.

Once the order is fixed, each tower can be no taller than its own maximum, and no taller than one less than the tower before it. Taking exactly that upper bound is best: a lower height would reduce the sum now, and it would not help the later towers, because their upper bounds depend on this height, so lowering it only lowers theirs too.

I also checked the code against a brute-force search over all assignments on 2,000 random small arrays, and the answers matched.

Complexity

• Time: O(n log n), dominated by sorting. The loop is O(n).
• Space: O(1) extra if you sort in place, or O(n) for a sorted copy.

Alternative view: count of values

Another way to see the -1 case: with sorted maximums m1 >= m2 >= ... >= mn, a valid assignment exists only if the i-th largest maximum is at least n - i + 1 for each i, since you need that many distinct positive values at or below it. The loop checks this as it goes.

Edge cases

In Java or C++, the total can exceed 32 bits when there are many towers with large maximums, so use long.

How to explain it in an interview

1. Restate the constraints, including the -1 case.
2. Say you want tall towers with distinct heights, so process from the largest maximum down.
3. State the rule: each height is the minimum of its maximum and one less than the previous height.
4. Explain why: swapping heights between towers doesn't help, and each choice is the largest possible.
5. Give complexity and the overflow note.
6. Test with [2,2,1], one element, and all equal values.

Related practice

Similar greedy and sorting problems include Assign Cookies and Minimum Number of Arrows to Burst Balloons. See our Blind 75 study plan and AI LeetCode tutor guide for how to organize practice, and the coding interview assistant guide for review routines.

Explain the exchange argument aloud when you practice. A mock interview transcript shows whether you gave a reason or only the code. Follow the employer's rules on AI tools in any live assessment.