3301. Maximize the Total Height of Unique Towers
Explanation
To maximize the total height of unique towers, we need to assign heights to each tower such that the height of the ith tower is a positive integer and does not exceed maximumHeight[i], and no two towers have the same height. We can achieve this by sorting the maximumHeight array in descending order and then assigning heights starting from 1 to the maximum height allowed for each tower. If at any point we find that the maximum height for a tower is less than the current height we are trying to assign, we return -1 as it is not possible to assign unique heights in this scenario.
- Sort the
maximumHeightarray in descending order. - Iterate over the sorted array and assign heights from 1 upwards to each tower, making sure that the assigned height does not exceed the maximum height allowed.
- If at any point we find that the maximum height for a tower is less than the current height we are trying to assign, return -1.
- Calculate and return the total sum of tower heights.
Time complexity: O(n log n) where n is the number of elements in the maximumHeight array due to sorting.
Space complexity: O(1) as we are using constant extra space.
import java.util.Arrays;
class Solution {
public int maximizeTowerHeights(int[] maximumHeight) {
Arrays.sort(maximumHeight);
int n = maximumHeight.length;
int totalHeight = 0;
for (int i = 0; i < n; i++) {
int height = Math.min(i + 1, maximumHeight[i]);
if (height < i + 1) {
return -1;
}
totalHeight += height;
}
return totalHeight;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.