Minimum Operations to Make Array Elements Unique

Problem Make all array elements unique using only increments (+1 per operation), minimizing the total number of increments.

Input / Output

• Input: int array nums. Output: minimum total increments.

Constraints

• n up to 10^5; O(n log n) expected.

Example

• [3,2,1,2,1,7] → 6 (e.g. [3,4,1,2,5,7]); [1,2,2] → 1.

Expected approach

• Sort; sweep keeping needed = max(prev + 1, nums[i]); cost += needed − nums[i]; prev = needed. Sorting makes the greedy exchange-safe: raising the smaller duplicate first is never worse. O(n log n)/O(1). Counting-based O(n + range) alternative if values are bounded. The union-find "next free slot" technique handles the unsorted-streaming variant — bonus points.