Top K Frequent Elements

leetcode.com

Problem Statement

Given an integer array and an integer k, return the k most frequent elements.

Brute Force Intuition

Count frequencies.

Sort elements based on frequency.

Return first K elements.

Complexity

Time Complexity: O(N log N)
Space Complexity: O(N)

Moving Towards the Optimal Approach

We only need:

Top K Frequencies

Not the entire sorted order.

Use:

Min Heap of Size K

Pattern Recognition

Whenever you see:

Top K
K Largest
K Smallest

Think:

Heap

Optimal Approach

Step 1:

Count frequencies.

HashMap<Integer,Integer>

Step 2:

Maintain Min Heap ordered by frequency.

If heap size exceeds K:

pq.poll();

At the end:

Heap contains K most frequent elements.

Optimal Java Solution

class Solution {

    public int[] topKFrequent(
        int[] nums,
        int k) {

        HashMap<Integer,Integer> map =
            new HashMap<>();

        for (int num : nums) {

            map.put(
                num,
                map.getOrDefault(num, 0) + 1
            );
        }

        PriorityQueue<Integer> pq =
            new PriorityQueue<>(
                (a,b) ->
                map.get(a) - map.get(b)
            );

        for (int key : map.keySet()) {

            pq.add(key);

            if (pq.size() > k)
                pq.poll();
        }

        int[] ans =
            new int[k];

        int idx = 0;

        while (!pq.isEmpty()) {

            ans[idx++] =
                pq.poll();
        }

        return ans;
    }
}

Dry Run

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

k = 2

Frequency Map:

Heap:

removed.

Remaining:

1
2

Answer:

[1,2]

Complexity Analysis

Metric	Complexity
Time	O(N log K)
Space	O(N)

Interview One-Liner

Count frequencies using HashMap and maintain a Min Heap of size K to keep only the most frequent elements.