Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 347. Top K Frequent Elements

Given an integer array and k, return the k most frequent elements — the core challenge is to count element frequencies and extract the top-k efficiently (better than O(n log n)), typically using a frequency map combined with a min-heap (O(n log k)) or bucket sort (O(n)).

Asked at:

DESCRIPTION

Input:

nums = [1,1,1,2,2,3], k = 2

Output:

[1,2]

Explanation: Element 1 appears 3 times (most frequent), element 2 appears 2 times (second most frequent). Return the top 2 most frequent elements.

Constraints:

1 <= nums.length <= 10^5
k is in the range [1, number of unique elements]
-10^4 <= nums[i] <= 10^4
The answer is guaranteed to be unique
Your algorithm's time complexity must be better than O(n log n)

Understanding the Problem

Let's understand what we're being asked to do. We have an array like [1, 1, 1, 2, 2, 3] and a value k=2, and we need to return the 2 most frequent elements.

Tracing through: count the frequencies: 1 appears 3 times, 2 appears 2 times, 3 appears 1 time. The top 2 most frequent are 1 (3 times) and 2 (2 times), so return [1, 2].

Important constraint: We need to do better than O(n log n) time complexity. A naive approach of sorting by frequency would be O(n log n), but we can achieve O(n log k) or even O(n).

Edge cases to consider: What if multiple elements have the same frequency? What if k equals the number of unique elements? What if all elements have the same frequency?

Brute Force Approach

First, build a frequency map by iterating through the array and counting occurrences of each element. Then, convert the frequency map into an array of (element, frequency) pairs and sort this array by frequency in descending order. Finally, take the first k elements from the sorted array. This approach is straightforward but requires sorting all unique elements, leading to O(n log n) complexity.

Visualization

def top_k_frequent(nums, k):
    """
    Find k most frequent elements using frequency map and sorting.
    Time: O(n log n), Space: O(n)
    """
    # Build frequency map
    freq_map = {}
    for num in nums:
        if num in freq_map:
            freq_map[num] += 1
        else:
            freq_map[num] = 1
    
    # Convert to list of (element, frequency) pairs
    freq_pairs = []
    for num, count in freq_map.items():
        freq_pairs.append((num, count))
    
    # Sort by frequency in descending order (brute force - sorts ALL elements)
    for i in range(len(freq_pairs)):
        for j in range(i + 1, len(freq_pairs)):
            if freq_pairs[j][1] > freq_pairs[i][1]:
                # Swap elements
                temp = freq_pairs[i]
                freq_pairs[i] = freq_pairs[j]
                freq_pairs[j] = temp
    
    # Extract first k elements
    result = []
    for i in range(k):
        result.append(freq_pairs[i][0])
    
    return result

Start: Find k most frequent elements using frequency map and sorting

0 / 42

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n) Building the frequency map takes O(n). Sorting the unique elements by frequency takes O(n log n) in the worst case when all elements are unique. Taking the top k is O(k). Overall: O(n log n).

Space Complexity: O(n) The frequency map stores up to n unique elements in the worst case. The sorted array also stores up to n elements. Overall: O(n) space.

Building Intuition

We need to solve two sub-problems: counting frequencies (how many times each element appears) and finding the top k (extracting the k elements with highest counts).

The first part is straightforward with a frequency map. The challenge is the second part: how do we efficiently find the top k without sorting all elements?

If we sort all unique elements by frequency, that's O(n log n) where n is the array length. But we only need the top k elements, not a fully sorted list.

By maintaining only k elements at a time (using a size-k structure), we can reduce this to O(n log k). When k is much smaller than n, this is a huge improvement!

Imagine you're tracking the top 3 most popular songs from a playlist of 1 million songs. You don't need to rank all 1 million songs - you just need to keep track of your current 'top 3' and update it as you scan through.

When you encounter a new song, you only compare it against your current top 3. If it's more popular than the least popular in your top 3, swap it in. This way, you only maintain 3 songs in memory, not 1 million.

This 'keep only what you need' approach is the key insight for achieving better than O(n log n) complexity.

Common Mistakes

Using a max-heap instead of min-heap: A max-heap makes it hard to remove the element with minimum frequency when the heap is full. A min-heap lets you efficiently remove the smallest frequency element.

Sorting the entire frequency map: This gives O(n log n) complexity, which violates the constraint. The problem specifically asks for better than O(n log n).

Not handling ties correctly: When multiple elements have the same frequency, any of them can be returned. Make sure your solution doesn't assume a specific ordering for ties.

Confusing k with array length: k is the number of most frequent elements to return, not the size of the input array. The heap size should be k, not n.

Forgetting to extract elements from the heap: After building the min-heap, you need to extract all k elements to form the result array. Don't return the heap structure itself.

Optimal Solution

First, build a frequency map to count occurrences of each element. Then, use a min-heap of size k to track the k most frequent elements. Iterate through the frequency map: for each element, if the heap has fewer than k elements, add it; otherwise, if the current element's frequency is greater than the minimum frequency in the heap, remove the minimum and add the current element. This maintains only k elements at a time, achieving O(n log k) complexity. An alternative optimal approach uses bucket sort to achieve O(n) by grouping elements by frequency.

Visualization

import heapq
from collections import Counter
def top_k_frequent(nums, k):
    """
    Find k most frequent elements using frequency map and min-heap.
    Time: O(n log k), Space: O(n)
    """
    # Build frequency map
    freq_map = Counter(nums)
    
    # Min-heap to track k most frequent elements
    # Heap stores tuples: (frequency, element)
    min_heap = []
    
    # Iterate through frequency map
    for num, freq in freq_map.items():
        # If heap has fewer than k elements, add current element
        if len(min_heap) < k:
            heapq.heappush(min_heap, (freq, num))
        # If current frequency > minimum frequency in heap
        elif freq > min_heap[0][0]:
            # Remove minimum and add current element
            heapq.heapreplace(min_heap, (freq, num))
    
    # Extract elements from heap (ignore frequencies)
    result = [num for freq, num in min_heap]
    return result

Start: Find k most frequent elements

0 / 13

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log k) Building the frequency map takes O(n). For each of the unique elements (at most n), we perform a heap operation (insert or replace) which takes O(log k) since the heap size is bounded by k. Overall: O(n log k). When k is small, this is much better than O(n log n).

Space Complexity: O(n) The frequency map stores up to n unique elements. The min-heap stores at most k elements. Overall: O(n) space dominated by the frequency map.

What We've Learned

Heap for top-K problems: When you need the k largest/smallest/most frequent elements from a dataset, use a min-heap of size k (for top-k largest) or max-heap of size k (for top-k smallest) - this gives O(n log k) complexity instead of O(n log n) sorting, because you only maintain k elements in the heap at any time.
Frequency map + heap combination: The two-step pattern of first building a frequency hashmap (O(n)) then pushing to a heap (O(n log k)) is the standard approach for frequency-based problems - separate the counting phase from the selection phase for cleaner code and optimal performance.
Bucket sort optimization for bounded frequencies: When frequencies are bounded by array length, bucket sort achieves O(n) time by creating buckets indexed by frequency count - this trades space for time and is optimal when k is large relative to n, avoiding heap overhead entirely.
Min-heap size maintenance: A critical implementation detail is using a min-heap of size k (not max-heap) for top-k frequent - when the heap exceeds k elements, pop the minimum, ensuring only the k most frequent remain. Many students mistakenly use max-heap which requires processing all n elements.
Heap vs bucket sort trade-off: Choose min-heap when k is small (O(n log k) is efficient) and bucket sort when k is large or k=n (O(n) is better) - understanding this trade-off shows algorithmic maturity, as the optimal solution depends on the relationship between n and k.
Real-world frequency analysis: This pattern appears in trending topics (Twitter's top hashtags), recommendation systems (most purchased items), log analysis (most common errors), and search autocomplete (most frequent queries) - any system that needs to surface popular items from streaming or batch data uses this exact technique.

Test Your Understanding

Why is heap the right data structure for this problem?

heap provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late December, 2025

Amazon

Senior

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Mid December, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 347. Top K Frequent Elements

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact