01
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. It is guaranteed the answer is unique (no tie for the k-th frequency).
02
Key Observations
- Count frequencies: One pass to build
num -> count. - Min-heap of size k keyed by frequency: For each (num, freq), add to heap; if heap size > k, poll the element with smallest frequency. The heap keeps the k elements with highest frequency. Return all heap elements. Time O(n log k).
03
Approach
High-level: Map to count freq. Min-heap of (freq, num). For each (num, freq): offer; if size > k poll. Return heap contents.
Steps: Map<Integer,Integer> freq = new HashMap<>(); for (int x : nums) freq.merge(x,1,Integer::sum); PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]); for (Map.Entry e : freq.entrySet()) { pq.offer(new int[]{e.getValue(), e.getKey()}); if (pq.size()>k) pq.poll(); } return pq stream to array.
04
Implementation
Java
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) {
freq.merge(x, 1, Integer::sum);
}
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1]-b[1]);
for (Map.Entry<Integer,Integer> e : freq.entrySet()) {
pq.offer(new int[]{e.getKey(), e.getValue()});
if (pq.size() > k) {
pq.poll();
}
}
return pq.stream().mapToInt(a -> a[0]).toArray();
}05
Test Cases
Example 1
Input
nums = [1,1,1,2,2,3], k = 2
Expected
[1,2]Explanation
1 and 2 most frequent.
06
Complexity Analysis
- Time: typically O(n log k) or O(n log n).
- Space: O(k) or O(n).
07
Follow-ups
- Stream: process one element at a time.