945. Minimum Increment to Make Array Unique

T: O(max)

S: O(max)

class Solution {
    public int minIncrementForUnique(int[] nums) {
        int max = 0;
        for (int num : nums) {
            max = Math.max(max, num);
        }

        int[] bucket = new int[max+1];
        for (int num : nums) {
            bucket[num]++;
        }
        int result = 0;
        for (int i = 0; i < max+1; i++) {
            if (i == max && bucket[i] > 1) {
                int x = 1;
                for (int j = 0; j < bucket[i]-1; j++) {
                    result += x;
                    x++;
                }
                break;
            }
            while (bucket[i] > 1) {
                result++;
                bucket[i+1]++;
                bucket[i]--;
            }
        }
        return result;
    }
}
/***
my new idea is to use bucket sort (count it)
then simulate the "unique process"
-> ex:
1 2 2 3

1 2 3   num 
1 2 1   count  
so make it to unique would be 1 2 3 4
  so this 2 -> move to 3
  then 3's count = 2 -> move to 4
  -> so total move is 2
  so this is for moving to next bucket and add result,
  also minus itselft
            while (bucket[i] > 1) {
                result++;
                bucket[i+1]++; // moving count to next bucket and
                bucket[i]--;
            }

but in last number, we don't have bigger buckets to calculate and simulate it
so just calcualte it directly
ex:
1 2 3 4 number
1 1 1 3 count -> there are 2 need to move to 5 and 6
1 to 5 (1 move)
1 to 6 (2 move, because this need to move to 5 first then to 6, so its 2 moves)
so means in the last number, if its count is 3 -> means there are 2 more count -> has 1 + 2 moves -> so ans is 3 (1+2) 

-> if there are 3 more count -> means 1+2+3 moves

            if (i == max && bucket[i] > 1) {
                int x = 1;
                for (int j = 0; j < bucket[i]-1; j++) {
                    result += x;
                    x++;
                }
                break;
            }


 */