Top K Frequent Elements

12 May 2026 0 Likes

Problem Description

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
 Output: [1,2]
Explanation: The element 1 appears 3 times and 2 appears 2 times, making them the two most frequent elements.
Example 2:
Input: nums = [1], k = 1
 Output: [1]
Explanation: Since there is only one element in the array, it becomes the most frequent element automatically.
Example 3:
Input: nums = [4,4,4,6,6,1,1,1,1], k = 2
 Output: [1,4]
Explanation: The element 1 appears 4 times and 4 appears 3 times, so they are the top 2 frequent elements.

Constraints

The array contains at least 1 element. The value of each integer inside nums may be positive, negative, or zero.

k will always be valid and less than or equal to the number of unique elements in the array. The answer is guaranteed to be unique.

An efficient solution is expected to perform better than O(n log n) in some optimized approaches.

Understanding the Problem

The problem is asking us to identify the elements that appear most frequently inside the array.

A simple way to understand the problem is by first counting how many times each element occurs. For example:

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

The frequencies become:

1 → 3 times
2 → 2 times
3 → 1 time

Now we need to return the 2 elements having the highest frequencies. That means: 1 and 2.

The main challenge is efficiently tracking frequencies and retrieving the most frequent elements without repeatedly scanning the array.

Hints

The first hint is to think about how frequencies of elements can be stored efficiently. A HashMap can help store:

Key → element
Value → frequency count

Once the frequencies are known, the next challenge is selecting the elements with the highest counts.

Sorting based on frequencies is one possible approach, but there are more efficient techniques such as Bucket Sort or Priority Queue.

Try thinking about how elements can be grouped according to their frequencies.

Solutions

BRUTE FORCE

HashMap with Frequency Sorting Solution

This approach first counts the frequency of every element using a HashMap.

The map stores:
Key → element
Value → frequency count

After counting frequencies, we sort the map entries in descending order of frequency.

Once the entries are sorted, we simply pick the first k elements because they represent the most frequent values in the array.

For example: nums = [1,1,1,2,2,3]

Frequency map:
1 → 3
2 → 2
3 → 1

After sorting by frequency:
1 → 3
2 → 2
3 → 1

The first k elements become the answer.

Although this solution is simple and intuitive, sorting introduces additional overhead.
public class A_BruteForce {

    public int[] topKFrequent(int[] nums, int k) {

        Map<Integer, Integer> unsortedMap = new HashMap<>();

        for (int num : nums) {
            unsortedMap.put(
                    num,
                    unsortedMap.getOrDefault(num, 0) + 1
            );
        }

        Map<Integer, Integer> sortedMap = unsortedMap.entrySet()
                .stream()
                .sorted(
                        Map.Entry
                                .<Integer, Integer>comparingByValue()
                                .reversed()
                )
                .collect(Collectors.toMap(
                        Map.Entry::getKey,
                        Map.Entry::getValue,
                        (oldValue, newValue) -> oldValue,
                        LinkedHashMap::new
                ));

        int[] output = new int[k];

        int i = 0;

        for (Map.Entry<Integer, Integer> entry : sortedMap.entrySet()) {

            if (i == k)
                break;

            output[i] = entry.getKey();

            i++;
        }

        return output;
    }
}
class Solution:

    def topKFrequent(self, nums, k):

        freq = Counter(nums)

        sorted_items = sorted(
            freq.items(),
            key=lambda x: x[1],
            reverse=True
        )

        result = []

        for i in range(k):
            result.append(sorted_items[i][0])

        return result
Time Complexity
O(n log n)
Space Complexity
O(n)
OPTIMAL

Bucket Sort Frequency Grouping Solution

This approach uses a combination of HashMap and Bucket Sort to efficiently retrieve the most frequent elements.

First, we count the frequency of every element using a HashMap.

After counting frequencies, we create an array of lists called buckets, where:
Index → frequency
Value → list of elements having that frequency

For example:
If the number 1 appears 3 times, it will be stored inside: buckets[3].

Once all elements are grouped by frequency, we traverse the bucket array from the highest frequency toward the lowest frequency.

This ensures that the most frequent elements are collected first. We continue collecting elements until we obtain exactly k elements.

This approach avoids sorting the entire frequency map and achieves highly efficient performance.
class Solution:

    def topKFrequent(self, nums, k):

        count = Counter(nums)

        buckets = [[] for _ in range(len(nums) + 1)]

        for num, freq in count.items():
            buckets[freq].append(num)

        result = []

        for i in range(len(buckets) - 1, -1, -1):

            for num in buckets[i]:

                result.append(num)

                if len(result) == k:
                    return result
public class B_BucketSort {

    public int[] topKFrequent(int[] nums, int k) {

        int[] result = new int[k];

        Map<Integer, Integer> counts = new HashMap<>();

        for (int num : nums) {
            counts.put(
                    num,
                    counts.getOrDefault(num, 0) + 1
            );
        }

        List<Integer>[] buckets = new List[nums.length + 1];

        counts.forEach((val, freq) -> {

            if (buckets[freq] == null) {
                buckets[freq] = new ArrayList<>();
            }

            buckets[freq].add(val);
        });

        int index = 0;

        for (int i = buckets.length - 1; i >= 0; i--) {

            if (buckets[i] != null) {

                for (int num : buckets[i]) {

                    result[index++] = num;

                    if (index == k)
                        return result;
                }
            }
        }

        return result;
    }
}
Time Complexity
O(n)
Space Complexity
O(n)

Conclusion

The Top K Frequent Elements problem is an important interview problem that combines concepts of hashing, frequency counting, and efficient data retrieval.

The problem teaches how to organize data based on occurrence counts and how to efficiently extract the most important elements.

Mastering this problem helps build a strong understanding of HashMaps, heaps, bucket sorting, and frequency-based processing, which are commonly used in real-world systems and coding interviews.

💬 Comments