Find The First Duplicate Number For Which The Second Occurrence Has The Minimal Index

October 26, 2023 Post a Comment

This is a question on codefights: Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence

Solution 1:

Emm... What's wrong with simple approach?

deffirstDuplicate(a):

   aset = set()
   for i in a:
       if i in aset:
           return i
       else:   
           aset.add(i)

print(firstDuplicate([7,4,5,6,4,6,3]))

dictionary version:

adict = {}
for i in a:
   if i in adict:
       return i
   else:   
       adict[i] = 1

Solution 2:

I think you can try using indexing technique here. Since you mentioned that numbers are in the range 1 to a.length, you can retrieve that element from the list, go to index l[i] and change that element to -l[l[i]] i.e.

l[l[i]] = -1 * l[l[i]]

While doing this, if you encounter a negative value, return the absolute value of the element present at this index. Let me know if you have problem implementing this. Here will be the code: (forgot to mention it earlier):

l = [7,4,5,6,4,2,3]
found = 0for i in range (0 , 6):
    item = abs(l[i])
    if(l[item - 1] > 0):
        l[item - 1] = -1 * l[item - 1]
    else:
        found = abs(l[i])
        breakprint (found)


output : 4

Time complexity : O(n)

Space : O(1)

Solution 3:

Your second for loop does the same for if and else condition, let's change that for loop, also, there's no need to store the elements that have less than two occurrences, so let's add that condition as well. What the second loop here does is, using list comprehension, it stores all occurrences of an element in a list(Famous solution), and then we store that in our indexdic. Finally, printing both dictionaries to see how they look like:

deffirstDuplicate(a):
    d = {}
    indexdic = {}

    for element in a:
        if a.count(element) > 1:
            if element in d:
                d[element] += 1else:
                d[element] = 1for key in d:
        indexdic[key] = [i for i, x inenumerate(a) if x == key]

    print('d: ', d)
    print('indexdic: ', indexdic)

Running this:

>>> firstDuplicate(['a','b','c','a','d','d','b'])
d:  {'a': 2, 'd': 2, 'b': 2}
indexdic:  {'a': [0, 3], 'd': [4, 5], 'b': [1, 6]}

Now after this hint, you need to work on what operations are needed in indexdic values to get the output you want, I'll let you work that out, it's an exercise afterall. Let me know if any of the steps is not well described.

Solution 4:

As I red in another post the key is to use a dictionary. Here is the solution for python 3. The index is the number, thus you will know if you saw it before.

deffirstDuplicate(a):
    oldies={}
    notfound=Truefor i inrange(len(a)):
        try:
            if oldies[a[i]]==a[i]:
                notfound=Falsereturn a[i]     
        except:
            oldies[a[i]]=a[i]
    if notfound:
        return -1

Solution 5:

def firstDuplicate(a):
lst = list()
x=-1for i in a:
    if i in lst:
        x = i
        breakelse:
       lst.append(i)
return(x)

This answer solves 20/22 inputs. Codefights gives error that it exceeds time limit.

Python Playground