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.

Examples

Example 1

1
2
3
4
5
6
7
8


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

Output: 10

Explanation:

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

Example 2

1
2
3
4
5
6
7
8


Input: maximumHeight = [15,10]

Output: 25

Explanation:

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

Example 3

1
2
3
4
5
6
7
8
9


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 <= 10^5
  • 1 <= maximumHeight[i] <= 10^9

Solution

Method 1 – Greedy Assignment with Sorting

Intuition

To maximize the total height with unique heights, assign the largest possible unique heights to the towers with the largest maximum allowed heights. Sort the maximum heights, then assign the largest possible unique values from the back, ensuring no two towers have the same height and each is within its allowed maximum.

Approach

  1. Sort maximumHeight in ascending order.
  2. Start from the largest tower, assign it the largest possible height (at most its maximum and less than the previous assigned height).
  3. For each tower from right to left, assign it the minimum of its maximum and one less than the previous assigned height.
  4. If at any point the assigned height is less than 1, return -1 (not possible).
  5. Sum all assigned heights and return the result.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maxTotalHeight(vector<int>& maxH) {
        int n = maxH.size();
        sort(maxH.begin(), maxH.end());
        int prev = 1e9, ans = 0;
        for (int i = n-1; i >= 0; --i) {
            prev = min(prev-1, maxH[i]);
            if (prev < 1) return -1;
            ans += prev;
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

func maxTotalHeight(maxH []int) int {
    sort.Ints(maxH)
    n := len(maxH)
    prev, ans := int(1e9), 0
    for i := n-1; i >= 0; i-- {
        if prev-1 < maxH[i] {
            prev = maxH[i]
        } else {
            prev--
        }
        if prev < 1 {
            return -1
        }
        ans += prev
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maxTotalHeight(int[] maxH) {
        Arrays.sort(maxH);
        int n = maxH.length, prev = Integer.MAX_VALUE, ans = 0;
        for (int i = n-1; i >= 0; i--) {
            prev = Math.min(prev-1, maxH[i]);
            if (prev < 1) return -1;
            ans += prev;
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maxTotalHeight(maxH: IntArray): Int {
        maxH.sort()
        var prev = Int.MAX_VALUE
        var ans = 0
        for (i in maxH.size-1 downTo 0) {
            prev = minOf(prev-1, maxH[i])
            if (prev < 1) return -1
            ans += prev
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
    def maxTotalHeight(self, maximumHeight: list[int]) -> int:
        maximumHeight.sort()
        prev = float('inf')
        ans = 0
        for h in reversed(maximumHeight):
            prev = min(prev-1, h)
            if prev < 1:
                return -1
            ans += prev
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
    pub fn max_total_height(mut max_h: Vec<i32>) -> i32 {
        max_h.sort();
        let mut prev = i32::MAX;
        let mut ans = 0;
        for &h in max_h.iter().rev() {
            prev = prev.saturating_sub(1).min(h);
            if prev < 1 { return -1; }
            ans += prev;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxTotalHeight(maximumHeight: number[]): number {
        maximumHeight.sort((a, b) => a - b);
        let prev = Number.MAX_SAFE_INTEGER, ans = 0;
        for (let i = maximumHeight.length - 1; i >= 0; i--) {
            prev = Math.min(prev - 1, maximumHeight[i]);
            if (prev < 1) return -1;
            ans += prev;
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n) — for sorting the array.
  • 🧺 Space complexity: O(1) — only a few variables are used.