We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize the Total Height of Unique Towers

Number: 3510

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given an array maximumHeight where maximumHeight[i] represents the maximum height that the iᵗʰ tower can be assigned, assign a unique positive integer height to each tower (not exceeding its maximum) such that the total sum of the assigned heights is maximized. If it is not possible to assign such heights, return -1.

Key Insights

  • To maximize the total height, try to assign each tower the highest possible height within its limit.
  • The heights must be unique. After assigning one tower a height, subsequent towers must have strictly lower assigned heights.
  • Sorting the maximum heights in descending order helps in greedily assigning the maximum valid unique height.
  • If at any step the allowable height becomes less than 1, the assignment is impossible and -1 should be returned.

Space and Time Complexity

Time Complexity: O(n log n) due to the sorting operation. Space Complexity: O(n), needed for the sorted array (or O(1) if sorting in-place).

Solution

The idea is to sort the maximumHeight array in descending order. Initialize the current maximum possible height to a very large value. For each tower in the sorted array, the tower's assigned height is the minimum of its maximum height and the current maximum height allowed (which is one less than the previous assigned height). If the computed height is less than 1, then it is impossible to assign valid heights and return -1. Otherwise, add the assigned height to the total sum and update the current maximum allowed height.

Code Solutions

# Python solution with line-by-line comments

def maximizeTowerHeight(maximumHeight):
    # Sort the maximum heights in descending order
    maximumHeight.sort(reverse=True)
    
    total_sum = 0
    # Initialize allowed_max as a very large number
    allowed_max = float('inf')
    
    # Iterate through each tower's maximum height
    for height in maximumHeight:
        # The current tower's assigned height is the minimum between its maximum and the allowed max
        assigned = min(height, allowed_max - 1)
        # If the assigned height falls below 1, assignment is impossible
        if assigned < 1:
            return -1
        total_sum += assigned
        allowed_max = assigned  # Update the allowed maximum for the next tower
    
    return total_sum

# Example usage:
print(maximizeTowerHeight([2,3,4,3]))  # Expected output: 10
← Back to All Questions