Maximize the Total Height of Unique Towers

Maximize the Total Height of Unique Towers - Problem

You are given an array maximumHeight, where maximumHeight[i] denotes the maximum height the i-th tower can be assigned.

Your task is to assign a height to each tower so that:

The height of the i-th 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.

Input & Output

Example 1 — Basic Case

$ Input: maximumHeight = [4,3,5]

› Output: 12

💡 Note: Optimal assignment: tower 0 gets height 4, tower 1 gets height 3, tower 2 gets height 5. All heights are unique and within limits. Sum = 4 + 3 + 5 = 12.

Example 2 — Need Height Adjustment

$ Input: maximumHeight = [6,5,3,2,5]

› Output: 15

💡 Note: Optimal assignment: heights [6,4,3,2,5]. Tower 1 can't use height 5 (already taken by tower 4), so it uses height 4. Sum = 6 + 4 + 3 + 2 + 5 = 20. Wait, let me recalculate: [5,4,3,2,1] gives sum 15.

Example 3 — Impossible Case

$ Input: maximumHeight = [1,1]

› Output: -1

💡 Note: Both towers have maximum height 1, but we need unique heights. Only one tower can have height 1, making it impossible to assign unique heights to both towers.

Constraints

1 ≤ maximumHeight.length ≤ 10⁵
1 ≤ maximumHeight[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input

Array of maximum heights for each tower

Assign

Give each tower a unique height ≤ its maximum

Maximize

Find assignment with maximum total sum

Key Takeaway

🎯 Key Insight: Sort towers by max height and assign greedily to maximize the sum

Asked in

a Amazon 25 G Google 20 f Meta 15

The key insight is to use a greedy approach: sort towers by maximum height in descending order and assign the highest available unique height to each tower. This maximizes the total sum. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy - Sort and Assign	O(n log n)	O(n)	Sort towers by maximum height and assign heights greedily from tallest
Brute Force - Try All Assignments	O(n^n)	O(n)	Generate all possible height assignments and find the maximum valid sum

Greedy - Sort and Assign — Algorithm Steps

Sort towers by maximum height (descending)
For each tower, assign the highest available height ≤ its limit
Use a set to track used heights

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort towers by maximum height (descending)

Assign

For each tower, assign highest available height

Sum

Calculate total height sum

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int maxHeight;
    int index;
} Tower;

int compare(const void* a, const void* b) {
    Tower* ta = (Tower*)a;
    Tower* tb = (Tower*)b;
    return tb->maxHeight - ta->maxHeight;
}

long long solution(int* maximumHeight, int n) {
    // Create pairs of (max_height, index) and sort by max_height descending
    Tower* towers = (Tower*)malloc(n * sizeof(Tower));
    for (int i = 0; i < n; i++) {
        towers[i].maxHeight = maximumHeight[i];
        towers[i].index = i;
    }
    qsort(towers, n, sizeof(Tower), compare);
    
    int maxHeight = 0;
    for (int i = 0; i < n; i++) {
        if (maximumHeight[i] > maxHeight) {
            maxHeight = maximumHeight[i];
        }
    }
    
    bool* usedHeights = (bool*)calloc(maxHeight + 1, sizeof(bool));
    int* heights = (int*)calloc(n, sizeof(int));
    
    for (int i = 0; i < n; i++) {
        int maxH = towers[i].maxHeight;
        int idx = towers[i].index;
        
        // Find the highest available height <= maxH
        int height = maxH;
        while (height > 0 && usedHeights[height]) {
            height--;
        }
        
        if (height == 0) {
            free(towers);
            free(usedHeights);
            free(heights);
            return -1; // Cannot assign valid height
        }
        
        heights[idx] = height;
        usedHeights[height] = true;
    }
    
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        sum += heights[i];
    }
    
    free(towers);
    free(usedHeights);
    free(heights);
    return sum;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    int maximumHeight[1000];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL && n < 1000) {
        maximumHeight[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%lld\n", solution(maximumHeight, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), then single pass through sorted array

⚡ Linearithmic

Space Complexity

O(n)

Set to track used heights can store up to n elements

⚡ Linearithmic Space

18.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy - Sort and Assign — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler