Top K Frequent Elements

1 min readUpdated 30 June 2025

Problem Statement

In the given problem, we are asked to find the k most frequent elements from an integer array nums. The elements in the output can be in any order, but they must be the top k elements in terms of frequency within the array. This problem examines our ability to track and sort elements based on the frequency of occurrence.

Examples

Example 1

Input:

EXAMPLE_ENTITY

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

Output:

EXAMPLE_ENTITY

[1,2]

Example 2

Input:

EXAMPLE_ENTITY

nums = [1], k = 1

Output:

EXAMPLE_ENTITY

[1]

Constraints

1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Approach and Intuition

To solve the problem of finding the k most frequent elements in the array, you can follow these general steps:

Count Frequency of Each Element:
Use a hash map to store the frequency of each element in the array. The key in the hash map would be the element from the array, and the value would be the count of how often it appears.
Sort Elements by Frequency:
Convert the frequency hash map into a list of (element, frequency) pairs and sort this list by frequency in descending order.
Extract Top k Elements:
Once sorted, the first k elements of this list will represent the k most frequent elements. Extract these and return them.

Special Scenario Handling:
- For an array with only one element or when k equals 1, the logic simplifies as the output will be the element itself, irrespective of its count.

These steps are optimal given the constraints, especially when considering the possible size of the input array and the range of elements it can include. This problem ensures that a unique answer is always possible, simplifying some aspects of the implementation.

Solutions

CPP
class Solution {
private:
    vector<int> distinctElements;
    unordered_map<int, int> frequencyMap;
    
public:
    int rearrange(int start, int end, int pivot_idx) {
        int pivot_freq = frequencyMap[distinctElements[pivot_idx]];
            
        // Move pivot to end
        swap(distinctElements[pivot_idx], distinctElements[end]);
    
        // Organize less frequent to the left
        int store_idx = start;
        for (int i = start; i <= end; i++) {
            if (frequencyMap[distinctElements[i]] < pivot_freq) {
                swap(distinctElements[store_idx], distinctElements[i]);
                store_idx++;
            }
        }
    
        // Restore pivot to its proper position
        swap(distinctElements[end], distinctElements[store_idx]);
    
        return store_idx;
    }
    
    void selectK(int start, int end, int k_least) {
        if (start == end) return;
    
        // Random pile index for partitioning
        int pivot_idx = start + rand() % (end - start + 1);
            
        // Find the pivot's sorted index
        pivot_idx = rearrange(start, end, pivot_idx);
    
        // If pivot is already in the correct spot
        if (k_least == pivot_idx) {
            return;
        } else if (k_least < pivot_idx) {
            selectK(start, pivot_idx - 1, k_least);
        } else {
            selectK(pivot_idx + 1, end, k_least);
        }
    }
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Counting the frequency of each number
        for (int value : nums) {
            frequencyMap[value]++;
        }
    
        // Collect distinct numbers
        int count = frequencyMap.size();
        for (auto& pair : frequencyMap) {
            distinctElements.push_back(pair.first);
        }
    
        // Partial sort to find the kth most frequent element
        selectK(0, count - 1, count - k);
            
        // Retrieve the top k frequent elements
        vector<int> result(k);
        copy(distinctElements.begin() + count - k, distinctElements.end(), result.begin());
        return result;
    }
};
Powered by Vultr AgentBeta

The provided C++ code solves the problem of finding the top K frequent elements in an array. It does this using a combination of a hash map and a quickselect algorithm, a variation inspired by quicksort. Here's a comprehensive overview of the solution:

Data Structures:
- vector<int> distinctElements - holds unique elements from the input array.
- unordered_map<int, int> frequencyMap - maps each element to its frequency in the input array.
Initial Setup:
- Populate frequencyMap where each key corresponds to an integer from the input and its value is the frequency of that integer.
- Extract the keys (distinct elements) from frequencyMap into distinctElements.
Quickselect Algorithm:
- The rearrange method is a helper function that partitions elements around a pivot element based on their frequency. Elements less frequent than the pivot come before it, and more frequent elements come after.
- The selectK method utilizes the rearrange method to find the correct position of the k-th most frequent element (count - k where count is the number of distinct elements). It recursively partitions the array to position the k-th largest frequency at its correct index in sorted order.
Finding the Top K Elements:
- After selectK positions the k-th most frequent element correctly, the top K elements can be found at the end of the distinctElements array.
- A subvector is then created from the last K positions of distinctElements, which are the most frequent elements.

This implementation efficiently groups the K most frequent elements without fully sorting the entire unique elements list, leveraging randomness for pivot selection which ensures good average performance. The final solution uses O(N) space due to the additional data structures and has an average time complexity of O(N) due to the quickselect process, though the worst case can degrade to O(N^2).

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.

Top K Frequent Elements

1 min readUpdated 30 June 2025

Problem Statement

Examples

Example 1

Input:

EXAMPLE_ENTITY

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

Output:

EXAMPLE_ENTITY

[1,2]

Example 2

Input:

EXAMPLE_ENTITY

nums = [1], k = 1

Output:

EXAMPLE_ENTITY

[1]

Constraints

1 <= nums.length <= 105
-104 <= nums[i] <= 104
k is in the range [1, the number of unique elements in the array].
It is guaranteed that the answer is unique.

Approach and Intuition

To solve the problem of finding the k most frequent elements in the array, you can follow these general steps:

Count Frequency of Each Element:
Use a hash map to store the frequency of each element in the array. The key in the hash map would be the element from the array, and the value would be the count of how often it appears.
Sort Elements by Frequency:
Convert the frequency hash map into a list of (element, frequency) pairs and sort this list by frequency in descending order.
Extract Top k Elements:
Once sorted, the first k elements of this list will represent the k most frequent elements. Extract these and return them.

Special Scenario Handling:
- For an array with only one element or when k equals 1, the logic simplifies as the output will be the element itself, irrespective of its count.

Solutions

CPP
class Solution {
private:
    vector<int> distinctElements;
    unordered_map<int, int> frequencyMap;
    
public:
    int rearrange(int start, int end, int pivot_idx) {
        int pivot_freq = frequencyMap[distinctElements[pivot_idx]];
            
        // Move pivot to end
        swap(distinctElements[pivot_idx], distinctElements[end]);
    
        // Organize less frequent to the left
        int store_idx = start;
        for (int i = start; i <= end; i++) {
            if (frequencyMap[distinctElements[i]] < pivot_freq) {
                swap(distinctElements[store_idx], distinctElements[i]);
                store_idx++;
            }
        }
    
        // Restore pivot to its proper position
        swap(distinctElements[end], distinctElements[store_idx]);
    
        return store_idx;
    }
    
    void selectK(int start, int end, int k_least) {
        if (start == end) return;
    
        // Random pile index for partitioning
        int pivot_idx = start + rand() % (end - start + 1);
            
        // Find the pivot's sorted index
        pivot_idx = rearrange(start, end, pivot_idx);
    
        // If pivot is already in the correct spot
        if (k_least == pivot_idx) {
            return;
        } else if (k_least < pivot_idx) {
            selectK(start, pivot_idx - 1, k_least);
        } else {
            selectK(pivot_idx + 1, end, k_least);
        }
    }
    
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Counting the frequency of each number
        for (int value : nums) {
            frequencyMap[value]++;
        }
    
        // Collect distinct numbers
        int count = frequencyMap.size();
        for (auto& pair : frequencyMap) {
            distinctElements.push_back(pair.first);
        }
    
        // Partial sort to find the kth most frequent element
        selectK(0, count - 1, count - k);
            
        // Retrieve the top k frequent elements
        vector<int> result(k);
        copy(distinctElements.begin() + count - k, distinctElements.end(), result.begin());
        return result;
    }
};
Powered by Vultr AgentBeta

Data Structures:
- vector<int> distinctElements - holds unique elements from the input array.
- unordered_map<int, int> frequencyMap - maps each element to its frequency in the input array.
Initial Setup:
- Populate frequencyMap where each key corresponds to an integer from the input and its value is the frequency of that integer.
- Extract the keys (distinct elements) from frequencyMap into distinctElements.
Quickselect Algorithm:
- The rearrange method is a helper function that partitions elements around a pivot element based on their frequency. Elements less frequent than the pivot come before it, and more frequent elements come after.
- The selectK method utilizes the rearrange method to find the correct position of the k-th most frequent element (count - k where count is the number of distinct elements). It recursively partitions the array to position the k-th largest frequency at its correct index in sorted order.
Finding the Top K Elements:
- After selectK positions the k-th most frequent element correctly, the top K elements can be found at the end of the distinctElements array.
- A subvector is then created from the last K positions of distinctElements, which are the most frequent elements.

More to Explore

Tech Talk: Running a Self-Improving AI Agent with Hermes on Vultr

Tech Talk: Implementing Fine-Grained Access Control with Vultr IAM

Tech Talk: Getting Started with Vultr IAM

Tech Talk: Simplifying Zero-Trust Networking with NetBird on Vultr Marketplace

0 Comments

Start the conversation

Be the first to comment and share your perspective with the community.