Minimum Increment to Make Array Unique LeetCode solution in Java

1
class Solution {
2
  public int minIncrementForUnique(int[] nums) {
3

4
    // Approach - 1 : Using a Count array
5

6
    // TC : O(N)
7
    // SC : O(N)
8

9
    int max = 0;
10
    for (int i : nums) max = Math.max(max, i);
11

12
    int count[] = new int[nums.length + max];
13

14
    for (int c : nums) count[c]++;
15

16
    int answer = 0, choosen = 0;
17
    int len = count.length;
18

19
    for (int i = 0; i < len; i++) {
20
      if (count[i] >= 2) {
21
        choosen += count[i] - 1;
22
        answer -= i * (count[i] - 1);
23
      } else if (choosen > 0 && count[i] == 0) {
24
        answer += i;
25
        choosen--;
26
      }
27
    }
28

29
    return answer;
30

31
    // Approach - 2:
32

33
    // TC : O(nlogn)
34
    // SC : O(1)
35

36
    Arrays.sort(nums);
37
    int answer = 0;
38
    for (int i = 1; i < nums.length; i++) {
39
      if (nums[i - 1] >= nums[i]) {
40
        answer += nums[i - 1] - nums[i] + 1;
41
        nums[i] = nums[i - 1] + 1;
42
      }
43
    }
44
    return answer;
45
  }
46
}