Top K Frequent Elements

Free with account Updated Nov 19, 2026 · 5 min read
On this page

    Problem statement

    Given an array of integers and a number k, return the k values that occur most often. The answer is guaranteed to be unique, and it can be returned in any order. Aim for better than O(n log n).

    It combines two patterns you'll use constantly: count with a hash map, then select the top k, either with a heap or, faster, with buckets indexed by count. Original problem: LeetCode 347.

    Example

    4 appears four times and 1 three times, so with k = 2 the answer is [4, 1].
    4 appears four times and 1 three times, so with k = 2 the answer is [4, 1].
    Input:  nums = [1, 1, 1, 2, 2, 3, 4, 4, 4, 4], k = 2
    Output: [4, 1]       # any order
    Input:  nums = [7], k = 1
    Output: [7]

    Constraints (assumed)

    • 1 ≤ n ≤ 100,000; k is between 1 and the number of distinct values.
    • The top k is unique (no tie at the boundary).

    What this question tests

    • Counting with a hash map.
    • Selecting the top k without sorting everything.
    • Spotting that counts are bounded by n, which allows bucket sort.

    Questions to ask first

    1. Any order in the output? (Here: yes.)
    2. What if several values tie at the k-th place? (Here: it can't happen. If it could, ask which to return.)
    3. Is k small relative to the number of distinct values? A size-k heap is great when k is small.
    4. Is the input a stream? Then you'd keep counts and a structure updated incrementally.