Top K Frequent Elements

Difficulty: Medium

Problem

Given an integer array nums and an integer k, return the k most frequent elements.

Example

Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
Explanation: 1 appears 3 times, 2 appears 2 times. These are the top 2 frequent elements.

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)