Domain 2MediumCORE

Top K Frequent Elements

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.

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Hash Table#Heap

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 (1≤k≤1 \le k \le number of unique elements).

Outputs:

  • A list containing exactly k distinct integers from nums.

Constraints & Edge Cases:

  • Array length up to 10510^5. This implies we need an efficient solution, likely linear or near-linear time.
  • Frequencies are bounded by the array size (NN).
  • 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 O(N)O(N) using a hash map (Counter). Sorting the unique elements takes O(Ulog⁡U)O(U \log U) where UU is the number of unique items (U≤NU \le N). This results in an overall time complexity of roughly O(N+Nlog⁡N)O(N + N \log N).

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:

  1. If the heap has fewer than k elements, add the current item.
  2. 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.
  3. 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 11 and NN, a Bucket Sort approach (frequency buckets) could achieve strict linear time O(N)O(N), but the Heap solution (O(Nlog⁡K)O(N \log K)) 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

  1. Frequency Counting: Use collections.Counter to build a hash map of element frequencies in O(N)O(N) time.
  2. Min-Heap Maintenance: Initialize an empty min-heap (using Python’s heapq). Iterate through each unique number and its frequency from the Counter.
  3. Selection Logic:
    • If heap size is less than k, push (frequency, element) onto the heap.
    • If heap size equals k and we find a new item with higher frequency than the root (smallest freq), use heapq.heapreplace. This pushes the new item and pops the smallest one automatically in O(log⁡k)O(\log k).
  4. Result Extraction: After iterating all unique elements, convert the heap contents back to a list of element values.

Complexity Analysis

  • Time Complexity: O(N+Ulog⁡K)O(N + U \log K), where NN is array length and UU is number of unique elements (U≤NU \le N). Counting takes O(N)O(N). Iterating through the map involves heap operations taking log⁡K\log K each. Since we do this for at most UU items, it’s bounded by O(Ulog⁡K)O(U \log K) or effectively O(Nlog⁡K)O(N \log K). This is strictly better than sorting (Nlog⁡NN \log N).
  • Space Complexity: O(N)O(N) 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 NN. Heap stores that one key (if k=1k=1) 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 K>0K > 0, we return the single element repeated in output list logic? No, Counter returns distinct keys. So [1].
  • Negative Numbers: Python’s hash map handles negative integers as unique keys correctly without issue.
  • k=number of unique elementsk = \text{number of unique elements}: The heap will simply fill up with all items and never pop anything (condition len(heap) < k or check fails to replace), returning the full set of frequencies, which is correct behavior for Top K when K=UK=U.