0

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))
Syed
  • 144
  • 9
  • 1
    I’m voting to close this question because this question might belong to another Stack site - [codereview](https://codereview.stackexchange.com) – baduker Feb 27 '21 at 17:12
  • [This](https://stackoverflow.com/questions/10797819/finding-the-mode-of-a-list) might be helpful – Kraigolas Feb 27 '21 at 17:18

3 Answers3

1
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
Amazing Coder
  • 21
  • 4
  • You should include what you expect the output to be. "smallest element with highest occurrences" I think you mean, the highest frequency is 3, both 3 and 4 occur 3 times. Then the answer is 3 because that is the smallest number with the maximum occurrence? – Vincent Feb 28 '21 at 05:35
1

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
Alain T.
  • 40,517
  • 4
  • 31
  • 51
  • `collections.Counter` would be even simpler: you can just give it a sequence and it'll compute the counts. – Masklinn Feb 27 '21 at 18:22
  • @Masklinn, indeed but I needed to illustrate my point about only adding 1 per bird rather than calling sum() each time. Counter would have abstracted part that too much. – Alain T. Feb 27 '21 at 19:42
-1

I am a new entry too in python! I solved like that...maybe this was not the scope of the exercise and probably this will be the worst code you have ever seen running...but it runs! :D

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

import pandas as pd
a=pd.Series(arr)

x=a.value_counts()==a.value_counts().max()
print( x[x].tail(1).index[0] )
BB-8
  • 1
  • 2