Top K Frequent Elements

Difficulty: Medium

Problem

Given an integer array nums and an integer k, find the k values that appear most often in nums and return them.

Example

Input: nums = [4, 4, 4, 4, 7, 7, 9, 9, 9, 5], k = 2
Output: [4, 9]
Explanation: Counts: 4 appears 4 times, 9 appears 3 times, 7 appears twice and 5 once. The two most frequent values are 4 and 9.

Brute-force approach

Count frequencies, then sort by frequency to get top k.

Steps

  1. Count frequency of each element
  2. Sort elements by frequency (descending)
  3. Return first k elements

Time complexity: O(n log n) · Space complexity: O(n)

Trade-offs

  • Sorting is O(n log n)
  • We only need top k, not full sort
  • Heap can do better

Optimal approach

Key insight: Frequency range is 1 to n. Create buckets where index = frequency. Place numbers into corresponding frequency bucket!

Use bucket sort: create buckets where index = frequency, place numbers into corresponding bucket, then traverse from high to low to collect top k.

Steps

  1. Count frequencies with hash map
  2. Create n+1 buckets (index 0 to n)
  3. Fill buckets by frequency: bucket[freq].add(num)
  4. Traverse buckets from high → low
  5. Collect first k elements

Time complexity: O(n) · Space complexity: O(n)

Pseudocode

function topKFrequent(nums, k):
    count frequency of each element
    
    create buckets array of size n+1
    for each element, count in frequency map:
        buckets[count].append(element)
    
    result = []
    for i from n down to 1:
        for each element in buckets[i]:
            result.append(element)
            if length of result == k:
                return result
    
    return result

Hints

  • First count frequencies with a hash map
  • The maximum frequency can be at most n (array length)
  • Bucket sort: put elements in bucket[frequency]

Complexity questions

Time to count and sort frequencies?

O(n log n). O(n) to count + O(n log n) to sort = O(n log n)

Time complexity of bucket sort approach?

O(n). O(n) count + O(n) bucket + O(n) collect = O(n)

Time with min-heap of size k?

O(n log k). n elements, each heap operation is O(log k) = O(n log k)

Space for bucket sort approach?

O(n). O(n) for frequency map + O(n) for buckets = O(n)

Check your understanding of Top K Frequent Elements

What does 'top k frequent' mean?

The k numbers that appear most often. We need to find the k elements that appear most frequently in the array.

Given [1,1,1,2,2,3] and k=2, what are the top 2 frequent elements?

[1, 2]. 1 appears 3 times (most), 2 appears 2 times (second most). So [1, 2].

If multiple elements have the same frequency, what do we do?

Return any k of them. When frequencies are equal, we can return any of the tied elements.

Related problems

Keep practising