Top K Frequent Elements

Problem

Given an integer array nums and an integer k, return the k most frequent elements in any order.

Constraints

• 1 ≤ nums.length ≤ 10⁵
• k is in [1, distinct count of nums]

Approach — Heaps / Top-K

This is a Heaps / Top-K problem. The idea: use a heap so the min, max, or top-k element stays reachable in O(log n) per operation. Work through the reference code below line by line, then re-derive it yourself in the editor — that's how the pattern sticks.

Complexity: O(n log k) time.

Solution code

Python

class Solution:
    def topKFrequent(self, nums, k):
        from collections import Counter
        c = Counter(nums)
        return [v for v, _ in c.most_common(k)]

Java

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1 — count each number.
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) count.merge(num, 1, Integer::sum);

        // Step 2 — min-heap of size k keyed on frequency: anything less
        // frequent than the root can never be top-K, so the heap always
        // holds the k best seen so far. Value-descending tie-break keeps
        // the output deterministic.
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) ->
            a[1] != b[1] ? Integer.compare(a[1], b[1])
                         : Integer.compare(b[0], a[0]));
        for (Map.Entry<Integer, Integer> e : count.entrySet()) {
            heap.offer(new int[]{ e.getKey(), e.getValue() });
            if (heap.size() > k) heap.poll();   // evict the weakest
        }

        // Step 3 — pop ascending, fill the answer from the back.
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) result[i] = heap.poll()[0];
        return result;

        // O(n) alternative: bucket-sort by frequency (index = count),
        // then walk the buckets from the highest frequency down.
    }
}

Practice it

Reading a solution isn't the same as being able to write it under pressure. Open this problem in the in-browser editor, hide the solution, and solve it from scratch — your code runs against real test cases instantly.