5
\$\begingroup\$

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.

\$\endgroup\$
10
  • 5
    \$\begingroup\$ "My code works in the linear time since". "arr.sort()" does not run in linear time, so your code is not linear. \$\endgroup\$
    – Peilonrayz
    Jul 29 '21 at 11:45
  • 1
    \$\begingroup\$ Timsort is \$O(n\sqrt{n})\$ your loop is \$O(n)\$. \$O(n\sqrt{n} + n) = O(n(\sqrt{n} + 1)) = O(n\sqrt{n})\$. \$\endgroup\$
    – Peilonrayz
    Jul 29 '21 at 12:35
  • 1
    \$\begingroup\$ Sorry, Timsort is \$O(n \log n)\$ not \$O(n\sqrt{n})\$ however the math and conclusion are roughly the same. \$\endgroup\$
    – Peilonrayz
    Jul 29 '21 at 12:56
  • 1
    \$\begingroup\$ What is the expected output for arr [3, 3, 6]? You could get there by one increment (arr[1] += 1 -> 4) and one decrement (arr[2] -= 1 -> 5). Is the expected output 0, because one increment and one decrement "cancel each other out"? Or 2 (1 increment of value 1, plus 1 decrement of value 1)? Or perhaps (1, 1), indicating the sum of all required increments is 1, and the sum of all required decrements is also 1? \$\endgroup\$ Jul 29 '21 at 13:18
  • 2
    \$\begingroup\$ Please do not edit the question, especially the code, after an answer has been posted. Changing the question may cause answer invalidation. Everyone needs to be able to see what the reviewer was referring to. What to do after the question has been answered. \$\endgroup\$
    – pacmaninbw
    Jul 30 '21 at 12:37
8
\$\begingroup\$

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)
\$\endgroup\$
7
  • \$\begingroup\$ Hello Kelly, thank you for your valuable input. I have just learned a new concept thanks to you. I could not fully comprehend how this module unpacks elements in the array for the lambda function. The lambda function works on two elements (prev, curr), but the elements in the array are integers, not tuples. I could not find anything about this. My wild guess is: if the function is operator.add, it fetches 0 and the first element at the beginning, and in the rest, previous element and the current element. If the function is mul, it fetches 1 and the first element at the beginning and so on. \$\endgroup\$
    – bbasaran
    Jul 30 '21 at 10:47
  • \$\begingroup\$ I don't know why, but the first algorithm works slightly faster (by 40 ms difference on average). \$\endgroup\$
    – bbasaran
    Jul 30 '21 at 11:12
  • \$\begingroup\$ @bbasaran Not quite. First prev is the first element, not 0 or 1. \$\endgroup\$ Jul 30 '21 at 12:05
  • \$\begingroup\$ What is the first curr then? It cannot be the first element as well, because when I tried this: accumulate([1,3,5], lambda prev, curr: prev+curr), it returns [1, 4, 9], not [2, 4, 9]. \$\endgroup\$
    – bbasaran
    Jul 30 '21 at 12:56
  • \$\begingroup\$ The second element. Try for example accumulate([1,3,5], print). \$\endgroup\$ Jul 30 '21 at 13:11
7
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ I totally agree with your comment about sorting. Probably Timsort would be the most optimal one. Actually, my intention is to change the algorithm for better performance. In this version, all elements should be shifted. However, it could be written in a more efficient way (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. Do you have any idea about this? Thanks! \$\endgroup\$
    – bbasaran
    Jul 29 '21 at 21:07
  • 2
    \$\begingroup\$ Doing that is probably not going to be faster. Finding something in a sorted set is \$O(\log n)\$, or if you want to make it \$O(1)\$ to find the next free integer, it's probably going to be at least \$O(\log n)\$ extra work per element visited so far to maintain the necessary information to do that. It might be an interesting question for the Computer Science site. \$\endgroup\$
    – G. Sliepen
    Jul 29 '21 at 21:35
  • \$\begingroup\$ Radix sort works only if the set of integers is bounded. In Python, there is no such bound on integers. But even if we limit input to 32-bit or 64-bit unsigned integers, I'm sceptical that an optimized radix sort would be faster (in wall time) than an optimized Timsort. Any benchmarks (in any programming language) to share? \$\endgroup\$
    – pts
    Jul 30 '21 at 15:47
  • 1
    \$\begingroup\$ @bbasaran Maybe we could use union-find, with streaks of consecutive numbers being the components, and an extra dict mapping values to their streaks so that for a value x, you can look up existing streaks that include x-1, x or x+1 (in order to find the "edges" connecting the nodes/streaks).. Then unite overlapping/touching streaks. Could be O(nα(n)), i.e., practically O(n). \$\endgroup\$ Jul 30 '21 at 17:45
  • 1
    \$\begingroup\$ They use sum twice, so process the input array four times. I wonder how fast these four times are. Even for large inputs, I can imagine the sort being faster than their loop part (and sum probably be fastest). I.e., the sort already not being the problem here. \$\endgroup\$ Jul 30 '21 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.