Maximize the Total Height of Unique Towers solution and explanation
9 more videos on this problem
Maximize the Total Height of Unique Towers || LeetCode Biweekly Contest 140 || Leetcode Solutioncodi · 0:39 · 1K views
3301. Maximize the Total Height of Unique Towers (Leetcode Medium)Programming Live with Larry · 7:53 · 364 views
Leetcode Biweekly Contest 140 | 3301. Maximize the Total Height of Unique Towers | C++ SolutionCodeFod · 6:53 · 364 views
Q2. Maximize the Total Height of Unique Towers || Leetcode solutions || Biweekly 140 ||CPPFrustrated_Muthyams🤡 · 2:37 · 329 views
Leetcode 3301 | Maximize the Total Height of Unique Towers | Biweekly Contest 140Road To FAANG · 9:19 · 232 views
Biweekly 140 Leetcode | Maximize the Total Height of Unique Towers | Explanationak tiwari · 16:30 · 213 views
3301. Maximize the Total Height of Unique Towers || Biweekly Contest 140 Solutionog_prakash · 5:35 · 125 views
LeetCode 3301: Maximize the Total Height of Unique Towers | Biweekly Contest 140 | C++ SolutionDebugAndDeploy · 6:37 · 102 views
Maximize the Total Height of Unique Towers || LeetCode Biweekly Contest 140 || DCC NITADCC NITA · 6:25 · 91 views
3301 Maximize the Total Height of Unique TowersCodeCracker · 8:01 · 74 views
The 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:
- 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
Approach overview
Problem Overview: You receive an array where maxHeights[i] represents the maximum allowed height of the i-th tower. You must assign each tower a positive integer height that does not exceed its limit, while ensuring every tower height is unique. The goal is to maximize the total sum of all chosen heights.
The main challenge is maintaining uniqueness without wasting large height values. If you greedily assign heights without considering conflicts, duplicates appear quickly and reduce the achievable total. The optimal strategy carefully distributes the largest valid heights first.
Approach 1: Greedy with Sorting (O(n log n) time, O(1) extra space)
Sort the array in descending order so the tower with the highest limit is processed first. Track the largest height that can still be used, initially set to the first tower's maximum. For each tower, assign min(maxHeights[i], previousHeight - 1). This guarantees uniqueness because each next tower must be strictly smaller than the previous assigned height.
If the computed height becomes <= 0, a valid configuration is impossible because all remaining towers would require non‑positive heights. Otherwise, add the assigned value to the running total and continue scanning the sorted array. Sorting ensures that large limits get priority, which maximizes the final sum. This greedy ordering works because decreasing earlier towers would only reduce the achievable total later.
This solution primarily uses operations on a sorted array combined with a classic greedy decision: always take the largest valid height available. The sorting step dominates the complexity, giving O(n log n) time and O(1) extra space if sorting in place.
Approach 2: Max Heap Simulation (O(n log n) time, O(n) space)
Another approach uses a max heap to repeatedly pick the tower with the largest remaining allowed height. Push all limits into a max heap. Each step pops the current maximum height and compares it with the previously assigned height to maintain uniqueness.
If the popped value would duplicate the previous height, reduce it to previousHeight - 1. If the adjusted value becomes non‑positive, the configuration cannot satisfy the constraints. Otherwise add it to the total and update the previous height tracker. The heap keeps the next largest candidate available at every step.
This method is conceptually straightforward because the heap naturally gives the largest available limit at each iteration. However, the extra heap operations add overhead compared to simply sorting once. The time complexity remains O(n log n) due to heap insertions and removals, with O(n) auxiliary space.
Recommended for interviews: The greedy sorting approach is the expected solution. It demonstrates recognition of a decreasing sequence constraint and the ability to enforce uniqueness using a simple invariant (nextHeight < previousHeight). Discussing why sorting first maximizes the total shows strong reasoning. Mentioning the heap variant shows awareness of alternative implementations, but the sorted greedy method is cleaner and typically preferred.
Approach 1: Greedy Approach with Sorting
In this approach, we first sort the maximumHeight array in descending order. We attempt to assign heights starting from the largest possible unique value, decrementing if necessary, to ensure all assigned heights are unique.
If it becomes impossible to assign a unique height to any tower (i.e., when the required height becomes zero), we return -1. Otherwise, we compute the total sum of the assigned heights.
def maximize_heights(maximum_height):
maximum_height.sort(reverse=True)
max_height = maximum_height[0]
total_height = 0
for height in maximum_height:
if max_height > height:
max_height = height
if max_height == 0:
return -1
total_height += max_height
max_height -= 1
return total_height
maximum_height = [2, 3, 4, 3]
print(maximize_heights(maximum_height))import java.util.Arrays;
public class MaximizeHeights {
public static int maximizeHeights(int[] maximumHeight) {
Arrays.sort(maximumHeight);
int maxHeight = maximumHeight[maximumHeight.length - 1];
int totalHeight = 0;
for (int i = maximumHeight.length - 1; i >= 0; i--) {
if (maxHeight > maximumHeight[i]) {
maxHeight = maximumHeight[i];
}
if (maxHeight == 0) {
return -1;
}
totalHeight += maxHeight;
maxHeight--;
}
return totalHeight;
}
public static void main(String[] args) {
int[] maximumHeight = {2, 3, 4, 3};
System.out.println(maximizeHeights(maximumHeight));
}
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maximizeHeights(vector<int>& maximumHeight) {
sort(maximumHeight.begin(), maximumHeight.end(), greater<int>());
int maxHeight = maximumHeight[0];
int totalHeight = 0;
for (int height: maximumHeight) {
if (maxHeight > height) {
maxHeight = height;
}
if (maxHeight == 0) {
return -1;
}
totalHeight += maxHeight;
maxHeight--;
}
return totalHeight;
}
int main() {
vector<int> maximumHeight = {2, 3, 4, 3};
cout << maximizeHeights(maximumHeight) << endl;
return 0;
}function maximizeHeights(maximumHeight) {
maximumHeight.sort((a, b) => b - a);
let maxHeight = maximumHeight[0];
let totalHeight = 0;
for (const height of maximumHeight) {
if (maxHeight > height) {
maxHeight = height;
}
if (maxHeight === 0) {
return -1;
}
totalHeight += maxHeight;
maxHeight--;
}
return totalHeight;
}
const maximumHeight = [2, 3, 4, 3];
console.log(maximizeHeights(maximumHeight));#include <stdio.h>
#include <stdlib.h>
int cmp(const void *a, const void *b) {
return (*(int *)b - *(int *)a);
}
int maximizeHeights(int *maximumHeight, int n) {
qsort(maximumHeight, n, sizeof(int), cmp);
int maxHeight = maximumHeight[0];
int usedHeight = 0;
int totalHeight = 0;
for (int i = 0; i < n; i++) {
if (maxHeight > maximumHeight[i]) {
maxHeight = maximumHeight[i];
}
if (maxHeight <= usedHeight) {
return -1;
}
totalHeight += maxHeight;
usedHeight = maxHeight;
maxHeight--;
}
return totalHeight;
}
int main() {
int maximumHeight[] = {2, 3, 4, 3};
int n = sizeof(maximumHeight) / sizeof(maximumHeight[0]);
int result = maximizeHeights(maximumHeight, n);
printf("%d\n", result);
return 0;
}using System;
public class Program
{
public static int MaximizeHeights(int[] maximumHeight)
{
Array.Sort(maximumHeight);
int maxHeight = maximumHeight[maximumHeight.Length - 1];
int totalHeight = 0;
for (int i = maximumHeight.Length - 1; i >= 0; i--)
{
if (maxHeight > maximumHeight[i])
{
maxHeight = maximumHeight[i];
}
if (maxHeight == 0)
{
return -1;
}
totalHeight += maxHeight;
maxHeight--;
}
return totalHeight;
}
public static void Main()
{
int[] maximumHeight = { 2, 3, 4, 3 };
Console.WriteLine(MaximizeHeights(maximumHeight));
}
}In this Python function, the list is sorted in reverse to efficiently pick from the top allowed maximum heights and reduce them gradually. We keep track of the maximum height wearable at each step, checking for a unique allocation possibility.
Time Complexity: O(n log n) for sorting operation.
Space Complexity: O(1) as we iterate and process in place.
Approach 2: Max Heap Approach
This approach uses a max heap (or priority queue) to efficiently determine the next maximum available height to assign. We initially insert all the heights into a max heap.
By repeatedly extracting the maximum and assigning it if valid (and decreasing for unique assignments), we ensure the solution handles the large input size well by using the heap's properties.
import heapq
def maximize_heights(maximum_height):
maximum_height = [-x for x in maximum_height]
heapq.heapify(maximum_height)
max_height = -maximum_height[0]
total_height = 0
while maximum_height:
current_max = -heapq.heappop(maximum_height)
if max_height > current_max:
max_height = current_max
if max_height == 0:
return -1
total_height += max_height
max_height -= 1
return total_height
maximum_height = [2, 3, 4, 3]
print(maximize_heights(maximum_height))import java.util.PriorityQueue;
import java.util.Collections;
public class MaximizeHeightsHeap {
public static int maximizeHeights(int[] maximumHeight) {
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
for (int height : maximumHeight) {
maxHeap.offer(height);
}
int expectedHeight = maxHeap.peek();
int totalHeight = 0;
while (!maxHeap.isEmpty()) {
int currentMax = maxHeap.poll();
if (expectedHeight > currentMax) {
expectedHeight = currentMax;
}
if (expectedHeight <= 0) {
return -1;
}
totalHeight += expectedHeight;
expectedHeight--;
}
return totalHeight;
}
public static void main(String[] args) {
int[] maximumHeight = {2, 3, 4, 3};
System.out.println(maximizeHeights(maximumHeight));
}
}class MaxHeap {
constructor() {
this.heap = [];
}
insert(num) {
this.heap.push(num);
this.bubbleUp();
}
bubbleUp() {
let index = this.heap.length - 1;
while (index > 0) {
let element = this.heap[index];
let parentIndex = Math.floor((index - 1) / 2);
let parent = this.heap[parentIndex];
if (parent >= element) break;
this.heap[index] = parent;
this.heap[parentIndex] = element;
index = parentIndex;
}
}
extractMax() {
const max = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this.sinkDown(0);
}
return max;
}
sinkDown(index) {
const length = this.heap.length;
const element = this.heap[index];
while (true) {
let leftChildIdx = 2 * index + 1;
let rightChildIdx = 2 * index + 2;
let leftChild, rightChild;
let swap = null;
if (leftChildIdx < length) {
leftChild = this.heap[leftChildIdx];
if (leftChild > element) {
swap = leftChildIdx;
}
}
if (rightChildIdx < length) {
rightChild = this.heap[rightChildIdx];
if (
(swap === null && rightChild > element) ||
(swap !== null && rightChild > leftChild)
) {
swap = rightChildIdx;
}
}
if (swap === null) break;
this.heap[index] = this.heap[swap];
this.heap[swap] = element;
index = swap;
}
}
}
function maximizeHeights(maxMaximumHeight) {
const heap = new MaxHeap();
for (const height of maxMaximumHeight) {
heap.insert(height);
}
let maxHeight = heap.extractMax();
let totalHeight = 0;
while (heap.heap.length > 0) {
const currentMax = heap.extractMax();
if (maxHeight > currentMax) {
maxHeight = currentMax;
}
if (maxHeight === 0) {
return -1;
}
totalHeight += maxHeight;
maxHeight--;
}
totalHeight += maxHeight; // Add the last extracted value
return totalHeight;
}
const maxMaximumHeight = [2, 3, 4, 3];
console.log(maximizeHeights(maxMaximumHeight));This Python implementation utilizes a heap to facilitate the dynamic selection of max available heights by initially negating the heights (for max-heap behavior) and using the built-in min heap. The process ensures efficient constraint application with each iteration.
Time Complexity: O(n log n) due to heap operations.
Space Complexity: O(n), proportional to heap's size during process execution.
Approach 3: Sorting + Greedy
We can sort the maximum heights of the towers in descending order, then allocate the heights one by one starting from the maximum height. Use a variable mx to record the current maximum allocated height.
If the current height x is greater than mx - 1, update x to mx - 1. If x is less than or equal to 0, it means the height cannot be allocated, and we directly return -1. Otherwise, we add x to the answer and update mx to x.
Finally, return the answer.
The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the length of the array maximumHeight.
function maximumTotalSum(maximumHeight: number[]): number {
maximumHeight.sort((a, b) => a - b).reverse();
let ans: number = 0;
let mx: number = Infinity;
for (let x of maximumHeight) {
x = Math.min(x, mx - 1);
if (x <= 0) {
return -1;
}
ans += x;
mx = x;
}
return ans;
}func maximumTotalSum(maximumHeight []int) int64 {
slices.SortFunc(maximumHeight, func(a, b int) int { return b - a })
ans := int64(0)
mx := 1 << 30
for _, x := range maximumHeight {
x = min(x, mx-1)
if x <= 0 {
return -1
}
ans += int64(x)
mx = x
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Greedy Approach with Sorting | Time Complexity: O(n log n) for sorting operation. |
| Max Heap Approach | Time Complexity: O(n log n) due to heap operations. |
| Sorting + Greedy | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Sorting | O(n log n) | O(1) | Best general solution. Simple logic and minimal memory usage. |
| Max Heap Simulation | O(n log n) | O(n) | Useful when processing dynamically or when largest values must be retrieved repeatedly. |
Frequently asked questions
Is Maximize the Total Height of Unique Towers easy or hard?
Maximize the Total Height of Unique Towers is classified as a medium difficulty problem. The challenge lies in recognizing the greedy pattern that enforces strictly decreasing heights after sorting. Once that insight is clear, the implementation becomes a straightforward O(n log n) algorithm.
Maximize the Total Height of Unique Towers Python/Java solution
In Python or Java, the common implementation sorts the array in descending order and iterates once to assign heights using min(maxHeight[i], prev - 1). The algorithm maintains a variable tracking the last assigned height and accumulates the total sum. FleetCode provides implementations in Python, Java, C++, C, C#, and JavaScript.
How to solve Maximize the Total Height of Unique Towers in O(n)?
A strict O(n) solution is generally not feasible because the tower limits are unsorted and the greedy strategy relies on processing the largest limits first. Sorting the array ensures the highest constraints are handled earlier, which is necessary for maximizing the total height. The resulting optimal complexity is O(n log n).
What is the best approach for Maximize the Total Height of Unique Towers?
The best approach sorts the maximum heights in descending order and greedily assigns each tower the largest possible unique value. Each new tower receives min(maxHeight[i], previousHeight - 1) to maintain strictly decreasing heights. This guarantees the maximum possible sum while ensuring uniqueness. The algorithm runs in O(n log n) time due to sorting.
Is Maximize the Total Height of Unique Towers asked at Google/Amazon/Meta?
Greedy problems involving unique assignments and decreasing constraints appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often require maximizing sums while preventing duplicates or enforcing strictly decreasing values. This problem is a typical medium‑level greedy interview question.
What data structure is used in Maximize the Total Height of Unique Towers?
The primary solution uses arrays and sorting to process tower limits from largest to smallest. An alternative implementation uses a max heap (priority queue) to repeatedly extract the largest available height. Both approaches enforce uniqueness by ensuring each chosen height is strictly smaller than the previous one.
What is the time complexity of Maximize the Total Height of Unique Towers?
The optimal greedy solution runs in O(n log n) time because the array must be sorted before assigning heights. After sorting, a single linear pass assigns heights and accumulates the total. The extra space complexity is O(1) if sorting is done in place.