Top K Frequent Elements - LeetCode
Explanation:
Frequency Map:
We use collections.Counter to create a frequency map of each number in the nums array.
Heap Construction:
Traverse through the frequency map, adding each element to a min-heap (using heapq.heappush).
If the heap size exceeds k, we remove the element with the lowest frequency (heapq.heappop).
Return the Result:
After processing all elements, the heap will contain exactly k most frequent elements.
We then extract just the elements from the heap and return them as the result.
Example Walkthrough:
For nums = [1, 1, 1, 2, 2, 3] and k = 2:
Step 1: Frequency Map: {1: 3, 2: 2, 3: 1}
Step 2: Add to heap:
Add (3, 1) - Heap: [(3, 1)]
Add (2, 2) - Heap: [(2, 2), (3, 1)]
Add (1, 3) - Heap: [(1, 3), (3, 1), (2, 2)] (size greaterThan k)
Pop the smallest - Heap: [(2, 2), (3, 1)]
Step 3: Return elements [2, 1] (or [1, 2]).
Complexity Analysis:
Time Complexity:
Building the frequency map takes
𝑂(𝑁)
O(N), where
𝑁
N is the number of elements.
Each heappush and heappop operation takes
𝑂(log𝑘)
O(logk).
Total complexity:
𝑂(𝑁log𝑘)
O(Nlogk).
Space Complexity:
The frequency map uses
𝑂(𝑁)
O(N).
The heap uses
𝑂(𝑘)
O(k).