# The optimized way to find the top k leading candidates from a unsorted hash map in python

I need to write a method that will accept a timestamp and takes an array of votes, I need to return the k leading candidates with that timestamp. I came up with the following solution,

Here is the input to the methods:

votes = [{'candidate':'a', 'timestamp':2},{'candidate':'c', 'timestamp': 5},{'candidate':'c', 'timestamp': 12}]

timestamp = 5

k = 5


And the method to solve the problem,

def leading_candidates(votes, timestamp,k):

candidates = {}

if vote['timestamp'] <= timestamp:
if vote['candidate'] not in candidates:
candidates[vote['candidate']] = 1
else:
candidates[vote['candidate']] += 1

for candidate in candidates:



As you can see the second solution has a time complexity of $$\O(k\,n)\$$ where k is the time it takes to find the index in the leading candidates sorted array, In the worst case, it can be $$\O(n^2)\$$ and because of sorting it may be at least $$\O(n\,\log n)\$$.

Is there any way we can make it work with $$\O(n)\$$?

• You already know that everything in sorted_votes is in candidates. Why not "for sorted_votes" k times instead of "for candidates"? – Frank Merrow Feb 12 at 3:37
• @FrankMerrow Yes, but how efficient it is to find the key of particular value in the hash table? – kgangadhar Feb 12 at 4:47
• Is there any other thing I can do to change the time taken. – kgangadhar Feb 12 at 4:48
• Welcome to CodeReview@SE. What is timestamp duration? – greybeard Feb 12 at 7:18
• (I do not want to know one/the value to use: I have no idea how to interpret it just from the problem description. I think one timestamp to mark one point in time, a duration could be specified by two timestamps. Then, there is before and after.) – greybeard Feb 12 at 8:42

So, you want to count something and afterwards get the top k? That sounds like a job for collections.Counter!

from collections import Counter

vote_counts = Counter(vote['candidate']
if vote['timestamp'] <= timestamp)
return [candidate[0] for candidate in vote_counts.most_common(k)]

if __name__ == "__main__":

This way you don't need to special case a candidate not yet having received a vote (something you could have also done with a collections.defaultdict(int)). And it is $$\\mathcal{O}(n)\$$.
Also note that if k is large, the line if candidates[candidate] in sorted_votes will become slow, as it is a linear scan. At the same time, you can iterate over the keys and values of a dictionary at the same time with candidates.items(), so you don't need to do candidates[candidate].
Python has an official style-guide, PEP8, which recommends using spaces after commas, which you forgot to do before k in the function signature.
You should always guard your code with an if __name__ == "__main__": guard to allow importing from the script without running it.
• Counter.most_common() uses a heap so it is O(k log h), where h is the total number of candidates (e.g., the size of the heap). Of course for most uses, neither k nor h are large. – RootTwo Feb 12 at 23:18
• @RootTwo True. And log h < n and k is constant. But filling the Counter is still O(n). – Graipher Feb 12 at 23:21
• @RootTwo Yup, Counter.most_common() uses a heap; more specifically, it uses heapq.nlargest(). Which according to stackoverflow.com/a/23038826 and stackoverflow.com/a/33644135 it actually has a time complexity of O(h log k), where h is the total number of candidates. – Setris Feb 13 at 1:42