Skip to content

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.

Medium#3301
LeetCode Problem

Maximize the Total Height of Unique Towers

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

Input
maximumHeight = [5,5,3]
Output
12
Explanation

Assign heights 5, 4, and 3. They are distinct, within their bounds, and sum to 12.

# Example 2

Input
maximumHeight = [1,1]
Output
-1
Explanation

Both towers would need height 1, which violates uniqueness.

Constraints

1 <= maximumHeight.length <= 100000
1 <= maximumHeight[i] <= 1000000000

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

  1. Sort the maximum heights in descending order. The invariant through the scan is that all assigned heights so far are distinct and strictly decreasing.
  2. Assign the first tower its full bound.
  3. 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.
  4. 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.
  5. 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

  1. maximumHeight is [5,5,3]; sorted descending it is 5, 5, 3.
  2. First tower takes height 5.
  3. Second tower: minimum of its bound 5 and 5 - 1 = 4 gives 4.
  4. Third tower: minimum of its bound 3 and 4 - 1 = 3 gives 3.
  5. 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.