Top K Frequent Elements

Problem Statement

You’re a data analyst with an array of integers. Your mission: find the k most frequent elements. This medium-level hashing challenge is a popularity contest—combine maps and heaps to crown the winners!

Example

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

Output: [1, 2] (1 appears 3x, 2 appears 2x)

Input: nums = [1], k = 1

Output: [1]

Input: nums = [4, 1, -1, 2, -1], k = 2

Output: [-1, 4] (-1 appears 2x, 4 appears 1x, arbitrary order)

Code

public class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map freq = new HashMap<>();
        for (int num : nums) freq.put(num, freq.getOrDefault(num, 0) + 1);
        PriorityQueue pq = new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b));
        for (int num : freq.keySet()) {
            pq.offer(num);
            if (pq.size() > k) pq.poll();
        }
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) result[i] = pq.poll();
        return result;
    }
}
            

from collections import Counter
import heapq
def top_k_frequent(nums, k):
    freq = Counter(nums)
    return heapq.nlargest(k, freq.keys(), key=freq.get)
            

function topKFrequent(nums, k) {
    let freq = new Map();
    for (let num of nums) freq.set(num, (freq.get(num) || 0) + 1);
    return Array.from(freq.entries())
        .sort((a, b) => b[1] - a[1])
        .slice(0, k)
        .map(([num]) => num);
}
            

Explanation

• Hashing Insight: Count frequencies with a map, then extract top k.
• Flow: Build freq map, use heap or sorting to get k most frequent.
• Example Walkthrough: [1,1,1,2,2,3] → freq={1:3,2:2,3:1}, top 2=[1,2].
• Python Elegance: heapq.nlargest simplifies heap usage.
• Trade-off: Heap is O(n log k), sorting is O(n log n)—choose based on k.

Note