Minimum number of increment (by 1) operations to make elements of an array unique

Reading time: 35 minutes | Coding time: 10 minutes

We are given a sorted array (if not, then sort it using any sorting algorithm or built in functions) which might have duplicate elements, our task is to find the minimum number of increment (by 1) operations needed to make the elements of an array unique.

Example : Consider a sorted array - x [1,2,4,4,4,5].
i=0 : x[i] = 1 (Unique)
i=1 : x[i] = 2 (Unique)
i=2 : x[i] = 4 (Unique)
i=3 : x[i] = 4 (increment once to get 5) => res = 1
i=4 : x[i] = 4 (increment twice to get 6) => res = 3
i=5 : x[i] = 5 (increment twice to get 7) => res = 5
=> 5 increment operations are required to make this array unique.

We have explored two approaches:

• Method 1: 2 pointers O(N^2) time
• Method 2: Using hashmap O(N) time

Method 1

Concept:

Start from the first index. We maintain 2 variables (prev and curr) which keep track of 2 consecutive elements in the array. These 2 pointers traverse the entire array. If both of them are equal, it means that we have encountered a duplicate set.

In this case we increment the element pointed by the second variable (curr) and also increment count. We do this exercise iteratively for each element until all the elements are rendered unique.

Algorithm

Step 1:Initialize prev,curr,count to zero.Start traversing the array from index 0.
Step 2:For each element run another loop through the entire array.
Step 3:For the inner loop initialize prev to arr[j] and curr to arr[j+1] till j<n-1.
Step 4:If prev == curr, increment curr,count.Go to step 3.
Step 5:Once the inner loop terminates for an element,sort the array, go to step 2 until i<n.
Step 6:Return count.

Implementation

import java.util.*;
static int unique(int arr[],int n)
{
    int prev,curr,count=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<n-1;j++)
        {
            prev = arr[j];
            curr = arr[j+1]
            if(prev == curr)
            {
                curr++;
                count++;
            }
        }
        Arrays.sort(arr);
    }
    return count;
}

public static void main(String args[])
{
    int arr[] = {2,2,2,3,6,6,8};
    System.out.println(unique(arr,arr.length));
}

Output

6

Example:

Let us consider a sorted array arr[] = {2,2,2,3,6,6,8}
Following is a dry run of the above mentioned algorithm for the array input:
n = 7,count = 0

arr[ ] =	2	2	2	3	6	6	8
i = 0	2	3	2	3	6	7	8
i = 1	2	3	3	4	6	7	8
i = 2	2	3	4	5	6	7	8

i = 0 :
j = 0 : prev = 2,curr = 2 => (prev == curr) increment curr to 3,increment count to 1
j = 1 : prev = 3,curr = 2
j = 2 : prev = 2,curr = 3
j = 3 : prev = 3,curr = 6
j = 4 : prev = 6,curr = 6 => (prev == curr) increment curr to 7,increment count to 2
j = 5 : prev = 7,curr = 8
Sort => arr[]={2,2,3,3,6,7,8}

i = 1:
j = 0 : prev = 2,curr = 2 => (prev == curr) increment curr to 3,increment count to 3
j = 1 : prev = 3,curr = 3 => (prev == curr) increment curr to 4,increment count to 4
j = 2 : prev = 4,curr = 3
j = 3 : prev = 3,curr = 6
j = 4 : prev = 6,curr = 7
j = 5 : prev = 7,curr = 8
Sort => arr[] = {2,3,3,4,6,7,8}

i=2:
j = 0 : prev = 2,curr = 3
j = 1 : prev = 3,curr = 3 => (prev == curr) increment curr to 4,increment count to 5
j = 2 : prev = 4,curr = 4 => (prev == curr) increment curr to 5,increment count to 6
j = 3 : prev = 5,curr = 6
j = 4 : prev = 6,curr = 7
j = 5 : prev = 7,curr = 8

count = 6
We stop iterating here as the elements have become unique.Of course, this will not happen when the program runs.

Time Complexity : O(n^2)

The first and the most trivial hint for the time complexity can be gathered from the fact that this algorithm has 2 for loops.
Another way of looking at it is to see that for each element, we traverse the entire array.We perform a simple comparison if a condition is met, which is a O(1) operation.Hence, we iterate over the algorithm in O(N^2) time.

Space Comlexity : O(1)

This approach uses constant space as it does not vary with input size.

Method 2:

Concept

This approach is implemented using a hashmap. We first traverse the array and put all the elements into the hashmap, updating the number of occurences of the elements while doing so.

After this step is completed, we traverse the array again and check each element. We use a variable adjust which keeps track of the no. of increments needed for each duplicate set.

As we encounter a duplicate element in the array we initialize adjust to that number and subtract the value of the array element from adjust. If this value comes out to be greater than (or equal) to 0 we add the it to count. If it is negative we do not add it to count. We increment the value of adjust and move on the next element. If the next element has the same value or is a non duplicate element we repeat the process of finding the difference of the element and adjust variable and if it is greater than 1,add it to count otherwise not.This is to be continued until another duplicate element is encountered. When this happens(i.e another duplicate element is encountered) we reinitailize the adjust variable to the new duplicate element and find the difference between the adjust and the array element.Increment the adjust variable by one and move to the next element. We keep on repeating the process until we reach the end of the array.

Now, we simply return count.

Algorithm

Step 1: Insert all the elements into the hashmap along with their number of occurences.Initialize adjust,count to zero.
Step 2: Now,start traversing the array again and check the hashmap to know whether the element is unique or not.
Step 3:If the element is unique and simply check if adjust - arr[i] is greater than zero.If it is then add it to count.
Step 4:If the element is not unique,reintialize adjust to that element and continue ahead.Go to Step 3.
Step 5:Once you reach the end of the array,return count.

Implementation

import java.util.*;

static int uniqueElements(int arr[],int n)
{
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<n;i++)
{
    if(!map.containsKey(arr[i]))
        map.put(arr[i] , 1);
    else
        map.put(arr[i] , map.get(arr[i]) + 1);
}
//we now have a hashmap which contains all the elements with the number of occurences for each element
int i = 0,count = 0;
int adjust = 0;
while(i < n)
{
    if(map.get(arr[i]) > 1) //If the element is not unique
    {
        adjust = arr[i];
        for(int j = i;j < i+map.get(arr[i]);j++)
        {
            if((adjust - arr[j]) > 0)
                count = count + adjust - arr[j];
            adjust++;
        }
    }
    else   //If the element is unique
    {
         if((adjust - arr[i]) > 0)
                count = count + adjust - arr[i];
    }
    i = i + map.get(arr[i])-1;
}
return count;
}

public static void main(String args[])
{
    int arr[] = {3,3,7,8,8,8,12};
    System.out.println(uniqueElements(arr,arr.length));
}

Output

4

Example

Let us consider a sorted array arr[] = {3,3,7,8,8,8,12},count = 0,adjust = 0
Following is the dry run for this algorithm with the input array :

arr[ ] =	3	3	7	8	8	8	12
adjust =	3	4	5	8	9	10	11
adjust - arr[ i ] =	0	1	-2	0	1	2	-1
count =	0	1	1	1	1	2	4

i = 0 :
arr[0] = 3 is not unique, hence initialize adjust to 3, calculate difference (adjust - arr[0], add to count if it is greater than 0), increment adjust, adjust = 4
i = 1:
arr[1] = 3 (part of the duplicate set), adjust - arr[1] = 4 - 3 = 1 , 1 > 0, add to count, count = 1, increment adjust, adjust = 5
i = 2:
arr[2] = 7 which is unique, therefore simply check if adjust - arr[2] is greater than 0, 5 - 7 = -2 ,as -2 < 0, don't add to count
i = 3 :
arr[3] = 8 which is not unique, hence initialize adjust to 8, calculate difference(adjust - arr[3]) 8 - 8 = 0, increment adjust, adjust = 9
i = 4 :
arr[4] = 8 (part of duplicate set), adjust - arr[4] = 9 - 8 = 1, 1 > 0, add to count, count = 2, increment adjust, adjust = 10
i = 5 :
arr[5] = 8 (part of duplicate set), adjust - arr[5] = 10 - 8 = 2, 2 > 0, add to count, count = 4, increment adjust, adjust = 11
i = 6 :
arr[6] = 12 which is unique, calculate adjust - arr[6] = 11 - 12 = -1, -1 < 0, don't add to count

Time Complexity : O(n)

This algorithm runs in O(n) time as we propagate the number of increments through the entire array while traversing it just once.This is done using the adjust variable which keeps sum count of the number of operations needed to make a duplicate set unique as well as the number of increment operations that will be reqiured to accomodate this unique set such that no other element later in the array becomes duplicate.

Space Complexity : O(n)

This algorithm uses O(n) extra space that is associated with the hashmap.