347. Top K Frequent Elements
Model: qwen3.5:9b
Topics: Hash Table,Heap
FAANG asked: 1
Acceptance rate: 62.6%
Problem Breakdown
We are given an integer array nums and a target number of elements k. The goal is to identify the specific values that appear most frequently in the input list. We need to return these top k values; their order does not matter, but we must ensure they correspond exactly to the highest frequency counts available in the dataset.
Inputs:
nums: A list of integers (can include duplicates and negative numbers).k: An integer representing how many frequent elements to return ( number of unique elements).
Outputs:
- A list containing exactly
kdistinct integers fromnums.
Constraints & Edge Cases:
- Array length up to . This implies we need an efficient solution, likely linear or near-linear time.
- Frequencies are bounded by the array size ().
- The problem guarantees a unique answer (no ambiguity on which elements to pick if frequencies were tied in specific test cases), though standard behavior is usually allowed for ties unless specified otherwise.
Intuition
A naive approach would be to count every element’s frequency and then sort all unique elements by that frequency, taking the top k. Counting takes using a hash map (Counter). Sorting the unique elements takes where is the number of unique items (). This results in an overall time complexity of roughly .
This violates the follow-up requirement to be better than O(n log n). To improve this, we recognize that sorting all elements is unnecessary. We only need the top k largest frequencies.
The key insight for “Top K” problems is using a Min-Heap (Priority Queue). Instead of storing and sorting every element, we can maintain a heap of size exactly k. As we iterate through our frequency map:
- If the heap has fewer than
kelements, add the current item. - If it’s full, compare the new item with the smallest (root) element in the heap. Since this is a min-heap ordered by frequency, the root holds the least frequent among our top candidates.
- We only keep an incoming element if its frequency is higher than that minimum threshold. This allows us to discard low-frequency elements efficiently without sorting everything at once.
Alternatively, since frequencies are bounded between and , a Bucket Sort approach (frequency buckets) could achieve strict linear time , but the Heap solution () is generally more robust for general “Top K” scenarios where frequency bounds might be looser or memory constraints exist. I will implement the Min-Heap approach as it’s idiomatic and satisfies the complexity constraint comfortably.
Approach
- Frequency Counting: Use
collections.Counterto build a hash map of element frequencies in time. - Min-Heap Maintenance: Initialize an empty min-heap (using Python’s
heapq). Iterate through each unique number and its frequency from the Counter. - Selection Logic:
- If heap size is less than
k, push(frequency, element)onto the heap. - If heap size equals
kand we find a new item with higher frequency than the root (smallest freq), useheapq.heapreplace. This pushes the new item and pops the smallest one automatically in .
- If heap size is less than
- Result Extraction: After iterating all unique elements, convert the heap contents back to a list of element values.
Complexity Analysis
- Time Complexity: , where is array length and is number of unique elements (). Counting takes . Iterating through the map involves heap operations taking each. Since we do this for at most items, it’s bounded by or effectively . This is strictly better than sorting ().
- Space Complexity: to store the frequency map and heap. The hash map stores all unique elements; in worst case (all distinct), this scales with input size.
Solution
import heapq
from collections import Counter
def topKFrequent(nums, k):
# Step 1: Count frequencies of each element
count = Counter(nums)
heap = []
for num in count:
freq = count[num]
if len(heap) < k:
heapq.heappush(heap, (freq, num))
else:
# If current frequency is greater than the smallest in our top-k set
# Replace the root with this new element to maintain size K of largest frequencies
if freq > heap[0][0]:
heapq.heapreplace(heap, (freq, num))
return [num for freq, num in heap]
Edge Cases Handled
- Single Element Array: The loop runs once, heap fills with the single element, returns correctly.
- All Elements Identical: Counter maps one key to . Heap stores that one key (if ) or handles it appropriately if multiple unique keys exist but same freq? Wait, constraint says answer is unique so frequencies distinguish elements sufficiently for a valid set of top K. If all are identical and , we return the single element repeated in output list logic? No,
Counterreturns distinct keys. So[1]. - Negative Numbers: Python’s hash map handles negative integers as unique keys correctly without issue.
- : The heap will simply fill up with all items and never pop anything (condition
len(heap) < kor check fails to replace), returning the full set of frequencies, which is correct behavior for Top K when .