Problem Overview

You are given an array nums and an integer k.
Your task is to return the k elements that appear the most often in the array.

Example input:

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

Frequencies:

• 1 appears 4 times

• 2 appears 4 times

• 3 appears 2 times

The two most frequent elements are:

[1, 2]

Approach 1: Using Sorting (O(n log n))

Steps:

1. Build a frequency map (number → count).

2. Put all pairs (number, count) into a vector.

3. Sort the vector by count in descending order.

4. Take the first k elements.

Why O(n log n)?
Because the sorting step requires log time as the number of unique elements increases.

This method is simple but not optimal for very large input sizes.

Approach 2: Bucket Counting (O(n))

This method avoids sorting completely.

Steps:

1. Build a frequency map.

2. Create a structure where index = frequency.
   Example:
   bucket[4] = {1, 2} because both appear 4 times.

3. Start from the highest frequency and collect numbers.

4. Stop when you collect k elements.

Why O(n)?
Counting + bucket creation + scanning are all linear operations.

This approach satisfies the follow-up requirement:
Must be better than O(n log n).

Final Code (O(n) Bucket Approach)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;

        vector<vector<int>> bucket(nums.size() + 1);
        for (auto &p : freq) bucket[p.second].push_back(p.first);

        vector<int> result;
        for (int i = bucket.size() - 1; i >= 0 && result.size() < k; i--) {
            for (int num : bucket[i]) {
                result.push_back(num);
                if (result.size() == k) break;
            }
        }
        return result;
    }
};