Top K Frequent Elements

The problem

You are given an array nums of whole numbers (call its length n) and a number top_count. Return the top_count values that appear most often in nums. You may return them in any order.

The input is chosen so that the answer is unique: there is never a tie at the edge of the top top_count.

Example 1

Input: nums = [4, 1, 4, 2, 1, 4, 3], top_count = 2

Output: [4, 1]

4 appears 3 times and 1 appears 2 times. 2 and 3 appear only once each.

nums

40114223144536

number	4	1	2	3
count	3	2	1	1

Example 2

Input: nums = [9], top_count = 1

Output: [9]

There is only one value, so it is the most frequent.

Example 3

Input: nums = [5, 6, 5, 6, 7, 6], top_count = 1

Output: [6]

6 appears 3 times, 5 appears twice and 7 once.

Constraints

• 1 ≤ n ≤ 100,000
• −10,000 ≤ nums[i] ≤ 10,000
• top_count is between 1 and the number of different values in nums. Below, k is top_count, and m is that number of different values.
• The answer is unique.

Clarifying questions

Does the order of the result matter?

No. [4, 1] and [1, 4] are both correct.

What if two values tie for the last spot?

That cannot happen here. The input promises a unique answer.

Can top_count be larger than the number of different values?

No. top_count is at most the number of different values.

Is there a time goal?

Yes. The follow-up asks for better than O(n log n), which rules out a full sort as the final answer.

Spot the pattern

“The k most frequent” is a top-k question, and every top-k question starts with a count in a hash map. The twist is in the counts themselves: a value can appear at most n times. Numbers in a small, known range can be used as list positions, and that lets us skip sorting.

Solutions

Count and sortO(n log n)Bucket by countO(n)

Show all

A heap that keeps the k most frequent values sits between these two, at O(n log k). The bucket method is faster and simpler, so it is the one shown.

Count and sort O(n log n)

The idea

First count how often each value appears, with a hash map from value to count. Then sort the different values by their count, highest first. The first top_count values are the answer.

This is correct and short. The cost is the sort: with all values different, there are n of them to sort.

Walkthrough

nums

40114223144536

1. count = {}
2. for number in nums:
3. count[number] = count.get(number, 0) + 1
4. order = sorted(count, by count, high first)
5. return order[:top_count]

Step 1: count how often each number appears. Step 2: sort the numbers by count and keep the first top_count = 2.

← BackStep →Play1 / 11

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Count, then sort: sort the distinct numbers by how often they appear.
    // Counting is O(n); sorting m distinct numbers is O(m log m), up to O(n log n).
    public int[] topKFrequent(int[] nums, int topCount) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int number : nums) count.merge(number, 1, Integer::sum);
        List<Integer> order = new ArrayList<>(count.keySet());
        // Highest count first, so the answer is the front of the list.
        order.sort((first, second) -> count.get(second) - count.get(first));
        int[] result = new int[topCount];
        for (int i = 0; i < topCount; i++) result[i] = order.get(i);
        return result;
    }
}

Big O

Time O(n log n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   Two lines do the work. The count line runs once per number and costs 1 step on average. The sort is one line, but sorting m values takes about m × log₂ m steps.

   1. count = {}
   2. for number in nums:
   3. count[number] = count.get(number, 0) + 1
   4. order = sorted(count, by count, high first)
   5. return order[:top_count]

2. 2 Count the runs on Example 1

   Example 1 has 7 numbers and 4 different values. Counting takes 7 steps. Sorting 4 values takes about 4 × log₂ 4 = 8 steps.

   part	count	sort
   steps on Example 1	7 (one per number)	4 × log₂ 4 = 8

3. 3 Write the count for any n

   With n numbers and m different values:

   n + m log m

   Check it with Example 1: 7 + 4 × 2 = 15. In the worst case every value is different, so m = n and the count is n + n log n.

4. 4 Keep only the part that grows fastest

   • Use the worst case, m = n. Big O plans for the hardest input.
   • Drop the + n. n log n always ends up bigger than n, so the sort is the biggest part.

   What is left is n log n.

   So the time is O(n log n).

5. S Space: count the extra memory the same way

   The count map holds m entries and the sorted list holds m values. In the worst case m = n, so the space is O(n).

   count (m entries)order (m numbers)

Bucket by count O(n)

The idea

We do not need the values in full sorted order. We only need them grouped by count. And a count is always a whole number from 1 to n.

So make a list of buckets, numbered 0 to n. Put each value into the bucket that matches its count: a value that appears 3 times goes into bucket 3. The bucket number is the position, so there is nothing to sort. Then walk the buckets from n down to 1 and collect values until you have top_count.

Why it never misses the answer: we visit counts from highest to lowest, so every value we take appears at least as often as every value we have not reached yet.

Walkthrough

nums

40114223144536

number	4	1	2	3
count	3	2	1	1

1. count = {}
2. for number in nums:
3. count[number] = count.get(number, 0) + 1
4. buckets = [[] for _ in range(len(nums) + 1)]
5. for number, frequency in count.items():
6. buckets[frequency].append(number)
7. result = []
8. for frequency in range(len(nums), 0, -1):
9. for number in buckets[frequency]:
10. result.append(number)
11. if len(result) == top_count:
12. return result

Count each number first, with a hash map: 4 appears 3 times, 1 twice, 2 and 3 once each.

← BackStep →Play1 / 12

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Bucket by count: a count is between 1 and n, so it can be a list index.
    // Count, fill buckets, scan buckets: three passes, so O(n) time and O(n) memory.
    public int[] topKFrequent(int[] nums, int topCount) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int number : nums) count.merge(number, 1, Integer::sum);
        // buckets[frequency] holds every number that appears exactly frequency times.
        List<List<Integer>> buckets = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            buckets.get(entry.getValue()).add(entry.getKey());
        }
        int[] result = new int[topCount];
        int filled = 0;
        // Walk from the highest possible count down, so the most frequent come first.
        for (int frequency = nums.length; frequency >= 1; frequency--) {
            for (int number : buckets.get(frequency)) {
                result[filled++] = number;
                if (filled == topCount) return result;
            }
        }
        return result;
    }
}

Big O

Time O(n)Space O(n)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   There are three loops, one after the other. The first counts each number. The second drops each different value into its bucket. The third walks the buckets from n down and takes values. Each run of each loop is 1 step.

   1. count = {}
   2. for number in nums:
   3. count[number] = count.get(number, 0) + 1
   4. buckets = [[] for _ in range(len(nums) + 1)]
   5. for number, frequency in count.items():
   6. buckets[frequency].append(number)
   7. result = []
   8. for frequency in range(len(nums), 0, -1):
   9. for number in buckets[frequency]:
   10. result.append(number)
   11. if len(result) == top_count:
   12. return result

2. 2 Count the runs on Example 1

   Example 1 has 7 numbers and 4 different values. Counting runs 7 times. Filling the buckets runs 4 times. The scan checks buckets 7, 6, 5, 4, 3 and 2, which is 6 runs, and stops with k = 2 values.

   7 + 4 + 6 = 17 runs.

   loop	count nums	fill buckets	scan buckets
   runs on Example 1	7	4	6 (7 down to 2)

   total

   7 + 4 + 6 = 17

3. 3 Write the count for any n

   In the worst case the scan checks every bucket from n down to 1 and takes every value:

   n + m + (n + m) ≤ n + n + 2n = 4n

   Check it with Example 1: 17 is below 4 × 7 = 28, because the scan stopped early.

4. 4 Keep only the part that grows fastest

   Drop the 4. A fixed number of passes over the input does not change how the work grows. When n doubles, 4n doubles too. What is left is n.

   So the time is O(n).

5. S Space: count the extra memory the same way

   The count map holds up to n entries. The buckets are n + 1 lists, and together they hold each value once. The result holds k values. All of these are at most n, so the space is O(n).

   count (m entries)buckets (n + 1 lists)result (top_count numbers)

Common mistake

Making only k buckets

The bucket index is a count, not a rank. A value can appear up to n times, so you need n + 1 buckets. With only k buckets, a value with a high count has nowhere to go.

Tested at the limits

2,000 random arrays of 1 to 12 numbers from a tiny range, so ties are common, and the answer is always unique. The count and sort and the bucket by count gave the same numbers every time.

Largest inputs	Result
100,000 numbers (the most allowed), with every allowed value present, asking for the top 1,000. Bucket by count.	0.02 s, and about 7 MB of extra memory: a count for 20,001 values and 100,001 buckets, which is the O(n) space.