First element which is repeated

The problem is:
Given an array of n numbers give an algorithm for finding the first element in the array which is repeated.

Sample Input : [3,2,1,2,2,3]
Sample Output : 3


'''Using hashing technique
Complexity Time: O(n) Space: O(n)'''

def detectRepetition(arr):
    numDict = {}
    
    for i in range(len(arr)):
        if arr[i] in numDict:
            if numDict[arr[i]] < 0:
                pass
            else:
                numDict[arr[i]] = -(numDict[arr[i]]) 
        else:
            numDict[arr[i]] = i+1
    
    max = -100000000000000   
    repeatedentry = 0     
    for entry, pos in numDict.iteritems():
        if pos < 0:
            if pos > max:
                max = pos
                repeatedentry = entry
                
    return repeatedentry

print detectRepetition(arr)

Advertisement

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s