Make array elements unique

JavaView on GFG

Problem Overview

Minimum increment operations to make all array elements distinct.

Intuition

Minimum increment operations to make all array elements distinct. Sort then fix conflicts.

Algorithm

1Sort array. If arr[i] <= arr[i-1]: set arr[i] = arr[i-1]+1, count the difference as operations.

Common Pitfalls

• Same as LC 945. Sort, then greedily increment. O(n log n). Track total increments applied.

Make array elements unique.java

Java

// Approach: Sort array. Ensure each element is strictly greater than previous by incrementing and counting moves.
// Time: O(n log n) Space: O(1)
class Solution {
    public int minIncrements(int[] arr) {
        Arrays.sort(arr);

        HashSet<Integer> set = new HashSet<>();

        int sum = 0, max = 0;

        for (int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max);

            if (set.contains(arr[i])) {
                sum += max + 1 - arr[i];
                max++;
                set.add(max);
            } else
                set.add(arr[i]);
        }

        return sum;
    }
}

Was this solution helpful?