3301. Maximize the Total Height of Unique Towers LeetCode Solution

In this guide, you will get 3301. Maximize the Total Height of Unique Towers LeetCode Solution with the best time and space complexity. The solution to Maximize the Total Height of Unique Towers problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Maximize the Total Height of Unique Towers solution in C++
4. Maximize the Total Height of Unique Towers solution in Java
5. Maximize the Total Height of Unique Towers solution in Python
6. Additional Resources

Problem Statement of Maximize the Total Height of Unique Towers

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:

The height of the ith tower is a positive integer and does not exceed maximumHeight[i].
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

Complexity Analysis

• Time Complexity: O(\texttt{sort})
• Space Complexity: O(\texttt{sort})

3301. Maximize the Total Height of Unique Towers LeetCode Solution in C++

class Solution {
 public:
  long long maximumTotalSum(vector<int>& maximumHeight) {
    long ans = 0;
    int mn = INT_MAX;

    ranges::sort(maximumHeight, greater<>());

    for (const int height : maximumHeight) {
      const int assigned = min(height, mn - 1);
      if (assigned == 0)
        return -1;
      ans += assigned;
      mn = assigned;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3301. Maximize the Total Height of Unique Towers LeetCode Solution in Java

class Solution {
  public long maximumTotalSum(int[] maximumHeight) {
    long ans = 0;
    int mn = Integer.MAX_VALUE;

    Arrays.sort(maximumHeight);

    for (int i = maximumHeight.length - 1; i >= 0; --i) {
      final int assigned = Math.min(maximumHeight[i], mn - 1);
      if (assigned == 0)
        return -1;
      ans += assigned;
      mn = assigned;
    }

    return ans;
  }
}
// code provided by PROGIEZ

3301. Maximize the Total Height of Unique Towers LeetCode Solution in Python

class Solution:
  def maximumTotalSum(self, maximumHeight: list[int]) -> int:
    ans = 0
    mn = math.inf

    for height in sorted(maximumHeight, reverse=True):
      assigned = min(height, mn - 1)
      if assigned == 0:
        return -1
      ans += assigned
      mn = assigned

    return ans
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.