ToolMight LogoToolMight
MediumArrays & HashingHeap & Priority QueuePattern: Bucket SortPattern: Frequency Map

Top K Frequent Elements

Return the k most frequent elements in an integer array. Master the Bucket Sort pattern to achieve linear O(n) runtime better than O(n log n) sorting.

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.

Examples & Constraints

Example 1
Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
Explanation: 1 appears three times, 2 appears twice, and 3 appears once. The 2 most frequent numbers are [1, 2].
Example 2
Input: nums = [1], k = 1
Output: [1]
Explanation: 1 is the only element, so it is the most frequent.
Constraints
  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in the array].
  • It is guaranteed that the answer is unique.

Bucket Sort by Frequency (Linear O(n) Time)

Optimal Approach
Time:O(n)
Space:O(n)

Count frequencies in a hash map. Group numbers into buckets indexed by their frequency count (0 to n). Iterate backwards from the highest frequency bucket to collect the top k elements in O(n) time.

Time ComplexityO(n)

Building the frequency map takes O(n). Distributing items into buckets takes O(n). Scanning the buckets from N down to 1 takes O(n). Total runtime is strictly linear O(n).

Space ComplexityO(n)

Consumes memory for the frequency hash map and the bucket array of size N + 1.

Underlying algorithmic logic

Why Sort by Frequency Can Be O(n)

Usually, sorting items by their frequency takes O(m log m) where M is the number of unique elements.

However, notice a crucial frequency constraint:

  • An element can appear at most N times (the total length of the array).
  • Therefore, the possible frequencies are integers bounded between 1 and N.

When values are bounded integers, we can use Bucket Sort!

The Bucket Sort Algorithm:

  1. Count Frequencies:
  • Use a Hash Map to count occurrences of each number: counts[num] = count.
  1. Create Buckets:
  • Create an array of lists buckets of size n + 1.
  • buckets[freq] stores all numbers that appeared exactly freq times.
  • For example, if number 1 appeared 3 times, place 1 in buckets[3].
  1. Collect Top K from Right to Left:
  • Traverse buckets starting from index n down to 1 (highest frequency first).
  • Append numbers from each non-empty bucket to our result list until we have collected k elements.
  1. Return the result list in guaranteed linear O(n) time!

Step-by-step execution walkthrough

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

Count frequencies using hash map: {1: 3, 2: 2, 3: 1}.

counts: 1 -> 3, 2 -> 2, 3 -> 1
2
Populate Buckets

buckets[3] = [1], buckets[2] = [2], buckets[1] = [3]. All others empty.

buckets: 3:[1], 2:[2], 1:[3]
3
Scan from Right (Freq 3)

buckets[3] contains [1]. Add 1 to result. Count collected = 1 < 2.

res = [1]
4
Scan Freq 2

buckets[2] contains [2]. Add 2 to result. Count collected = 2 == k. Terminate!

Final res: [1, 2]
Advantages
  • •Optimal O(n) runtime beating traditional O(n log n) sorting
  • •Straightforward bucket array traversal
Trade-offs
  • •Consumes O(n) auxiliary memory for buckets array

Code Implementations

Copy & paste production-ready solutions for Bucket Sort by Frequency (Linear O(n) Time) in your language of choice

File: solution.py
Python
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
    # buckets[i] stores numbers that appear i times
    buckets = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)
    res = []
    for freq in range(len(nums), 0, -1):
        for num in buckets[freq]:
            res.append(num)
            if len(res) == k:
                return res
    return res
if __name__ == "__main__":
    test1 = [1, 1, 1, 2, 2, 3]
    k1 = 2
    test2 = [1]
    k2 = 1
    print("test1 top 2:", top_k_frequent(test1, k1))
    print("test2 top 1:", top_k_frequent(test2, k2))
Interactive visualizer available

Understand Hash Table Visually

Visualize key hashing functions, index mapping arrays, and hash collision resolution techniques. Test live edge cases and watch memory state transitions step-by-step.

Launch Hash Table Visualizer

Frequently Asked Questions

Related Logic & Algorithm Problems

All problems
EasyArrays & Hashing
Visualizer

Contains Duplicate

Determine if any value appears at least twice in an integer array. A foundational problem for mastering constant-time hash lookups vs sorting trade-offs.

2 approaches(O(n))
Learn logic
MediumHeap & Priority Queue
Visualizer

Kth Largest Element in an Array

Find the kth largest element in an unsorted array. The premier problem for learning Min-Heap bounded tracking and Quickselect partitioning.

1 approach(O(n log k))
Learn logic
EasyArrays & Hashing
Visualizer

Two Sum

Find the two numbers in an array that sum up to a target value. The quintessential problem for learning how to trade memory for speed using a Hash Map.

2 approaches(O(n))
Learn logic