# Maximize the Total Height of Unique Towers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/maximize-the-total-height-of-unique-towers)
Canonical: https://scaleengineer.com/dsa/problems/maximize-the-total-height-of-unique-towers
**Patterns:** [Greedy](https://scaleengineer.com/dsa/patterns/greedy)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## Problem
You are given an array `maximumHeight`, where `maximumHeight[i]` denotes the **maximum** height the `ith` tower can be assigned.

Your task is to assign a height to each tower so that:

1. The height of the `ith` tower is a positive integer and does not exceed `maximumHeight[i]`.
2. No two towers have the same height.

Return the **maximum** possible total sum of the tower heights. If it's not possible to assign heights, return `-1`.

**Example 1:**

**Input:** maximumHeight \= \[2,3,4,3\]

**Output:** 10

**Explanation:**

We can assign heights in the following way: `[1, 2, 4, 3]`.

**Example 2:**

**Input:** maximumHeight \= \[15,10\]

**Output:** 25

**Explanation:**

We can assign heights in the following way: `[15, 10]`.

**Example 3:**

**Input:** maximumHeight \= \[2,2,1\]

**Output:** \-1

**Explanation:**

It's impossible to assign positive heights to each index so that no two towers have the same height.

**Constraints:**

* `1 <= maximumHeight.length <= 105`
* `1 <= maximumHeight[i] <= 109`

# Approaches
## Greedy Approach with Linear Scan
This approach is based on a greedy strategy. To maximize the total sum of heights, we should try to assign the largest possible heights to the towers. The towers with a higher `maximumHeight` have more flexibility in choosing a large height. Therefore, it's a good greedy heuristic to prioritize towers with higher `maximumHeight`. We process towers in descending order of their `maximumHeight`. For each tower, we assign it the largest possible height that is less than or equal to its `maximumHeight` and has not been assigned to any previous tower. The search for an available height is done by a simple linear scan downwards.
**Time:** O(N^2) in the worst case. Sorting takes O(N log N). The main loop runs N times, and the inner `while` loop for finding an available height can run up to N times in the worst-case scenario (e.g., an input with many identical `maximumHeight` values). This makes the overall complexity dominated by the nested search, resulting in O(N^2). · **Space:** O(N), where N is the number of towers. This is for storing the pairs for sorting and the `usedHeights` set.
**Pros:** The logic is straightforward and follows a natural greedy intuition.; It is guaranteed to find the correct answer.
**Cons:** The time complexity of O(N^2) is too slow for the given constraints (N <= 10^5), which will result in a 'Time Limit Exceeded' error on larger test cases.
### Explanation
The algorithm works as follows:
1.  To implement the greedy strategy of prioritizing towers with higher `maximumHeight`, we first need to sort the towers. Since we must respect the `maximumHeight` constraint for each specific tower, we cannot simply sort the `maximumHeight` array. Instead, we can create pairs of `(maximumHeight, original_index)` and sort these pairs.
2.  We sort these pairs in descending order based on the `maximumHeight` value.
3.  We use a `HashSet` called `usedHeights` to keep track of which heights have already been assigned to a tower. This allows for an average O(1) time complexity for checking if a height is taken.
4.  We initialize `totalSum = 0`.
5.  We iterate through our sorted towers. For each tower:
    *   We retrieve its `maximumHeight`.
    *   We start a search for an available height `h`, beginning from its `maximumHeight` and decrementing downwards.
    *   In a loop, we check if `h` is in `usedHeights`. If it is, we decrement `h` and check again. We continue this until we find an `h` that is not used, or `h` becomes 0.
    *   If the loop terminates because `h` is 0, it means we couldn't find any positive unique height for this tower, making a valid assignment impossible. We return -1.
    *   If we find a valid `h > 0`, we add it to `usedHeights` and add its value to `totalSum`.
6.  If we successfully assign a height to every tower, the final `totalSum` is the answer.

```java
import java.util.*;

class Solution {
    public long maximumTotalHeight(int[] maximumHeight) {
        int n = maximumHeight.length;
        // Create pairs of (maxHeight, original_index) to sort
        int[][] towers = new int[n][2];
        for (int i = 0; i < n; i++) {
            towers[i][0] = maximumHeight[i];
            towers[i][1] = i;
        }

        // Sort towers by maxHeight in descending order
        Arrays.sort(towers, (a, b) -> Integer.compare(b[0], a[0]));

        Set<Integer> usedHeights = new HashSet<>();
        long totalSum = 0;

        for (int[] tower : towers) {
            int maxH = tower[0];
            int h = maxH;
            // Linearly scan for the largest available height
            while (h > 0 && usedHeights.contains(h)) {
                h--;
            }

            if (h == 0) {
                // No positive unique height can be assigned
                return -1;
            }

            usedHeights.add(h);
            totalSum += h;
        }

        return totalSum;
    }
}
```
### Algorithm
- Create pairs of `(maximumHeight[i], i)` to keep track of original towers after sorting.
- Sort these pairs in descending order based on `maximumHeight`.
- Initialize a `HashSet` `usedHeights` to store assigned heights and a `totalSum` to 0.
- Iterate through the sorted towers:
  - For the current tower with `maxH`, find the largest integer `h` such that `1 <= h <= maxH` and `h` is not in `usedHeights`.
  - This is done by a linear scan, starting from `maxH` and decrementing until an unused height is found.
  - If no such positive `h` exists, return -1.
  - Otherwise, add `h` to `usedHeights` and to `totalSum`.
- Return `totalSum`.

## Optimized Greedy Approach with Sorting
This approach improves upon the naive greedy strategy by eliminating the costly linear scan for the next available height. The core idea remains the same: prioritize towers with higher `maximumHeight`. However, we can observe a crucial pattern. If we sort the `maximumHeight` values in descending order, the height we assign to the `i`-th tower in this sorted list will be at most the height assigned to the `(i-1)`-th tower minus one. This is because the `(i-1)`-th tower (with a higher or equal `maximumHeight`) has already taken the best possible slot, so the `i`-th tower must take a strictly smaller one to maintain uniqueness. This observation allows us to find the height for each tower in O(1) time after the initial sort.
**Time:** O(N log N). The dominant operation is sorting the `maximumHeight` array. The subsequent loop to calculate the sum runs in O(N) time. · **Space:** O(N) or O(log N), depending on the sort implementation. If we create a copy of the array to sort, it's O(N). An in-place sort would use O(log N) for recursion stack space.
**Pros:** Highly efficient with a time complexity of O(N log N), which is optimal due to the sorting requirement.; The implementation is simpler and more concise than other efficient alternatives like using a Disjoint Set Union (DSU) data structure.
**Cons:** The proof of correctness is non-trivial and relies on concepts from matching theory, which might not be immediately obvious.
### Explanation
The key insight is that we don't need to track which specific heights are used. By processing the `maximumHeight`s in descending order, we can determine the optimal height for the current tower based only on the height assigned to the previous one.

The algorithm proceeds as follows:
1.  First, we sort the `maximumHeight` array in descending order. It turns out we don't need to track the original indices. A valid assignment of the generated heights to the original towers is always possible if one exists.
2.  We initialize a `totalSum` to 0 and a variable, let's call it `availableHeight`, to a very large number. This `availableHeight` will represent the upper bound for the height we can assign, which gets updated after each assignment.
3.  We iterate through the sorted `maximumHeight`s. For each `currentMaxH`:
    *   The height we can assign, `h`, must be unique and at most `currentMaxH`. Since we are processing in descending order of `maximumHeight` and assigning the largest possible values, the height `h` must also be strictly less than the height assigned to the previous tower. Thus, `h` is the minimum of `currentMaxH` and `availableHeight - 1`.
    *   If the calculated `h` is not positive (i.e., `h <= 0`), it's impossible to assign a valid height, so we conclude that no solution exists and return -1.
    *   Otherwise, we add `h` to our `totalSum`.
    *   We then update `availableHeight = h` for the next iteration, enforcing the uniqueness constraint.
4.  After the loop finishes, `totalSum` holds the maximum possible total height.

```java
import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public long maximumTotalHeight(int[] maximumHeight) {
        int n = maximumHeight.length;
        // Create a list from the array to sort it.
        List<Integer> sortedMaxHeight = new ArrayList<>();
        for (int h : maximumHeight) {
            sortedMaxHeight.add(h);
        }
        // Sort in descending order.
        Collections.sort(sortedMaxHeight, Collections.reverseOrder());

        long totalSum = 0;
        // This represents the maximum possible height we can assign,
        // which is one less than the previously assigned height.
        long availableHeight = Long.MAX_VALUE; 

        for (int maxH : sortedMaxHeight) {
            // The height to assign is limited by the tower's max height
            // and must be less than the previously assigned height.
            long heightToAssign = Math.min((long)maxH, availableHeight - 1);
            
            // Height must be positive.
            if (heightToAssign <= 0) {
                return -1;
            }
            
            totalSum += heightToAssign;
            // For the next tower, the height must be less than the current one.
            availableHeight = heightToAssign;
        }

        return totalSum;
    }
}
```
### Algorithm
- Create a list from the `maximumHeight` array.
- Sort this list in descending order.
- Initialize `totalSum = 0` and `availableHeight = infinity`. `availableHeight` will track the upper bound for the next assignment.
- Iterate through the sorted list of maximum heights (`m`):
  - For the current `maxH`, the height to assign is `h = min(maxH, availableHeight - 1)`.
  - If `h` is not positive, return -1.
  - Add `h` to `totalSum`.
  - Update `availableHeight = h` to ensure the next assigned height is strictly smaller.
- Return `totalSum`.

# Solutions
### Java

```java
class Solution {
public
  long maximumTotalSum(int[] maximumHeight) {
    long ans = 0;
    int mx = 1 << 30;
    Arrays.sort(maximumHeight);
    for (int i = maximumHeight.length - 1; i >= 0; --i) {
      int x = Math.min(maximumHeight[i], mx - 1);
      if (x <= 0) {
        return -1;
      }
      ans += x;
      mx = x;
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long maximumTotalSum(vector<int> &maximumHeight) {
    ranges ::sort(maximumHeight, greater<int>());
    long long ans = 0;
    int mx = 1 << 30;
    for (int x : maximumHeight) {
      x = min(x, mx - 1);
      if (x <= 0) {
        return -1;
      }
      ans += x;
      mx = x;
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def maximumTotalSum(self, maximumHeight: List[int]) -> int: maximumHeight . sort() ans, mx = 0, inf for x in maximumHeight[:: - 1]: x = min(x, mx - 1) if x <= 0: return - 1 ans += x mx = x return ans

```