# Top 2 most common elements inside array in Python

I got this interview problem from leetcode for top k frequent elements, https://leetcode.com/problems/top-k-frequent-elements/description/ But I decide to simplify the problem just most common elements to make it simpler to solve. If the 3 item has the same frequentcy, then it's okay to return all 3.

"""Given an array, return an array of the top 2 most elements. // Input: [1, 2, 3, 4, 5, 3, 4] | Output: [3, 4] // Input: [2, 2, 3, 2, 4, 3, 4] | Output: [2,4]"""

import collections

def top2Frequent(nums):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
if len(nums) < 2:
return []
freq = {}
for num in nums:
if num in freq:
freq[num] = freq[num] + 1
else:
freq[num] = 1

bucket = collections.defaultdict(list)
for key in freq:
f = freq[key]
bucket[f].append(key)
res = []
count = len(nums)  # the upper limit for res
while len(res) < 2:
if bucket[count]:
res += bucket[count]
count -= 1
return res

nums = [1, 4, 3, 4, 5, 3, 4]  # [4,3]
solution = top2Frequent(nums)
print(solution) # [4,3]


https://gist.github.com/Jeffchiucp/2e733e57476bd697bc430cdf48f6e180

I am also tried to solve this problem without using any python library built in collections.

• I'm confused, you say you don't want to use the built-in collections, but you used collections.defaultdict. Jul 23, 2018 at 15:39
• I don't think the code works as required, when I use nums = [2, 2, 3, 3, 3, 4, 4, 5] the result is [3, 2, 4]. Please fix this before people can answer the question, see also"If your question contains broken code…". Jul 23, 2018 at 16:37

If you're okay with using the built-in collections module, I'd suggest the following. collections.Counter is ideally suited for this and will make the problem trivial.

from collections import Counter

def top_k(numbers, k=2):
"""The counter.most_common([k]) method works
in the following way:
[('a', 5), ('r', 2), ('b', 2)]
"""

c = Counter(numbers)
most_common = [key for key, val in c.most_common(k)]

return most_common


Without using the built-in collections module, the following will work:

def top_k_nobuiltin(numbers, k=2):
# The first part is identical to your implementation and works just
# fine
counter = {}
for number in numbers:
if number in counter:
counter[number] += 1
else:
counter[number] = 1

# The line below creates an iterator that will generate the
# sequence [(4, 3), (3, 2), (5, 1), (1, 1)], i.e.
# count the occurrence for each value.
# In particular, sorted() with key=lambda kv: kv[1] will turn
# a dictionary into a list of tuples, sorted by the second item
# of each tuple

sorted_by_value = reversed(sorted(counter.items(), key=lambda kv: kv[1]))

top_vals = [item[0] for item in sorted_by_value][:k]



For both cases, you'll get the desired result:

def main():
nums = [1, 4, 3, 4, 5, 3, 4]  # [4,3]

print(top_k(nums))  # [4,3]
print(top_k_nobuiltin(nums))  # [4,3]

if __name__ == '__main__':
main()

• You have presented an alternative solution, but haven't reviewed the code. Please edit it to explain your reasoning (how your solution works and how it improves upon the original) so that everyone can learn from your thought process. Jul 23, 2018 at 17:08
• @TobySpeight I think that the justification for this answer was self-evident. Jul 23, 2018 at 17:55
• I think this solutions violate the must be better than O(n log n) time complexity requirement. Jul 23, 2018 at 18:25

According to the leetcode description one requirement of the algorithm is:

...must be better than O(n log n), where n is the array's size.

I am not 100% sure but i think you can't use the built-in sorted method of python since it has a time complexity of O(n log n). One possibility for this problem is a bucket sort approach.

The idea:

1. Count frequency of elements in list.
2. Create a list of buckets with len(nums) + 1 length
3. Iterate over the frequency dict and put elements in buckets according to their frequency
4. Iterate in reversed order over the bucket list and return k first elements.
def top_k_frequent(nums, k):
cnt = {}
for n in nums:
cnt[n] = cnt.get(n, 0) + 1

bucket = [[] for _ in range(len(nums)+1)]
for key, val in cnt.items():
bucket[val].append(key)

res = []
for i in reversed(range(len(bucket))):
if bucket[i]:
res.extend(bucket[i])
if len(res) >= k:
break

return res[:k]


Please also see the more elegant approach to count with dict in python.