945. Minimum Increment to Make Array Unique

Version #2 Sort
The current number need to be at least prev + 1

Time O(nlogn) Space O(1)
class Solution {
    public int minIncrementForUnique(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        Arrays.sort(A);
        int prev = A[0];
        int result = 0;
        for (int i = 1; i < A.length; i++) {
            // a have to be at least prev + 1
            result += Math.max(prev + 1 - A[i], 0);
            prev = Math.max(A[i], prev + 1);
        }
        return result;
    }
}


Version # 1 Counter
Time O(n) Space O(n)
class Solution {
    public int minIncrementForUnique(int[] A) {
        int[] counter = new int[50000];
        int max = 0;
        int result = 0;
        for (int a : A) {
            counter[a]++;
            max = Math.max(max, a);
        }
        int j = 0;
        for (int i = 0; i <= max; i++) {
            while (counter[i] > 1) {
                j = Math.max(j, i + 1);
                while (counter[j] > 0) {
                    j++;
                }
                counter[j] = 1;
                counter[i]--;
                result += j - i;
            }
        }
        return result;
    }
}