Let’s solve Leetcode 347 using Python.
Problem Statement
You are given an array nums
and an integer k
, you need to return k
most frequent elements.
Problem Explanation
Given array consists of repeated elements and we need to return k
which is the number of elements that are most repeated in the array. The length of array is between 1 and 10^5, and it is guaranteed that the answer is unique and there will always be k
unique elements.
Solution 1
Explanation
Step 1: To solve this, we would need to find how many times each element is occurring. To do this in the most efficient manner we can go through each element once and store the frequency in a dictionary.


Step 2: Sort the record dictionary in descending order of their occurrence.
We are using sorted
function which takes an iterable, and we are passing dictionary with .items()
it will convert key and value into tuple format.
record = sorted(record.items(), key=lambda x:x[1], reverse=True)
Step 3: Since now record is ordered in descending order of occurrence of elements, we can return the first k
elements.
Final Code


Algorithm Analysis
Time Complexity: O(n log n)
Space Complexity: O(n)
Solution 2
Explanation
The above solution had the time complexity of O(n log n), can we do better than that? In above solution, the time complexity comes from sorting the dictionary value, so if somehow we don’t need to sort then we might achieve O(n) of time complexity.
To do that we can take a hint from Bucket Sort strategy. We can create a lists of list, where index of the list represents occurrence of an element and then we can return the k
number of elements from that bucket list (tail first).
Step 1: Count the occurrence of each element and store it in the dictionary.


Step 2: Store the occurrences in a list bucket
. bucket
is a list of list, initialized to the length of the array+1, each index represents occurrence, and since there can be more than 1 element of same occurrence therefore we have used list of list.


Step 3: Iterate over the bucket
list from the tail till we get k
number of elements and then return the resulting array.
Final Code


Algorithm Analysis
Time Complexity: O(n)
Space Complexity: O(n)