This post is completed by 3 users

  • 0
 Add to List
Medium

528. 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

Output:

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

Related Problems: