Maximize the Total Height of Unique Towers
MedPrompt
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
ithtower is a positive integer and does not exceedmaximumHeight[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 <= 1051 <= maximumHeight[i] <= 109
Approaches
2 approaches with complexity analysis and trade-offs.
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.
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
HashSetusedHeightsto store assigned heights and atotalSumto 0. - Iterate through the sorted towers:
- For the current tower with
maxH, find the largest integerhsuch that1 <= h <= maxHandhis not inusedHeights. - This is done by a linear scan, starting from
maxHand decrementing until an unused height is found. - If no such positive
hexists, return -1. - Otherwise, add
htousedHeightsand tototalSum.
- For the current tower with
- Return
totalSum.
Walkthrough
The algorithm works as follows:
- To implement the greedy strategy of prioritizing towers with higher
maximumHeight, we first need to sort the towers. Since we must respect themaximumHeightconstraint for each specific tower, we cannot simply sort themaximumHeightarray. Instead, we can create pairs of(maximumHeight, original_index)and sort these pairs. - We sort these pairs in descending order based on the
maximumHeightvalue. - We use a
HashSetcalledusedHeightsto 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. - We initialize
totalSum = 0. - We iterate through our sorted towers. For each tower:
- We retrieve its
maximumHeight. - We start a search for an available height
h, beginning from itsmaximumHeightand decrementing downwards. - In a loop, we check if
his inusedHeights. If it is, we decrementhand check again. We continue this until we find anhthat is not used, orhbecomes 0. - If the loop terminates because
his 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 tousedHeightsand add its value tototalSum.
- We retrieve its
- If we successfully assign a height to every tower, the final
totalSumis the answer.
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; }}Complexity
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.
Trade-offs
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.
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.
Algorithm
- Create a list from the
maximumHeightarray. - Sort this list in descending order.
- Initialize
totalSum = 0andavailableHeight = infinity.availableHeightwill 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 ish = min(maxH, availableHeight - 1). - If
his not positive, return -1. - Add
htototalSum. - Update
availableHeight = hto ensure the next assigned height is strictly smaller.
- For the current
- Return
totalSum.
Walkthrough
The key insight is that we don't need to track which specific heights are used. By processing the maximumHeights 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:
- First, we sort the
maximumHeightarray 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. - We initialize a
totalSumto 0 and a variable, let's call itavailableHeight, to a very large number. ThisavailableHeightwill represent the upper bound for the height we can assign, which gets updated after each assignment. - We iterate through the sorted
maximumHeights. For eachcurrentMaxH:- The height we can assign,
h, must be unique and at mostcurrentMaxH. Since we are processing in descending order ofmaximumHeightand assigning the largest possible values, the heighthmust also be strictly less than the height assigned to the previous tower. Thus,his the minimum ofcurrentMaxHandavailableHeight - 1. - If the calculated
his 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
hto ourtotalSum. - We then update
availableHeight = hfor the next iteration, enforcing the uniqueness constraint.
- The height we can assign,
- After the loop finishes,
totalSumholds the maximum possible total height.
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; }}Complexity
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.
Trade-offs
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.
Solutions
Solution
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; }}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; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.