Given an array of integers, return the minimum required increment to make each element unique

Question

The task is:

Given an array of integers, return the minimum required increment to make each element unique.

Sample Input 1: [3, 4, 2, 2, 6]

Sample Output 1: 3 (One of the 2s should be incremented to 5)

Sample Input 2: [3, 4, 5]

Sample Output 2: 0 (There is no duplicate)

My code works by shifting all numbers even if there is only one duplicate in a whole array. I guess this could be written more efficiently (e.g., in each duplicate, looking at the minimum number that does not exist in the array and shifting one of the duplicates to that number), but I couldn't manage it.

def getMinimumCoins(arr):
  sumBefore = sum(arr)
  arr.sort()

  previous = arr[0]

  for i in range(1, len(arr)):
    if arr[i] <= previous:
      arr[i] = previous + 1
    
    previous = arr[i]

  return sum(arr) - sumBefore

Besides, in the way I proposed above, decremental operations also could be possible. I mean, in my code, if the input is [3,3,3], the resulting array would be [3,4,5] with total increment equals 3. However, in the new algorithm, it could be possible to obtain a resulting array of [1,2,3] with a total decrement equals to -3.

Answer 1

The algorithm is good, but...

• Use a better function name than getMinimumCoins. The task isn't about coins.
• Python prefers snake_case and four-space indentation.
• If the list is empty, you crash instead of returning zero.
• No need to actually perform the increments in the array, and itertools.accumulate can help:

from itertools import accumulate

def minimum_increments(arr):
    arr.sort()
    return sum(accumulate(arr, lambda prev, curr: max(prev + 1, curr))) - sum(arr)

Answer 2

As already mentioned by Peilonrayz, your algorithm's time complexity is \$\mathcal{O}(n\log{n})\$, because of sort(). You also process the input array three times: once to sort, once to increment elements as necessary to ensure there are duplicates, and once to calculate how much you incremented. To get the best performance, you want to have a sorting function that is better than sort(), and use as few loops over the input as possible to get the answer.

Since the input is an array of integers, you can use radix sort to sort the input in \$\mathcal{O}(n)\$ time. Then you should be able to loop over the the result and increment where necessary, and keep track of how much you incremented at the same time.

A big caveat is that a better time complexity does not guarantee better performance unless your input is very large. Python's built-in sort() is highly optimized and implemented in C, so up to a certain size of the input it might still be faster than an \$\mathcal{O}(n)\$ implementation you wrote in pure Python.