# Minimum Increments to make all array elements unique

Given a sorted array of integers, Write an algorithm to make all array elements distinct or unique by doing minimum increments.

Example:

```Given Input: [2, 2, 3, 5, 6, 6]
Unique Array: [2, 3, 4, 5, 6, 7], Minimum Increments: 3
Explanation:
Increment 2 to 3, 3 to 4 and 6 to 7.

Given Input: [1, 1, 1, 1]
Unique Array: [1, 2, 3, 4], Minimum Increments: 3
```

Approach:

Brute Force: Use nested loops and compare each element to the rest of the elements and increment.

Time Complexity: O(n^2)

Better Solution – O(N)

• Initialize previous = input[0].
• minIncrements = 0.
• Iterate the array from 1 to last element, for each element input[i]
• If input[i] <= pervious
• Copy input[i] into temp
• Copy the previous to input[i].
• Increment input[i] by 1.
• Increment minIncrements by temp-input[i].
• previous = input[i].
• Return minIncrements.

Walk-through

```Input = [1, 1, 1, 1]

previous = 1
Rest of the input = [1, 1, 1]
minIncrements = 0

i=1
input[i] <= pervious (1<=1)
temp = input[i] = 1,
Copy the previous to input[1] so input[1] = 1
Increment input[1] by 1=> input[1] = 2
minIncrements = minIncrements + (input[i]-temp) => 0+(2-1) = 1
previous = input[1] = 2

i=2
input[i] <= pervious (1<=2)
temp = input[i] = 1,
Copy the previous to input[1] so input[2] = 2
Increment input[2] by 1=> input[2] = 3
minIncrements = minIncrements + (input[i]-temp) => 1+(3-1) = 1 + 2 = 3
previous = input[2] = 3

i=3
input[i] <= pervious (1<=3)
temp = input[i] = 1,
Copy the previous to input[3] so input[3] = 3
Increment input[3] by 1=> input[3] = 4
minIncrements = minIncrements + (input[i]-temp) => 3+(4-1) = 3 + 3 = 6
previous = input[3] = 4

Modified Array = [1, 2, 3, 4]
Minimum increments required : 6
```

Complete Code:

Output:

```Given Input: [1, 1, 3, 3]
Unique Array: [1, 2, 3, 4], Minimum Increments: 2
```

This site uses Akismet to reduce spam. Learn how your comment data is processed.