Detecting Duplicate Elements

The problem is as follows:
Given an array of n numbers, give an algorithm for checking
whether there are any duplicated elements in the array or not

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

arr = [3,2,1,2,2,3]
'''Using hashing
Complexity Time O(n), Space O(n)'''

def duplicateElements(arr):
    duplicates = {}
    
    for entry in arr:
        if entry in duplicates:
            if duplicates[entry] < 0:
                pass
            else:
                duplicates[entry] = -(duplicates[entry])
        else:
            duplicates[entry] = 1
            
    duplicateList = []
    for entries in duplicates:
        if duplicates[entries] < 0:
            duplicateList.append(entries)
        else:
            pass
    return duplicateList
        


print duplicateElements(arr)

'''Improved method
Complexity Time: O(n), Space: O(1)'''

def detectDuplicateElementsImproved(arr):
    for i in range(len(arr)):
        if arr[arr[i]] < 0:
            return True
        else:
            arr[arr[i]] = -arr[arr[i]]
    return False

print detectDuplicateElementsImproved(arr)

Advertisement