Practice Maximize the Total Height of Unique Towers
Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.
Problem Statement
Assign a positive integer height to every tower. Tower i cannot exceed maximumHeight[i], and all assigned heights must differ. Maximize their sum, or return -1 if no assignment exists. Approach: Sort the upper bounds from largest to smallest. Give the first tower its upper bound; each following height is the smaller of its own bound and the previous height minus one. A nonpositive choice means no valid assignment exists. Choosing each height as high as possible leaves the most room for subsequent towers. Sorting takes O(n log n) time; accumulate the answer in a 64-bit integer.
Source: Maximize the Total Height of Unique Towers on LeetCode. Use the original task for its coding environment and submissions.
Examples
# Example 1
maximumHeight = [5,5,3]
12
Assign heights 5, 4, and 3. They are distinct, within their bounds, and sum to 12.
# Example 2
maximumHeight = [1,1]
-1
Both towers would need height 1, which violates uniqueness.
Constraints
How to solve Maximize the Total Height of Unique Towers
Original notes for interview preparation, written for this problem. Reviewed .
Key insight
Process the towers from the largest bound downward and give each the highest height still available, which is the smaller of its own bound and one less than the previous height. Taking the most for the current tower never hurts a later one because every later tower has an equal or smaller bound.
Why brute force is not enough
Enumerating assignments is exponential, and even a per-tower scan downward through used heights with a set can cost many steps per tower when bounds reach 10^9 and n is up to 100,000, so a direct used-height array or search is impractical.
Approach
- Sort the maximum heights in descending order. The invariant through the scan is that all assigned heights so far are distinct and strictly decreasing.
- Assign the first tower its full bound.
- For each subsequent tower, set its height to the minimum of its own bound and the previous assigned height minus one. This is the largest value that respects both its bound and uniqueness against everything already placed.
- If that value is zero or negative, no valid assignment exists because this tower and all remaining ones have bounds too small to be distinct positive integers; return -1 immediately.
- Accumulate the heights in a 64-bit sum and return it. Exchange reasoning shows any assignment can be transformed into this one without lowering the total.
Walkthrough of Example 1
maximumHeight = [5,5,3] → 12
- maximumHeight is [5,5,3]; sorted descending it is 5, 5, 3.
- First tower takes height 5.
- Second tower: minimum of its bound 5 and 5 - 1 = 4 gives 4.
- Third tower: minimum of its bound 3 and 4 - 1 = 3 gives 3.
- All heights are positive and distinct, and 5 + 4 + 3 = 12 matches the expected output of 12.
Time and space
Time O(n log n) · Space O(1). With n towers the sort dominates and the subsequent scan is linear; sorting in place needs only constant extra memory beyond the sort's own stack.
Interview pitfalls
- Sorting ascending and assigning from the smallest bound upward, which does not naturally guarantee distinctness or maximality.
- Forgetting the positivity check, so an input like [1,1] produces heights 1 and 0 and a bogus sum instead of -1.
- Overflow: up to 10^5 towers with heights near 10^9 sum to about 10^14, beyond 32 bits.
- Returning the partial sum computed before discovering the impossibility instead of -1.
- Mishandling duplicates by thinking equal bounds are impossible; they are fine as long as the chain of previous minus one stays positive.
Follow-up questions interviewers ask
- What if heights only need to be distinct within groups of towers rather than globally?
- How would you report the actual assignment in the original input order?
- If each tower also had a minimum height, how would you check feasibility and still maximize the sum?
Further reading on the technique: Greedy algorithm
Related LeetCode Problems
Practice more problems similar to Maximize the Total Height of Unique Towers.
Review your practice with PhantomCodeAI
After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.