CODEWITHSUNDEEP
pythonpython-3.xlistpython-2.7
Syed
Syed

Reputation: 146

Optimizing Python Code for returning the smallest element with highest occurrences in a list

I am trying to solve one of HackerRanks easy rated problems with Python. My code solves 4 out of 5 test cases but for one of the test cases, I get an error message saying time limit exceeded. Please recommend ways to optimize this. I am a beginner at python and still trying to understand itertools but it seems quite complicated.

Problem Statement: Given an array of bird sightings where every element represents a bird type id, determine the id of the most frequently sighted type. If more than 1 type has been spotted that maximum amount, return the smallest of their ids.

Sample input: arr=[1,2,3,4,5,4,3,2,1,3,4] Sample output: 3

My current code:

def migratoryBirds(arr):
    d={}
    arr2=[]
    for i in range(len(arr)):
        d[arr[i]]=arr.count(arr[i])
    for i in d.keys():
        if d[i]==max(d.values()):
            arr2.append(i)
    return(min(arr2))

Upvotes: 0

Views: 114

Answers (2)

Amazing Coder
Amazing Coder

Reputation: 31

def migratoryBirds(arr):                                                                                                                                                                                                                                                                    
    most_common_item = max(arr, key=arr.count)           
    print(most_common_item)


migratoryBirds([1, 2, 3, 4, 5, 4, 3, 2, 1, 3, 4]) # Testing

Upvotes: 2

Alain T.
Alain T.

Reputation: 42143

Your algorithm is slower because you are going through the whole array multiple times with the .count() function. You are also going through your dictionary multiple times in the second loop with the max() function. This results in O(N^2) time complexity.

To achieve O(N) time, you should only add 1 per item in the array and then process the dictionary on the basis of max total / min id:

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

counts = {}
for bird in arr: counts[bird] = counts.get(bird,0) + 1      # +1 per bird
result,_ = max(counts.items(),key=lambda kv:(kv[1],-kv[0])) # max total / min id

print(result) # 3

Upvotes: 2

Related Questions