Top K Frequent Elements

Medium Heaps Composite comparator Original on LeetCode

Top K Frequent Elements is a medium heaps problem solved with the composite comparator pattern. The best approach, bucket sort by frequency (o(n)), runs in O(n) time and O(n) space. Below are 3 approaches in Java, Python, C++ and JavaScript, from count, then sort by frequency up.

Problem

Return the k most frequent values in an integer array, in any order. The answer is guaranteed to be unique.

Examples

Example 1

Input
nums = [4, 4, 4, 1, 1, 7], k = 2
Output
[4, 1]

Example 2

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

Constraints

  • 1 <= nums.length <= 10^5; the answer is unique.
  • Better than O(n log n).

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (2 examples, or your own). Submit also runs 8 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Count, then sort by frequencyO(n log n)O(n)
Min-heap of size k (comparator on frequency)O(n log k)O(n)
Bucket sort by frequency (O(n))O(n)O(n)

1Count, then sort by frequency

TimeO(n log n)
SpaceO(n)

Count with a map, sort the distinct values by count descending, take the first k.

  1. Count; sort entries by value descending; take k keys.
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        List<Integer> keys = new ArrayList<>(count.keySet());
        keys.sort((a, b) -> count.get(b) - count.get(a));
        int[] out = new int[k];
        for (int i = 0; i < k; i++) out[i] = keys.get(i);
        return out;
    }
}

2Min-heap of size k (comparator on frequency)

TimeO(n log k)
SpaceO(n)

Push (value, count) pairs into a min-heap ordered by count and pop when it exceeds k. What stays are the k most frequent.

  1. Count with a map.
  2. Heap comparator: (a, b) -> a[1] - b[1]; offer each entry, poll when size > k.
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            heap.offer(new int[] { e.getKey(), e.getValue() });
            if (heap.size() > k) heap.poll();
        }
        int[] out = new int[k];
        for (int i = k - 1; i >= 0; i--) out[i] = heap.poll()[0];
        return out;
    }
}

3Bucket sort by frequency (O(n))

TimeO(n)
SpaceO(n)

A count is between 1 and n, so put each value into bucket[count]. Walk buckets from high to low until you have k values.

  1. bucket[c] = list of values with count c.
  2. For c from n down to 1, add values until k are collected.
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        List<List<Integer>> bucket = new ArrayList<>();
        for (int i = 0; i <= nums.length; i++) bucket.add(new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : count.entrySet()) bucket.get(e.getValue()).add(e.getKey());
        int[] out = new int[k];
        int j = 0;
        for (int c = nums.length; c > 0 && j < k; c--)
            for (int v : bucket.get(c)) if (j < k) out[j++] = v;
        return out;
    }
}

Edge cases to test

  • k equals the number of distinct values
  • Negative values

Hints

Hint 1

Count frequencies, then either keep a size-k heap ordered by frequency (a composite comparator) or bucket values by their count.

FAQ

What is the best time complexity for Top K Frequent Elements?

Bucket sort by frequency (O(n)) runs in O(n) time and O(n) extra space.

Which pattern does Top K Frequent Elements use?

It is a heaps problem that uses the composite comparator pattern. Other problems with the same pattern: Design Task Manager, Rank Teams by Votes, Design Movie Rental System.

Is there a brute force solution for Top K Frequent Elements?

Yes. Count, then sort by frequency takes O(n log n) time and O(n) space. Count with a map, sort the distinct values by count descending, take the first k.

Which edge cases should I test for Top K Frequent Elements?

k equals the number of distinct values; Negative values.