Maximize the total height of unique towers

Array Greedy Sorting

37.3% acceptance

Feb 23, 2026

129

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 ith 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.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn maximum_total_sum(maximum_height: Vec<i32>) -> i64 {
    let mut sorted = maximum_height.clone();
    sorted.sort_unstable_by(|a, b| b.cmp(a)); // descending
    let mut total: i64 = sorted[0] as i64;
    let mut prev = sorted[0] as i64;
    for i in 1..sorted.len() {
      let h = (prev - 1).min(sorted[i] as i64);
      if h <= 0 { return -1; }
      total += h;
      prev = h;
    }
    total
  }
}