Understanding the Problem

You are given an integer array and a number K.
Your task is to return the K elements that appear the most number of times in the array.

Example:

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

Here:
1 occurs 3 times
2 occurs 2 times
3 occurs 1 time

The top two most frequent elements are 1 and 2.

You do not need to return the elements in sorted order.

The array can be very large, so the solution must be better than O(n log n).

---

Approach (Explained in Simple Language)

To solve this problem efficiently, follow these steps.

1. Count the frequency of each number

We use a HashMap where:
key = number in the array
value = how many times it appears

This step is O(n).

Example: for [1,1,1,2,2,3]
Map = {1=3, 2=2, 3=1}

2. Use a min-heap (priority queue) of size K

We want only the top K frequent numbers.

A min-heap always removes the element with the smallest frequency first.
So we push each (number, frequency) into a min-heap.

When the heap size becomes greater than K, we remove the smallest frequency element.

This ensures the heap always stores only the K most frequent elements.

Time complexity: O(n log K).
Since K is small, this is efficient.

3. Extract the K elements from the heap

The heap now contains exactly the K numbers with the highest frequency.
We read them and return them as the answer.

---

Java Code

import java.util.*;

public class TopKFrequentElements {

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

        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<int[]> minHeap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[1], b[1])
        );

        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            minHeap.offer(new int[]{entry.getKey(), entry.getValue()});
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        int[] result = new int[k];
        int index = 0;
        while (!minHeap.isEmpty()) {
            result[index++] = minHeap.poll()[0];
        }

        return result;
    }

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

---

Dry Run

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

Step 1: Build frequency map

Traverse nums:
1 → freq 1
1 → freq 2
1 → freq 3
2 → freq 1
2 → freq 2
3 → freq 1

Final frequencyMap =
{1=3, 2=2, 3=1}

Step 2: Push into min-heap

We process each map entry one by one.

Insert number 1 (freq 3)

Heap =
[ (1,3) ]
Size is 1, which is ≤ k, so continue.

Insert number 2 (freq 2)

Heap =
[ (2,2), (1,3) ]
(2,2) is root because it has smaller frequency.
Size is 2, equal to k. Continue.

Insert number 3 (freq 1)

Push (3,1):

Heap becomes:
[ (3,1), (1,3), (2,2) ]

Size is 3 which is > k.
So we remove smallest frequency element.

Remove root → (3,1)

Heap now contains:
[ (2,2), (1,3) ]

These are the top 2 frequent so far.

Step 3: Build result array

Pop elements from heap:

First pop: (2,2)
result = [2]

Second pop: (1,3)
result = [2, 1]

Output order may vary. Both [1,2] or [2,1] are correct.

Final Answer: [2, 1] or [1, 2]