Top K Frequent Elements problem and solution in Java and Python

“Top K Frequent Elements” is a classic FAANG problem. The goal is to find the k most frequent elements in an array. The most efficient solution uses a hash map + heap. I’ll show both Java and Python solutions.

Problem Statement

• Input: nums = [1,1,1,2,2,3], k = 2
• Output: [1, 2] (the two most frequent elements)

1️⃣ Java Solution

import java.util.*;

public class TopKFrequent {
    public static int[] topKFrequent(int[] nums, int k) {
        // Step 1: Count frequencies
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : nums) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Min-heap to keep top k elements
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap =
            new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));

        for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
            minHeap.add(entry);
            if (minHeap.size() > k) {
                minHeap.poll(); // remove element with smallest frequency
            }
        }

        // Step 3: Extract result
        int[] result = new int[k];
        int i = 0;
        while (!minHeap.isEmpty()) {
            result[i++] = minHeap.poll().getKey();
        }
        return result;
    }

    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(Arrays.toString(topKFrequent(nums, k))); // [2, 1]
    }
}

Time Complexity: O(n log k) Space Complexity: O(n)

2️⃣ Python Solution

from collections import Counter
import heapq

def top_k_frequent(nums, k):
    # Step 1: Count frequencies
    freq_map = Counter(nums)

    # Step 2: Min-heap to keep top k frequent
    min_heap = []

    for num, freq in freq_map.items():
        heapq.heappush(min_heap, (freq, num))
        if len(min_heap) > k:
            heapq.heappop(min_heap)

    # Step 3: Extract elements
    return [num for freq, num in min_heap]

# Example
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(top_k_frequent(nums, k))  # Output: [2, 1]

✅ Python tip: heapq is a min-heap by default. We push (freq, num) to always remove the least frequent element when heap size exceeds k.

⚡ Key Points for FAANG

1. HashMap / Counter: To count frequencies in O(n).
2. Heap (min-heap of size k): To efficiently track top k elements → O(n log k).
3. Alternative: Bucket sort method can solve in O(n) time if frequency range is small.
4. Always clarify order of output: problem may allow any order or require sorted by frequency.