Can this (find + sort) problem be solved in O(n)?

Question

I went thru this problem on geeksforgeeks.com and while my solution managed to pass all test cases, I actually used .sort() so I know it doesn't fit the Expected Time Complexity of O(n): I mean we all know no sorting algorithm works on O(n), not even the best implementation of Timsort (which is what Python uses). So I went to check the website's Answer/Solution and found this:

def printRepeating(arr, n):

# First check all the
    # values that are
# present in an array
    # then go to that
# values as indexes
    # and increment by
# the size of array
for i in range(0, n):
    index = arr[i] % n
    arr[index] += n

# Now check which value
    # exists more
# than once by dividing
    # with the size
# of array
for i in range(0, n):
    if (arr[i]/n) >= 2:
        print(i, end=" ")

I tried to follow the logic behind that algorithm but honestly couldn't, so I tested different datasets until I found that it failed for some. For instance:

arr = [5, 6, 3, 1, 3, 6, 6, 0, 0, 11, 11, 1, 1, 50, 50]

Output: 0 1 3 5 6 11 13 14

Notice that:

Number 5 IS NOT repeated in the array,
Numbers 13 and 14 are not even present in the array, and
Number 50 is both, present and repeated, and the solution won't show it.

I already reported the problem to the website, I just wanted to know if, since these problems are supposed to be curated, there is a solution in O(n). My best guess is there isn't unless you can somehow insert every repeated number in O(1) within the mapping of all keys/values.

user_1405065 · Answer

The reason the code doesn't work with your example data set is that you're violating one of the constraints that is given in the problem. The input array (of length n) is supposed to only contain values from 0 to n-1. Your values of 50 are too big (since you have 15 elements in your list). That constraint is why adding n to the existing values doesn't break things. You have a less-than-n original value (that can be extracted with arr[i] % n), and the count (that can be extracted with arr[i] // n). The two values are stacked on top of each other, cleverly reusing the existing array with no extra space needed.

user_234593 · Answer

The problem can be solved with dict().

And for Python here: https://docs.python.org/3.10/library/stdtypes.html#mapping-types-dict

It's an abstract data type that accesses in amortized O(1), which as you've mentioned, is exactly what you need.

Python stdlib also has collections.Counter, which is a specialization of dict that accomplishes 90% of what the problem asks for.

edit

Oh, the results have to be sorted too. Looks like they want you to use a list() "as a dict", mapping integers to their number of occurrences via their own value as an index.

Can this (find + sort) problem be solved in O(n)?

2 Answers