deepSWE.io

Top K Frequent Elements

Hashing

25 min

Problem Statement

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Solution (Hash Map & Bucket Sort)

This problem can be solved by first counting the frequency of each element using a hash map. Then, we can use a variation of bucket sort to group elements by their frequency.

Algorithm Steps

Count the frequency of each number in the input array and store it in a hash map.
Create an array of lists (buckets), where the index represents the frequency.
Iterate through the frequency map and place each number in the bucket corresponding to its frequency.
Iterate through the buckets from the end (highest frequency) and collect the elements until you have `k` elements.

Nums:k:

Frequency Map

Start. Count frequencies of each number.

Top K Frequent Elements Solution


from collections import Counter

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        count = Counter(nums)
        return [item[0] for item in count.most_common(k)]