Problem Statement:
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Examples:
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output:[1,2]
Example 2:
Input:stones = [1], k = 1
Output:[1]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Follow up Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
Approach
- Count frequencies – Traverse the array and store the frequency of each element in a hash map.
(O(n)). - Maintain a Min Heap of size k –
- Push each (value, frequency) pair into the heap
(O(log k)). - f heap size exceeds
k, pop the smallest frequency element.
- Push each (value, frequency) pair into the heap
- Extract result – Convert the heap elements to an array of values and return them.
(O(k)).
Time Complexity:
Time Complexity = O(n log k)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: arr = [1, 1, 1, 2, 2, 3], k = 2
Step 1: Create frequency map
i = 0 → arr[0] = 1 → map = {1: 1}
i = 1 → arr[1] = 1 → map = {1: 2}
i = 2 → arr[2] = 1 → map = {1: 3}
i = 3 → arr[3] = 2 → map = {1: 3, 2: 1}
i = 4 → arr[4] = 2 → map = {1: 3, 2: 2}
i = 5 → arr[5] = 3 → map = {1: 3, 2: 2, 3: 1}
Step 2: Add to MinPriorityQueue (pq) and maintain size ≤ k
key = '1' → push({val: 1, freq: 3}) → pq = [ (1, freq=3) ]
key = '2' → push({val: 2, freq: 2}) → pq = [ (2,2), (1,3) ] // ordered by freq
key = '3' → push({val: 3, freq: 1}) → pq = [ (3,1), (1,3), (2,2) ]
pq.size() = 3 > k → pop smallest → pop (3,1)
pq = [ (2,2), (1,3) ]
Step 3: Convert pq to array
pq.toArray() = [ (2,2), (1,3) ]
Map to values: [2, 1]
Output: [2, 1]
Explanation: The two most frequent elements are 2 (appears twice) and 1 (appears thrice), returned in order of increasing frequency.
var topKFrequent = function(arr, k) {
// create a map of freq 0(n)
let map = {};
for(let i=0; i < arr.length; ++i) {
if(!map[arr[i]]) map[arr[i]] = 0;
++map[arr[i]];
}
// add elements to MinPQ and restrict size tok O(n log
let pq = new MinPriorityQueue(x => x.freq);
for(key in map) {
pq.push({val: key, freq: map [key]}); // log k
if(pq.size() > k) {
pq.pop(); // removing smallest element // log k
}
}
// retrun remaining k element in PQ
return pq. toArray().map(x=> Number(x.val))
};
import heapq
from collections import Counter
def topKFrequent(arr, k):
# Count frequencies
freq_map = Counter(arr)
# Min heap
min_heap = []
for num, freq in freq_map.items():
heapq.heappush(min_heap, (freq, num))
if len(min_heap) > k:
heapq.heappop(min_heap)
return [num for freq, num in min_heap]
# Example usage
arr = [1, 1, 1, 2, 2, 3]
k = 2
print(topKFrequent(arr, k))
import java.util.*;
public class Solution {
public List topKFrequent(int[] arr, int k) {
Map map = new HashMap<>();
for (int num : arr) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue> pq =
new PriorityQueue<>((a, b) -> a.getValue() - b.getValue());
for (Map.Entry entry : map.entrySet()) {
pq.offer(entry);
if (pq.size() > k) {
pq.poll();
}
}
List result = new ArrayList<>();
while (!pq.isEmpty()) {
result.add(pq.poll().getKey());
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] arr = {1, 1, 1, 2, 2, 3};
int k = 2;
System.out.println(sol.topKFrequent(arr, k));
}
}
vector topKFrequent(vector& arr, int k) {
unordered_map map;
for (int num : arr) {
map[num]++;
}
// Min heap (priority queue) based on frequency
priority_queue, vector>, greater>> pq;
for (auto& entry : map) {
pq.push({entry.second, entry.first});
if (pq.size() > k) {
pq.pop();
}
}
vector result;
while (!pq.empty()) {
result.push_back(pq.top().second);
pq.pop();
}
return result;
}
int main() {
vector arr = {1,1,1,2,2,3};
int k = 2;
vector res = topKFrequent(arr, k);
for (int num : res) {
cout << num << " ";
}
return 0;
}
// Function to compare the elements for the priority queue
int compare(const void *a, const void *b) {
return ((*(int*)a) - (*(int*)b));
}
int* topKFrequent(int* arr, int arrSize, int k, int* returnSize) {
int map[MAX_SIZE] = {0};
// Count frequencies
for (int i = 0; i < arrSize; ++i) {
map[arr[i]]++;
}
// Create a priority queue (min heap)
int* pq = (int*)malloc(k * sizeof(int));
*returnSize = k;
// Fill priority queue with first k frequent elements
qsort(pq, k, sizeof(int), compare);
return pq;
}
int main() {
int arr[] = {1, 1, 1, 2, 2, 3};
int k = 2;
int returnSize;
int* result = topKFrequent(arr, 6, k, &returnSize);
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
return 0;
}
using System;
using System.Collections.Generic;
public class Solution {
public int[] TopKFrequent(int[] arr, int k) {
Dictionary map = new Dictionary();
foreach (var num in arr) {
if (!map.ContainsKey(num)) map[num] = 0;
map[num]++;
}
var pq = new SortedList(Comparer.Create((x, y) => x.CompareTo(y)));
foreach (var entry in map) {
pq.Add(entry.Value, entry.Key);
if (pq.Count > k) pq.RemoveAt(0);
}
return pq.Values.ToArray();
}
}
