Find duplicate in O(n)

Question

I am new to competitive programming, I am doing a question in that i am getting TLE as i am not finding the duplicate values in an array in O(n), with O(1) extra space.

I want to have the worst time complexity as O(n),

I came across an approach given on geeks for geeks:

def printRepeating(arr, size): 
      
    print("The repeating elements are: ") 
      
    for i in range(0, size): 
          
        if arr[abs(arr[i])] >= 0: 
            arr[abs(arr[i])] = -arr[abs(arr[i])] 
        else: 
            print (abs(arr[i]), end = " ")

But what if an element in the array is greater than the size of the array? Something like [10, 20, 10], isn't it an index out of bounds error? How can modify it to get result for all the conditions?

But brother, if I do like that, for every value in the array I have to check against each value in the set. So it will be O(n^2) if all the values are distinct. — Asim, Jul 08 '20 at 05:48
Are you sure there isn't a precondition for the input that says `abs(arr[i]) < arr.len()`? — Ken Y-N, Jul 08 '20 at 05:58
@Asim https://stackoverflow.com/questions/2831212/python-sets-vs-lists — Alexei Levenkov, Jul 08 '20 at 05:59
But the worst time complexity of using set is O(n), geeksforgeeks.org/internal-working-of-set-in-python/…. . I tried with set, its giving TLE so stop giving the same answer again and again. — Asim, Jul 08 '20 at 06:04
That code only works if all the values in the initial list are positive, but less than the length of the list. By the pigeonhole principle, that would actually *require* there to be at least one duplicate. To work for more general inputs, you'd need a different algorithm. — Blckknght, Jul 08 '20 at 06:06
Thanks Blckknght you are the only person who is answering what I asked. What I asked was, what modification do I need to do in the geeksforgeeks code to cope up with index out of bounds error, and people started advising me about "set" and all. — Asim, Jul 08 '20 at 06:11

score 1 · Answer 1 · answered Jul 08 '20 at 05:48

1

Iterate over array and check and store in set if not exists, So you can find all duplicates in O(n)

answered Jul 08 '20 at 05:48

Vikram Patil

628
6
20

But brother, if i do like that , for every value in the array i have to check against each value in the set. So it will be O(n^2) if all the values are distinct. – Asim Jul 08 '20 at 05:51
when you use sets or any hash based structure, you are making checks in O(1). https://www.geeksforgeeks.org/implementation-of-hashing-with-chaining-in-python/ https://stackoverflow.com/questions/3949310/how-is-set-implemented – Vikram Patil Jul 08 '20 at 05:58
like if i take [10, 20, 30], set states will be like 1. {10}, for searching 20 i need to see the whole set 2. {10, 20} for finding 30 i need to see the whole set. So it is O(n^2) right? – Asim Jul 08 '20 at 06:01
But the worst time complexity of using set is O(n), https://www.geeksforgeeks.org/internal-working-of-set-in-python/#:~:text=Checking%20if%20an%20item%20is,set%20is%20done%20through%20set. . I tried with set, its giving TLE so stop giving the same answer again and again. – Asim Jul 08 '20 at 06:04
1

you have to just check "10 in set_of_numbers" – Vikram Patil Jul 08 '20 at 06:04
https://stackoverflow.com/questions/3949310/how-is-set-implemented and there is concept called abstraction try understanding it – Vikram Patil Jul 08 '20 at 06:07
What I asked was, what modification do I need to do in the geeksforgeeks code to cope up with index out of bounds error, and people started advising me about set and all. – Asim Jul 08 '20 at 06:08
Again, I don't want advice on how can I do it with sets hashmaps and all. I just what to know how can I modify this code to get the desired result. – Asim Jul 08 '20 at 06:13

score 0 · Answer 2 · answered Jul 08 '20 at 06:26

0

Some people advised me of using a set to maintain the unique values so, iterate the array and store the values in the set. But i saw that python set has the worst time complexity of O(n), so if the array is already unique then that statement:

if key in set:

is taking a lot more time.

so i finally has written a code which can find it in O(n), please check and reply:

def check_duplicate(array):
    map_array = dict()
    for i in range(len(array)):
        map_array[array[i]] = i

    for i in range(len(array)):
        if map_array[array[i]] != i:
            return False

    return True

l = [1,2,3,4,1]

print(check_duplicate(l))

answered Jul 08 '20 at 06:26

Asim

85
1
11

isn't `if key in set` O(1)? it should be a hash map similar to dict. – Ehsan Jul 08 '20 at 07:08
Checking if an item is in : Time complexity of this operation is O(1) on average. However u=in worst case it can become O(n). Adding elements:- Insertion in set is done through set.add() function, where an appropriate record value is created to store in the hash table. Same as checking for an item, i.e., O(1) on average. However u=in worst case it can become O(n). – Asim Jul 08 '20 at 07:35
do you need worst case to be O(n)? I think in that case, a list of length of your maximum value in `array` would be the answer, not a dict or set. – Ehsan Jul 08 '20 at 07:39
OMG, Ehsan bro you got there. Yeah, this was the answer I was looking for. Thanks a lot for your help. I don't know why people were downvoting the question and not giving good answer to this. – Asim Jul 09 '20 at 17:12
Ehsan bro, please write a short answer to this, I want to set your answer as a solution. – Asim Jul 09 '20 at 17:15
I added an answer. Please check out to see if that answers your question. Thank you. – Ehsan Jul 09 '20 at 19:35

score 0 · Answer 3 · answered Jul 09 '20 at 19:35

This should be O(n) in worst case scenario in cost of memory (and this assumes values are int, if they are not, you still will need a hash table unless they are all in Q (and not R-Q)):

def printRepeating(arr): 
    min_val = min(arr)
    arr = [x-min_val for x in arr]
    count = [0]*(max(arr)+1)
    print("The repeating elements are: ")   
    for x in arr:    
      if count[x]: 
        print (x+min_val, end = " ") 
      else:
        count[x] = 1

Also, please mind that this reprints the multiple duplicates. If you need only a single copy, you can save duplicates and print only one copy.

Find duplicate in O(n)

3 Answers3