Sorting: Minimum increment to make array unique

Problem Statement:

You are given an array.

You need to choose a index and increment that value by 1.

You need to return the number of operations needed to make all the array elements unique

Example:

Input: arr = [1, 2, 2]
Output: 1

Solution 1: Using sorting

The solution is very simple.

Sort the array in ascending order.

Then check and increment accordingly

Time Complexity: O(n logn)
Space Complexity: O(1)

Solution 2: using frequency array

We will create frequency array and update how many times each element is repeated.

The we increment the element by the times the frequency to make it unique.

Time Complexity: O(n + max)
Space Complexity: O(n + max)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution_1 (vector<int>& arr) 
{
  	
  	sort(arr.begin(), arr.end());
  
  	int count = 0;
  	for (int i = 1; i < arr.size(); i++) 
    {
      
    	if (arr[i] <= arr[i-1]) 
        {

          	count += arr[i-1] + 1 - arr[i];
          	arr[i] = arr[i-1] + 1;
        }
    }
    
    return count;
}

int solution_2(vector<int>& arr) 
{
    int n = arr.size();
    int count = 0;

	int max = *max_element(arr.begin(), arr.end());
    vector<int> freq(n + max, 0);
    
    for (int ele : arr) 
        freq[ele]++;
  	
    for (int num = 0; num < freq.size(); num++) 
    {
        
        if (freq[num] > 1) 
        {
            
            freq[num + 1] += freq[num] - 1;
            
            count += freq[num] - 1;
            freq[num] = 1;
        }
    }
  
    return count;
}

int main() 
{
    vector<int> arr = {1, 2, 2};
    cout <<"Solution 1 = "<< solution_1(arr)<<endl;
    arr = {1, 2, 2};
    cout <<"Solution 2 = "<< solution_2(arr);
}

Output

Solution 1 = 1
Solution 2 = 1