Top K Frequent Elements

Problem in Plain English

Given an integer array and a count k, return the k elements that appear most often. The answer is guaranteed unique and may be returned in any order.

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.

Counting frequencies is only half the job; the challenge is selecting the top k without paying a full sort. Because no value can occur more than n times, frequencies double as bucket indices for a linear-time selection. The answer is guaranteed unique as a set of k values; ties within that set are allowed.

Follow-up: use less than $O(n log n)$ time, where n is the input length.

Constraints

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= number of distinct values in nums
It is guaranteed that the answer is unique.

Examples

Example 1

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

1 occurs three times and 2 occurs twice, making them the top 2 most frequent elements.

Example 2

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

The only element present is automatically the most frequent.

Example 3

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

Values 1 and 2 each occur four times, while 3 occurs twice. Both tied leaders belong in the answer; their order does not matter.

Example 4

Input: nums = [-1, -1, 0, 0, 5], k = 3
Output: [-1, 0, 5]

k equals the three distinct values, so all are returned despite different frequencies. Negative numbers and zero are ordinary map keys.

Intuition

Rank distinct values by how often they appear, not by their numeric size. Example 1 has counts {1: 3, 2: 2, 3: 1}, so k = 2 selects 1 and 2. A frequency is never larger than the array length: place each value in the bucket numbered by its frequency, then visit buckets from high counts to low counts.

Approaches

Count and Sort

Solution Details

Reveal Count and Sort: intuition, complexity, and code

Intuition

Count each value once in a hash map, then order the distinct values by their counts and take the first k. Sorting the distinct values dominates the cost, which bucketing by frequency later removes.

Step-by-Step Logic

Create an empty frequency map. For each num, increment its count; Example 1 builds {1: 3, 2: 2, 3: 1} after six updates.
Collect each distinct map key once. Here the keys are [1, 2, 3]; map iteration order may vary across languages.
Sort the keys by descending map count, not by their numeric value. Example 1 gives [1, 2, 3] with frequencies [3, 2, 1]. Equal-frequency values may be in either order.
Take exactly the first k keys and return them. With k = 2, return [1, 2]; the uniqueness guarantee prevents an ambiguous tie across the cutoff.

Why It Works

The counting pass records every occurrence, so each key has its true frequency. Sorting places every larger count before every smaller one. Taking the first k distinct keys therefore selects the k highest frequencies. Ties within the chosen set may be ordered freely; a tie crossing the cutoff would contradict the guaranteed unique answer.

Dry Run

Count and Sort: variable states at each step
Phase	Index: value / action	Count map	Ranked keys	Result
Count	0: 1	{1: 1}	none	[]
Count	1: 1	{1: 2}	none	[]
Count	2: 1	{1: 3}	none	[]
Count	3: 2	{1: 3, 2: 1}	none	[]
Count	4: 2	{1: 3, 2: 2}	none	[]
Count	5: 3	{1: 3, 2: 2, 3: 1}	none	[]
Collect	collect distinct keys	{1: 3, 2: 2, 3: 1}	[1, 2, 3]	[]
Sort	descending counts [3, 2, 1]	unchanged	[1, 2, 3]	[]
Select	take position 0	unchanged	[1, 2, 3]	[1]
Select	take position 1; k = 2 reached	unchanged	[1, 2, 3]	[1, 2]; return

Complexity Analysis

Time Complexity

O(n log n)

Space Complexity

O(n)

Let n be the input length and u the number of distinct values. Counting takes expected O(n) time, sorting u keys costs O(u log u), and selecting k costs O(k), bounded overall by O(n log n). The map, key list, and sorting workspace use O(u) space, bounded by O(n); the result holds k values. This baseline does not meet the follow-up when u grows with n.

Code

Solution.java

1import java.util.*;2
3class Solution {4    public int[] topKFrequent(int[] nums, int k) {5        Map<Integer, Integer> count = new HashMap<>();6        for (int num : nums) {7            count.put(num, count.getOrDefault(num, 0) + 1);8        }9        List<Integer> unique = new ArrayList<>(count.keySet());10        unique.sort((a, b) -> count.get(b) - count.get(a));11        int[] res = new int[k];12        for (int i = 0; i < k; i++) {13            res[i] = unique.get(i);14        }15        return res;16    }17}

Hints

Hint 1

One pass with a hash map gives every frequency; the remaining question is how to pick the top k cheaply.

Hint 2

Sorting distinct values by count works but costs

O(n log n)

; look for structure in the frequencies themselves.

Hint 3

A count can never exceed n, so index buckets by count and walk them from the top down.

Edge Cases

k equal to the number of distinct values returns every distinct value.
Tied frequencies share one bucket, so buckets must hold lists rather than single values.
A single-element array answers with that element after one bucket placement.
When one value occurs n times, bucket n must exist; [7, 7, 7] with k = 1 returns [7].
A tie crossing the kth boundary is outside the unique-answer guarantee. Ties inside the answer are valid, as in Example 3.

Common Mistakes and Interview Tips

Sizing the bucket array as n instead of n + 1, which overflows when one value fills the whole array.
Storing one value per bucket and silently dropping values that tie on frequency.
Settling for the sort-based selection when the bounded frequencies allow a linear bucket walk.
Sorting by numeric value instead of frequency returns the wrong ranking, especially with negatives.
Allocating buckets as repeated references to one mutable list makes separate frequencies share entries; create a fresh list for every bucket.
Interview tip: distinguish n input positions from u distinct values, and explain that the unique answer permits tied leaders but excludes an ambiguous cutoff.

Key Takeaway

When the key range of a ranking is bounded by the input size, indexing buckets by rank selects the top entries in linear time.