LeetCode Unique Towers Problem: Complete Solution

The Unique Towers problem on LeetCode is a neat greedy challenge that looks simple at first but rewards careful thinking. You are given an array where each value represents the maximum allowed height of a tower. Your task is to choose a positive height for every tower so that all chosen heights are unique, no tower exceeds its maximum, and the total height is as large as possible.

TLDR: Sort the maximum heights in descending order, then greedily assign each tower the largest valid height that is smaller than the previously assigned height. If at any point the assigned height becomes less than 1, no valid construction exists, so return -1. Otherwise, add all assigned heights and return the maximum possible sum.

Understanding the Problem

Imagine you are designing a skyline. Each tower has a construction limit: tower i cannot be taller than maximumHeight[i]. However, the city has a strange rule: no two towers may have the same height. Among all possible valid skylines, you want the one with the greatest total height.

Formally, given an integer array maximumHeight, choose an array height such that:

• 1 <= height[i] <= maximumHeight[i]
• All values in height are distinct
• The sum of all height[i] values is maximized

If it is impossible to choose valid positive unique heights for all towers, return -1.

Example Walkthrough

Consider the input:

maximumHeight = [2, 3, 4, 3]

One valid assignment is:

height = [2, 3, 4, 1]

All heights are positive and unique, and no tower exceeds its limit. The total is:

2 + 3 + 4 + 1 = 10

Could we do better? After sorting the maximum heights in descending order, we get:

[4, 3, 3, 2]

Now assign greedily:

• First tower: assign 4
• Second tower: assign 3
• Third tower: cannot assign 3 again, so assign 2
• Fourth tower: cannot assign 2, so assign 1

The result is:

4 + 3 + 2 + 1 = 10

So the maximum total height is 10.

The Key Observation

The main difficulty is preventing duplicate heights while keeping the total sum as large as possible. A natural thought is: if a tower can be tall, we should try to make it tall. But we also need to leave room for the remaining towers to have different positive heights.

The best strategy is to process towers from the largest maximum height to the smallest. Why? Because towers with larger limits are more flexible. They can be assigned many possible heights. Smaller towers have fewer choices, so we must be careful not to waste small available values too early.

After sorting in descending order, we keep track of the largest height we are still allowed to use. For the first tower, that value can be its maximum height. For every next tower, its height must be:

• No greater than its own maximum height
• Strictly smaller than the previously assigned height

Therefore, the assigned height is:

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

If currentHeight becomes 0 or negative, we cannot build all towers with positive unique heights.

Why the Greedy Approach Works

The greedy approach works because at every step we assign the largest possible height that does not break uniqueness. This choice is optimal: making the current tower smaller than necessary would never help increase the total sum. It would only reduce the answer and still leave the same or fewer useful height options for future towers.

Sorting descending gives us a clean structure. Since we process bigger limits first, each new tower only needs to be smaller than the previous assigned height. This automatically guarantees uniqueness because the assigned sequence becomes strictly decreasing.

For example, suppose after sorting we have:

[7, 7, 6, 5]

The greedy assignment is:

7, 6, 5, 4

This is clearly better than something like:

7, 5, 4, 3

The second assignment is valid, but it unnecessarily reduces the second tower. Since the goal is to maximize the sum, we should always keep each tower as tall as possible while preserving uniqueness.

Algorithm Steps

1. Sort maximumHeight in descending order.
2. Initialize previousHeight to a very large number, or simply use the first sorted value.
3. For each maximum height:
   • Choose currentHeight = min(maxHeight, previousHeight - 1).
   • If currentHeight <= 0, return -1.
   • Add currentHeight to the answer.
   • Update previousHeight = currentHeight.
4. Return the final sum.

JavaScript Solution

function maximumTotalSum(maximumHeight) {
  maximumHeight.sort((a, b) => b - a);

  let total = 0;
  let previousHeight = Infinity;

  for (const maxHeight of maximumHeight) {
    const currentHeight = Math.min(maxHeight, previousHeight - 1);

    if (currentHeight <= 0) {
      return -1;
    }

    total += currentHeight;
    previousHeight = currentHeight;
  }

  return total;
}

This implementation is short, readable, and efficient. The variable previousHeight ensures that every new tower is strictly shorter than the one before it.

Python Solution

class Solution:
    def maximumTotalSum(self, maximumHeight):
        maximumHeight.sort(reverse=True)

        total = 0
        previous_height = float("inf")

        for max_height in maximumHeight:
            current_height = min(max_height, previous_height - 1)

            if current_height <= 0:
                return -1

            total += current_height
            previous_height = current_height

        return total

The Python version follows exactly the same logic. Sorting in reverse order lets us greedily build a strictly decreasing sequence of tower heights.

Complexity Analysis

The time complexity is dominated by sorting:

• Time Complexity: O(n log n), where n is the number of towers.
• Space Complexity: O(1) extra space if sorting is done in place, not counting language-specific sorting overhead.

The loop itself is only O(n), so the solution is efficient even for large inputs.

Common Mistakes

One common mistake is to sort in ascending order. That makes the greedy logic harder and may lead to poor choices because small maximum heights get assigned before flexible tall towers. Another mistake is only checking for duplicate maximum values. The actual assigned heights may differ from the maximum values, so uniqueness must be enforced during assignment.

Also, remember that tower heights must be positive. A height of 0 is not allowed. If the greedy process reaches zero, the correct answer is -1.

Final Thoughts

The Unique Towers problem is a classic example of how sorting can unlock a simple greedy strategy. By arranging the towers from the largest maximum height to the smallest, we can assign each tower the tallest possible unique height without reconsidering earlier choices. The result is an elegant solution that is easy to implement and efficient enough for competitive programming constraints.

If you remember one idea, remember this: sort descending, then keep each chosen height just below the previous one while staying within its limit. That single rule gives you the complete solution.