Top K Frequent Elements Problem
Top K Frequent Elements Problem
Given an integer array nums and an integer k, return the k most frequent elements within the array.
The test cases are generated such that the answer is always unique.
You may return the output in any order.
Output: [2,3]
Output: [7]
Constraints:
- 1 <= nums.length <= 10^4
- -1000 <= nums[i] <= 1000
- 1 <= k <= number of distinct elements in nums.
Top K Frequent Elements Solution
Recommendation – You should aim for a solution with O(n) time and O(n) space, where n is the size of the input array.
Hints for solving problems
Hint 1 :
A naive solution would be to count the frequency of each number and then sort the array based on each element’s frequency. After that, we would select the top k frequent elements. This would be an O(nlogn) solution. Though this solution is acceptable, can you think of a better way?
Hint 2:
Can you think of an algorithm which involves grouping numbers based on their frequency?
Hint 3:
Use the bucket sort algorithm to create n buckets, grouping numbers based on their frequencies from 1 to n. Then, pick the top k numbers from the buckets, starting from n down to 1.
There are mainly 3 approach to solve this problem
- Sorting Method
- Heap Method
- Bucket Sort Method
1. Sorting Method
This method counts the frequency of each element using a hash map, then sort the elements by frequency in descending order and pick the top K elements.
- Time complexity: O(nlog n)
- Space complexity: O(n)
Code
class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map count;
for (int num : nums) {
count[num]++;
}
vector> arr;
for (const auto& p : count) {
arr.push_back({p.second, p.first});
}
sort(arr.rbegin(), arr.rend());
vector res;
for (int i = 0; i < k; ++i) {
res.push_back(arr[i].second);
}
return res;
}
};
public class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
List arr = new ArrayList<>();
for (Map.Entry entry : count.entrySet()) {
arr.add(new int[] {entry.getValue(), entry.getKey()});
}
arr.sort((a, b) -> b[0] - a[0]);
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = arr.get(i)[1];
}
return res;
}
}
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
for num in nums:
count[num] = 1 + count.get(num, 0)
arr = []
for num, cnt in count.items():
arr.append([cnt, num])
arr.sort()
res = []
while len(res) < k:
res.append(arr.pop()[1])
return res
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
topKFrequent(nums, k) {
const count = {};
for (const num of nums) {
count[num] = (count[num] || 0) + 1;
}
const arr = Object.entries(count).map(([num, freq]) => [freq, parseInt(num)]);
arr.sort((a, b) => b[0] - a[0]);
return arr.slice(0, k).map(pair => pair[1]);
}
}
2. Heap Method
This method use a min-heap to store the K most frequent elements. Iterate through the frequency map, adding elements to the heap while maintaining its size at K.
- Time complexity: O(nlogk)
- Space complexity: O(n+k)
where n is the length of the array and k is the number of top frequent elements.
Code
class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map count;
for (int num : nums) {
count[num]++;
}
priority_queue, vector>, greater>> heap;
for (auto& entry : count) {
heap.push({entry.second, entry.first});
if (heap.size() > k) {
heap.pop();
}
}
vector res;
for (int i = 0; i < k; i++) {
res.push_back(heap.top().second);
heap.pop();
}
return res;
}
};
public class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
PriorityQueue heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (Map.Entry entry : count.entrySet()) {
heap.offer(new int[]{entry.getValue(), entry.getKey()});
if (heap.size() > k) {
heap.poll();
}
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = heap.poll()[1];
}
return res;
}
}
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
for num in nums:
count[num] = 1 + count.get(num, 0)
heap = []
for num in count.keys():
heapq.heappush(heap, (count[num], num))
if len(heap) > k:
heapq.heappop(heap)
res = []
for i in range(k):
res.append(heapq.heappop(heap)[1])
return res
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
topKFrequent(nums, k) {
const count = {};
for (const num of nums) {
count[num] = (count[num] || 0) + 1;
}
const heap = new MinPriorityQueue(x => x[1]);
for(const [num, cnt] of Object.entries(count)){
heap.enqueue([num, cnt]);
if (heap.size() > k) heap.dequeue();
}
const res = [];
for(let i = 0; i < k; i++) {
const [num, cnt] = heap.dequeue();
res.push(num)
}
return res;
}
}
3. Bucket Sort Method
This method group elements by their frequency in buckets (arrays), then iterate through the buckets from highest to lowest frequency to extract the top K elements.
- Time complexity: O(n)
- Space complexity: O(n)
Code
class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map count;
vector> freq(nums.size() + 1);
for (int n : nums) {
count[n] = 1 + count[n];
}
for (const auto& entry : count) {
freq[entry.second].push_back(entry.first);
}
vector res;
for (int i = freq.size() - 1; i > 0; --i) {
for (int n : freq[i]) {
res.push_back(n);
if (res.size() == k) {
return res;
}
}
}
return res;
}
};
public class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map count = new HashMap<>();
List[] freq = new List[nums.length + 1];
for (int i = 0; i < freq.length; i++) {
freq[i] = new ArrayList<>();
}
for (int n : nums) {
count.put(n, count.getOrDefault(n, 0) + 1);
}
for (Map.Entry entry : count.entrySet()) {
freq[entry.getValue()].add(entry.getKey());
}
int[] res = new int[k];
int index = 0;
for (int i = freq.length - 1; i > 0 && index < k; i--) {
for (int n : freq[i]) {
res[index++] = n;
if (index == k) {
return res;
}
}
}
return res;
}
}
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
freq = [[] for i in range(len(nums) + 1)]
for num in nums:
count[num] = 1 + count.get(num, 0)
for num, cnt in count.items():
freq[cnt].append(num)
res = []
for i in range(len(freq) - 1, 0, -1):
for num in freq[i]:
res.append(num)
if len(res) == k:
return res
class Solution {
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
topKFrequent(nums, k) {
const count = {};
const freq = Array.from({ length: nums.length + 1 }, () => []);
for (const n of nums) {
count[n] = (count[n] || 0) + 1;
}
for (const n in count) {
freq[count[n]].push(parseInt(n));
}
const res = [];
for (let i = freq.length - 1; i > 0; i--) {
for (const n of freq[i]) {
res.push(n);
if (res.length === k) {
return res;
}
}
}
}
}
