Problem

You are given an integer array nums. In one move, you can pick an index i where 0 <= i < nums.length and increment nums[i] by 1.

Return the minimum number of moves to make every value in nums unique.

The test cases are generated so that the answer fits in a 32-bit integer.

Examples

Example 1:

Input:
nums = [1,2,2]
Output:
 1
Explanation: After 1 move, the array could be [1, 2, 3].

Example 2:

Input:
nums = [3,2,1,2,1,7]
Output:
 6
Explanation: After 6 moves, the array could be [3, 4, 1, 2, 5, 7].
It can be shown with 5 or less moves that it is impossible for the array to have all unique values.

Solution

First solution that comes to mind is using hashmap to collect the duplicates, but then we can also use sorting. Here is the video explanation:

Method 1 - Using TreeMap as frequency map

One way can be to count the frequency of each number in array, as the duplicates are involved. Now, we can take following approach, (assume using [1, 1, 1, 2, 2, 3]):

  1. Count the frequencies (map = {1: 3, 2: 2, 3: 1}}
  2. Now, we start going from smallest to largest value. Lets call it num (in this case 1)
    1. For this number we get the frequency. (for eg. for 1 it is 3.). We know that we can only use one of this num, and propagate frequency - 1 it to the next numbers. (For 1 we use one 1, but 2 1s are duplicates, so we make them 2, and add them to map - see next steps)
    2. As we propagate, now we increment num + 1 frequencies by frequency - 1 as we make num unique, and deal the rest frequency - 1 in next iteration. Also, now as num is unique, remove it from map.(map = {2: 4, 3: 1})
    3. As we propagate frequency - 1 to next iteration, moves += frequency - 1. (moves = 2)
  3. Now, loop till the map is empty
  4. Return the moves

Note that we can use Hashmap as well, but there is no ordering. But we want to process next greater element to check for the duplicates, as we increment the number by 1. Hence treemap is better, as we are propagating the frequency in specific order.

Other way is we loop on 10^5 numbers as per constraint, and use hashmap, but treemap solution is more elegant.

Code

public class Solution {

	public int minIncrementForUnique(int[] nums) {
		TreeMap<Integer, Integer> map = new TreeMap<>();
		int moves = 0;

		// Count the frequency of each number.
		for (int num: nums) {
			map.put(num, map.getOrDefault(num, 0) + 1);
		}

		while (!map.isEmpty()) {
			// Remove the entry with the lowest key.
			int num = map.firstKey();
			int frequency = map.remove(num);

			// If frequency is more than 1, increment the number and add back to the map.
			if (frequency > 1) {
				map.put(num + 1, map.getOrDefault(num + 1, 0) + frequency - 1);
				moves += frequency - 1;
			}
		}

		return moves;
	}
}
Java

Complexity

  • Time: O(n log n) - For adding n elements it takes O(n log n), similarly for delete and update.
  • Space: O(n) where n is number of unique elements, in worst case all elements.

Method 2 - Using Sorting

Instead of using TreeMap, we can actually sort the array, and increment the difference we get from the previous element. That we just diff only when the array is not having unique and sorted value. The beauty of sorting is that all the duplicates come together.

Here is a dry run for that:

sorted nums = [1,1,2,2,3,3] 
nums[1] is incremented to 2 (+1)  
nums[2] is incremented to 3 (+1)  
nums[3] is incremented to 4 (+2)  
nums[4] is incremented to 5, (+2)  
nums[5] is incremented to 6, (+3)

Code

Java
class Solution {
    public int minIncrementForUnique(int[] nums) {
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 1; i < nums.length; i++) {
	        // if current element is less than or equal to prev element
            if (nums[i] <= nums[i - 1]) {
                ans += nums[i - 1] - nums[i] + 1;
                nums[i] = nums[i - 1] + 1;
            }
        }
        return ans;
    }
}

Complexity

  • Time: O(n log n)
  • Space: O(1)