I am solving a problem on HackerEarth (full text can be found here):
Bob has a playlist of songs, each song has a singer associated with it (denoted by an integer)
Favourite singer of Bob is the one whose songs are the most on the playlist
Count the number of Favourite Singers of Bob
For example with [1, 1, 2, 2, 3] as input, the output should be 2 since both 1 and 2 as the most common.
The problem is that my code passes all the test cases except for the ones which have large data sets, this violates the time constraints. Certainly, I need to optimise my code further.
Here’s my code:
singer_tokens = input()
singer_tokens = singer_tokens.split(' ')
fav_singers = []
result = []
for i in singer_tokens[:]:
if i not in result:
result.append(i)
for i in result:
fav_singers.append(singer_tokens.count(i))
max_elem = max(fav_singers)
print(fav_singers.count(max_elem))
user26346636 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
bottlenecks and improvements
Your code has two main inefficient steps.
Here you are searching in the list of unique values for each new item.
Once result starts to be large, this search will be inefficient
for i in singer_tokens[:]:
if i not in result: # this is inefficient
result.append(i)
This step is done efficiently using a set in python:
result = set(singer_tokens)
Then you search each unique value in the full input, this means that you will have to read again the full list for each unique value.
for i in result:
fav_singers.append(singer_tokens.count(i))
You could use a dictionary to keep track of the values. This way you won’t even have to know the list of unique values in advance:
counts = {}
for s in singer_tokens:
counts[s] = counts.get(s, 0) + 1
Or, better, using collections.Counter:
from collections import Counter
counts = Counter(singer_tokens)
Then to get the number of maxima:
counts = list(Counter(singer_tokens).values())
print(counts.count(max(counts)))
batteries included
Now, there’s an even better approach since python is delivered with batteries included, using statistics.multimode which will return the list of most frequent values:
from statistics import multimode
print(len(multimode(singer_tokens)))
Output: 2
0