Let’s solve Leetcode 347 using Python.

Table of Contents

• Problem Statement
• Problem Explanation
• Solution 1
  • Explanation
  • Final Code
  • Algorithm Analysis
• Solution 2
  • Explanation
  • Final Code
  • Algorithm Analysis

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.

record = dict()
for num in nums:
    record[num] = record.get(num, 0) + 1

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

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        record = dict()
        for num in nums:
            record[num] = record.get(num, 0) + 1

        record = sorted(record.items(), key=lambda x:x[1], reverse=True)
        return [elem[0] for elem in record[:k]]

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.

record = dict()
for num in nums:
    record[num] = record.get(num, 0) + 1

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.

bucket = [[] for _ in range(len(nums)+1)]
for num, freq in record.items():
    bucket[freq].append(num)

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

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        record = dict()
        bucket = [[] for _ in range(len(nums)+1)]

        for num in nums:
            record[num] = record.get(num, 0) + 1

        for num, freq in record.items():
            bucket[freq].append(num)

        res = []
        for i in range(len(bucket)-1, 0, -1):
            for x in bucket[i]:
                res.append(x)
                if len(res) == k:
                    return res

Algorithm Analysis

Time Complexity: O(n)

Space Complexity: O(n)