Problem Summary

You are given an integer array nums.
In one operation, you may increment or decrement any element by exactly 1.

Your task is to compute the minimum number of operations required to make all elements in the array distinct.

Example
Input:

nums = [1,2,2]

Output:

1

Explanation: You can change the last 2 to 3 using 1 operation, resulting in [1,2,3].

Another example
Input:

nums = [3,2,1,2,1,7]

Output:

6

Explanation: Make the array [1,2,3,4,5,7] or another distinct arrangement.

Constraints

• 1 ≤ nums.length ≤ 10⁵
• Values can be negative or positive
• Operations cost is linear distance moved (±1 per step)

---

Key Insight

This is a variant of “make array unique” except increments and decrements both cost 1 per unit.

The classic solution is:

1. Sort the array
2. Ensure each value is strictly greater than the previous one
3. Move values upward when needed

Why This Works

Because numbers can shift both ways, but sorting ensures:

• The optimal arrangement for uniqueness is non-decreasing without gaps on the left.
• If a number equals or is less than or equal to the previous unique value, you must increase it.

We never decrease after sorting because decreasing would cause collisions with previous numbers.

This is proven minimal because:

• Any decrease would push it toward earlier elements and risk additional corrections.
• Adjusting forward (increasing) maintains sorted order and yields minimum total movement.

---

Approach (Simple English)

1. Sort the array.
2. Track a variable last, the last assigned distinct value.
3. For each number:
   • If it is greater than last, keep it as is.
   • If it is less than or equal to last, then:
     • Increase it to last + 1
     • Add (last + 1) - nums[i] to the cost
   • Update last accordingly.

This ensures strictly increasing values with minimal increment operations.

---

Java Code (Optimal O(n log n) Solution)

import java.util.Arrays;

class Solution {
    public long minimumOperations(int[] nums) {

        Arrays.sort(nums);

        long operations = 0;
        long last = Long.MIN_VALUE;

        for (int num : nums) {
            if (num > last) {
                last = num;
            } else {
                long newValue = last + 1;
                operations += newValue - num;
                last = newValue;
            }
        }

        return operations;
    }
}

Notes:

• Use long because operations can grow large.
• Sorting is required to ensure minimal adjustment.

---

Dry Run

Input:

nums = [3,2,1,2,1,7]

Sorted:

[1,1,2,2,3,7]

Initialize:

last = -∞
operations = 0

1. First 1: last < 1 → keep
   last = 1
2. Second 1: <= last
   new = last + 1 = 2
   operations += (2 – 1) = 1
   last = 2
3. First 2: <= last
   new = 3
   operations += (3 – 2) = 1
   last = 3
4. Second 2: <= last
   new = 4
   operations += (4 – 2) = 2
   last = 4
5. 3: <= last
   new = 5
   operations += (5 – 3) = 2
   last = 5
6. 7: > last
   keep
   last = 7

Total operations = 1 + 1 + 2 + 2 = 6

---

Complexity Analysis

Time:
O(n log n) for sorting

Space:
O(1) extra space (sorting done in-place)

---

Edge Cases

• Already unique → 0 operations
• All identical numbers → cost is arithmetic series
• Negative numbers → handled naturally by sorting
• Large values → requires long for safe accumulation