Maximum repeated element

The problem is as follows:
Given an array of n numbers. Give an algorithm for finding the element which
appears maximum number of times in the array.

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

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

arr = [3,2,1,2,2,2,3]

def maximumRepetition(arr):
    numDict = {}
    for entry in arr:
        if entry in numDict:
            numDict[entry] += 1
            numDict[entry] = 1
    maxElement = 0
    maxCount = 0
    for entries in numDict:
        if numDict[entries] > maxCount:
            maxCount = numDict[entries]
            maxElement = entries
    return maxElement

print maximumRepetition(arr)

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

n = len(arr) #This is supposed to be given

def maximumRepitionImproved(arr):
    for i in range(len(arr)):
        arr[arr[i]] += n
    maxi = -1
    maxValue = 0
    for i in range(len(arr)):
        if arr[i]/n > maxValue:
            maxValue = arr[i]/n
            maxi = i
    return arr[maxi]

print maximumRepetition(arr)

Leave a Reply

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

You are commenting using your 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