Tejav
#3301

Maximize the Total Height of Unique Towers

Medium
ArrayGreedySortingGreedySorting
LeetCode ↗

Approaches

Brute ForceOptimal
Complexity Comparison
Brute ForceOptimal Solution★
Time
O(n²)
O(n log n)
Space
O(1)
O(1)
💡

Intuition

Time O(n log n)Space O(1)

The optimal approach sorts the maximum heights in descending order and assigns the highest possible unique heights while ensuring no two towers have the same height. This is efficient and straightforward.

⚙️

Algorithm

4 steps
  1. 1Step 1: Sort the maximumHeight array in descending order.
  2. 2Step 2: Initialize a variable to keep track of the last assigned height.
  3. 3Step 3: Iterate through the sorted array and assign heights starting from the maximum allowed, ensuring uniqueness by decrementing if necessary.
  4. 4Step 4: If at any point the assigned height is less than 1, return -1.
solution.py13 lines
1# Full working Python code
2
3def maxTowerHeight(maximumHeight):
4    maximumHeight.sort(reverse=True)
5    total_height = 0
6    last_height = float('inf')
7    for height in maximumHeight:
8        assigned_height = min(height, last_height - 1)
9        if assigned_height <= 0:
10            return -1
11        total_height += assigned_height
12        last_height = assigned_height
13    return total_height
ℹ

Complexity note: The time complexity is O(n log n) due to the sorting step, while the iteration through the array is O(n). The space complexity is O(1) since we are using a constant amount of extra space.

  • 1Sorting helps in efficiently assigning unique heights.
  • 2Always check for uniqueness while assigning heights to avoid conflicts.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.