Maximize the Total Height of Unique Towers - Video Solutions

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.