Problem statement

Given an integer array nums and an integer k, return the k most frequent elements, ordered by frequency from highest to lowest. If two values have the same frequency, put the smaller value first.

Example 1

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2

Input: nums = [4,4,7,7,5], k = 3
Output: [4,7,5]
Explanation: 4 and 7 tie on frequency — smaller first.

Constraints

• 1 <= nums.length <= 30
• -50 <= nums[i] <= 50
• k is between 1 and the number of distinct elements.

Hints for Top K Frequent Elements

1. Hint 1

   Count with a hash map, then pick the top k by (frequency, value).

2. Hint 2

   Bucket sort by frequency achieves O(n).

How to solve Top K Frequent Elements

Two independent steps. First count occurrences with a hash map — that collapses the array to at most one entry per distinct value. Then pick the best k entries under the ordering the problem defines: frequency descending, and on a tie the smaller value first.

Approach

1. Sweep the array once, incrementing a counter per value.
2. Collect the distinct values.
3. Sort them by (-frequency, value) — highest frequency first, and ascending value as the tie-break.
4. Return the first k.

Why it works

Counting is exact and order-independent, so after the first sweep the frequencies are final. The comparator then encodes the required ordering completely: the primary key selects by popularity, and the secondary key removes the ambiguity between equally frequent values, making the output uniquely determined. With O(d log d) for d distinct values this is fast enough; a bucket sort indexed by frequency would make the selection step linear.

Complexity

• Time — O(n + d log d)
• Space — O(d)

Pitfalls

• The tie-break is mandatory here. Without it two equally frequent values may come out in either order and the answer becomes non-deterministic.
• Sort the distinct values, not the original array.
• Frequency is descending while the tie-break is ascending — mixing the directions up is easy in a single comparator.

Reference solution

Python

from typing import List
from collections import Counter

def topKFrequent(nums: List[int], k: int) -> List[int]:
    count = Counter(nums)
    ordered = sorted(count.items(), key=lambda e: (-e[1], e[0]))
    return [v for v, _ in ordered[:k]]

Java

public static int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : nums) count.put(x, count.getOrDefault(x, 0) + 1);
    List<Integer> values = new ArrayList<>(count.keySet());
    Collections.sort(values, (a, b) -> {
        int fa = count.get(a);
        int fb = count.get(b);
        if (fa != fb) return fb - fa;
        return a - b;
    });
    int[] out = new int[k];
    for (int i = 0; i < k; i++) out[i] = values.get(i);
    return out;
}

C++

vector<int> topKFrequent(vector<int>& nums, int k) {
    map<int, int> count;
    for (int x : nums) count[x]++;
    vector<pair<int, int>> items(count.begin(), count.end());
    sort(items.begin(), items.end(), [](const pair<int, int>& a, const pair<int, int>& b) {
        if (a.second != b.second) return a.second > b.second;
        return a.first < b.first;
    });
    vector<int> out;
    for (int i = 0; i < k && i < (int) items.size(); i++) out.push_back(items[i].first);
    return out;
}

JavaScript

var topKFrequent = function(nums, k) {
    const count = new Map();
    for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
    return Array.from(count.entries())
        .sort(function(a, b) { return (b[1] - a[1]) || (a[0] - b[0]); })
        .slice(0, k)
        .map(function(e) { return e[0]; });
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium