Top K Frequent Elements

The problem

Given a list of integers nums and a number k, return the k values that appear most often, in any order. The input is chosen so that the answer is unique: every value in the answer appears more often than every value left out.

What to write

function solve(nums: number[], k: number): number[]

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

Output
[1,2]

Input
nums = [1]
k = 1

Output
[1]

Constraints

The set of k most frequent values is unique; 1 ≤ k ≤ distinct values.

Hints

Each hint gives away a little more. Open one only when you need it.

1. Hint 1: Use the constraints

   The answer depends only on how often each value appears, not on where it sits in the list. You are also promised that every value in the answer appears more often than every value left out, so there is exactly one right set of values.

2. Hint 2: Ask a smaller question

   Take the list 1, 1, 1, 2, 2, 3 and pick its two most frequent values by hand. What did you have to work out about each value before you could choose?

3. Hint 3: Name the pattern

   The work splits in two: first count how often each value appears, with a hash map from value to count, then choose the largest counts. The first half is frequency counting. Read the lesson on frequency counting.

4. Hint 4: State the invariant

   After the counting pass, the map holds every different value exactly once, with its exact number of appearances. Nothing else about the list matters from then on.

5. Hint 5: Sketch the pseudocode

   Count each value in a map. Take the map's keys and sort them by their counts, largest first. Return the first k keys.

Solution

From here on the page gives the method away. If you are still solving, go back to the hints.

Approach

Count occurrences, sort distinct values by frequency, and take the first k.

The slow way

For each different value, walk the whole list again to count it, then pick the largest counts. It is correct, but a list of n values that are all different costs n full passes, which is n × n steps.

The insight

One pass is enough to count everything if you keep a running count for each value in a hash map. After that the list itself is no longer needed: sorting the different values by their counts puts the answer in front.

Step by step

1. Count how many times each value appears. A hash map keeps one running count per value, so the whole list is counted in a single pass.
2. Order the different values from most to least frequent. Sorting by count puts the most frequent values at the front. Only the different values are sorted, not the whole list.
3. The first k of them are the answer. After sorting, the most frequent values are the first ones. The problem promises that no value left out ties with one that is kept, so that set is unique.

The same numbered steps are the comments in each solution.

function solve(nums, k) {
  // 1. Count how many times each value appears
  const counts = new Map();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
  // 2. Order the different values from most to least frequent
  const ordered = [...counts.keys()].sort(
    (a, b) => counts.get(b) - counts.get(a),
  );
  // 3. The first k of them are the answer
  return ordered.slice(0, k);
}

function solve(nums: number[], k: number): number[] {
  // 1. Count how many times each value appears
  const counts = new Map<number, number>();
  for (const n of nums) counts.set(n, (counts.get(n) || 0) + 1);
  // 2. Order the different values from most to least frequent
  const ordered = [...counts.keys()].sort(
    (a, b) => counts.get(b)! - counts.get(a)!,
  );
  // 3. The first k of them are the answer
  return ordered.slice(0, k);
}

def solve(nums, k):
    # 1. Count how many times each value appears
    counts = {}
    for num in nums:
        counts[num] = counts.get(num, 0) + 1
    # 2. Order the different values from most to least frequent
    ordered = sorted(counts, key=counts.get, reverse=True)
    # 3. The first k of them are the answer
    return ordered[:k]

Example 1, traced

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

Output
[1,2]

Why it works

The map's counts are exact, because every element adds one to its own value's count. Sorting those counts from largest to smallest places the most frequent values first, and the problem promises that the top k form a unique set.

Time and space

Time O(n + u log u), extra space O(u). Counting reads each of the n values once. Sorting the u different values takes about u log u steps: O(n + u log u) time. The map and the sorted list hold one entry per different value, so the space is O(u).

n and m are input sizes, h is a tree's height, V and E are a graph's vertices and edges. The bounds describe this reference solution.

Watch out

• Sort the different values, not the original list. Sorting the list by frequency repeats each value as many times as it appears.
• Sort from the largest count to the smallest. The other direction returns the rarest values instead of the most frequent.

Pattern

Frequency counting. Builds on Valid Anagram.

Keep going