Top K Frequent Elements

Given an integer array and k, return the k most frequent elements.

Language Selection

Choose your preferred programming language

Showing: Python

Top K Frequent Elements

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.

Examples

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: 1 appears 3 times and 2 appears 2 times. These are the two most frequent elements.

Example 2:

Input: nums = [1], k = 1
Output: [1]
Explanation: Only one element exists, and it is the most frequent.

Example 3:

Input: nums = [4,4,4,1,1,2,2,2,3], k = 2
Output: [4,2]
Explanation: 4 and 2 both appear 3 times. 1 appears 2 times. Returning either [4,2] or [2,4] is acceptable.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • k is in the range [1, the number of unique elements in the array]
  • It is guaranteed that the answer is unique

Approach 1: Sorting by Frequency

Algorithm

Count the frequency of each element, then sort by frequency in descending order and take the first k elements.

Steps:

  1. Build a frequency map counting occurrences of each element
  2. Sort the unique elements by their frequency in descending order
  3. Return the first k elements

Implementation

Python:

from collections import Counter

def topKFrequent(nums, k):
    """
    Find k most frequent elements by sorting frequencies
    Time: O(n log n)
    Space: O(n)
    """
    # Count frequencies
    count = Counter(nums)

    # Sort unique elements by frequency (descending)
    sorted_elements = sorted(count.keys(), key=lambda x: count[x], reverse=True)

    return sorted_elements[:k]

Java:

import java.util.*;

class Solution {
    /**
     * Find k most frequent elements by sorting frequencies
     * Time: O(n log n)
     * Space: O(n)
     */
    public int[] topKFrequent(int[] nums, int k) {
        // Count frequencies
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // Sort unique elements by frequency (descending)
        List<Integer> uniqueElements = new ArrayList<>(count.keySet());
        uniqueElements.sort((a, b) -> count.get(b) - count.get(a));

        // Take first k elements
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = uniqueElements.get(i);
        }

        return result;
    }
}

Go:

import "sort"

// topKFrequent - Find k most frequent elements by sorting frequencies
// Time: O(n log n)
// Space: O(n)
func topKFrequent(nums []int, k int) []int {
    // Count frequencies
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    // Collect unique elements
    uniqueElements := make([]int, 0, len(count))
    for num := range count {
        uniqueElements = append(uniqueElements, num)
    }

    // Sort by frequency (descending)
    sort.Slice(uniqueElements, func(i, j int) bool {
        return count[uniqueElements[i]] > count[uniqueElements[j]]
    })

    return uniqueElements[:k]
}

JavaScript:

/**
 * Find k most frequent elements by sorting frequencies
 * Time: O(n log n)
 * Space: O(n)
 */
function topKFrequent(nums, k) {
    // Count frequencies
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }

    // Sort unique elements by frequency (descending)
    const uniqueElements = Array.from(count.keys());
    uniqueElements.sort((a, b) => count.get(b) - count.get(a));

    return uniqueElements.slice(0, k);
}

C#:

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    /// <summary>
    /// Find k most frequent elements by sorting frequencies
    /// Time: O(n log n)
    /// Space: O(n)
    /// </summary>
    public int[] TopKFrequent(int[] nums, int k) {
        // Count frequencies
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }

        // Sort unique elements by frequency (descending) and take k
        return count.Keys
            .OrderByDescending(x => count[x])
            .Take(k)
            .ToArray();
    }
}

Complexity Analysis

  • Time Complexity: O(n log n) - Counting is O(n), sorting is O(m log m) where m is the number of unique elements (m <= n)
  • Space Complexity: O(n) - For the frequency map

Approach 2: Min-Heap of Size K

Algorithm

Use a min-heap of size k to efficiently track the k most frequent elements without fully sorting.

Steps:

  1. Build a frequency map
  2. Maintain a min-heap of size k, ordered by frequency
  3. For each unique element, push it onto the heap; if heap size exceeds k, pop the smallest
  4. The heap now contains the k most frequent elements

Implementation

Python:

import heapq
from collections import Counter

def topKFrequent(nums, k):
    """
    Find k most frequent elements using min-heap
    Time: O(n log k)
    Space: O(n) for frequency map + O(k) for heap
    """
    count = Counter(nums)

    # Min-heap of size k: stores (frequency, element) pairs
    heap = []

    for num, freq in count.items():
        heapq.heappush(heap, (freq, num))
        if len(heap) > k:
            heapq.heappop(heap)  # Remove the least frequent

    return [num for freq, num in heap]

Java:

import java.util.*;

class Solution {
    /**
     * Find k most frequent elements using min-heap
     * Time: O(n log k)
     * Space: O(n)
     */
    public int[] topKFrequent(int[] nums, int k) {
        // Count frequencies
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // Min-heap ordered by frequency
        PriorityQueue<int[]> heap = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[1], b[1])
        );

        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            heap.offer(new int[]{entry.getKey(), entry.getValue()});
            if (heap.size() > k) {
                heap.poll(); // Remove least frequent
            }
        }

        // Extract elements from heap
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = heap.poll()[0];
        }
        return result;
    }
}

Go:

import "container/heap"

type FreqPair struct {
    num  int
    freq int
}

type MinHeap []FreqPair

func (h MinHeap) Len() int            { return len(h) }
func (h MinHeap) Less(i, j int) bool  { return h[i].freq < h[j].freq }
func (h MinHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(FreqPair)) }
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[:n-1]
    return x
}

// topKFrequent - Find k most frequent elements using min-heap
// Time: O(n log k)
// Space: O(n)
func topKFrequent(nums []int, k int) []int {
    // Count frequencies
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    // Min-heap of size k
    h := &MinHeap{}
    heap.Init(h)

    for num, freq := range count {
        heap.Push(h, FreqPair{num, freq})
        if h.Len() > k {
            heap.Pop(h)
        }
    }

    // Extract elements
    result := make([]int, k)
    for i := 0; i < k; i++ {
        result[i] = heap.Pop(h).(FreqPair).num
    }
    return result
}

JavaScript:

/**
 * Find k most frequent elements using min-heap (simplified with array + sort)
 * Time: O(n log k) with a proper heap; O(n log n) with array sort fallback
 * Space: O(n)
 */
function topKFrequent(nums, k) {
    // Count frequencies
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }

    // Use a simple min-heap implementation
    const heap = [];

    const swap = (i, j) => { [heap[i], heap[j]] = [heap[j], heap[i]]; };

    const bubbleUp = (idx) => {
        while (idx > 0) {
            const parent = Math.floor((idx - 1) / 2);
            if (heap[parent][1] <= heap[idx][1]) break;
            swap(parent, idx);
            idx = parent;
        }
    };

    const bubbleDown = (idx) => {
        while (2 * idx + 1 < heap.length) {
            let smallest = 2 * idx + 1;
            if (2 * idx + 2 < heap.length && heap[2 * idx + 2][1] < heap[smallest][1]) {
                smallest = 2 * idx + 2;
            }
            if (heap[idx][1] <= heap[smallest][1]) break;
            swap(idx, smallest);
            idx = smallest;
        }
    };

    for (const [num, freq] of count) {
        heap.push([num, freq]);
        bubbleUp(heap.length - 1);

        if (heap.length > k) {
            // Pop minimum
            heap[0] = heap[heap.length - 1];
            heap.pop();
            if (heap.length > 0) bubbleDown(0);
        }
    }

    return heap.map(pair => pair[0]);
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find k most frequent elements using min-heap
    /// Time: O(n log k)
    /// Space: O(n)
    /// </summary>
    public int[] TopKFrequent(int[] nums, int k) {
        // Count frequencies
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }

        // Min-heap ordered by frequency
        var heap = new PriorityQueue<int, int>();

        foreach (var kvp in count) {
            heap.Enqueue(kvp.Key, kvp.Value);
            if (heap.Count > k) {
                heap.Dequeue(); // Remove least frequent
            }
        }

        // Extract elements
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = heap.Dequeue();
        }
        return result;
    }
}

Complexity Analysis

  • Time Complexity: O(n log k) - Counting is O(n), each heap operation is O(log k), performed m times (m = unique elements)
  • Space Complexity: O(n) for the frequency map, O(k) for the heap

Approach 3: Bucket Sort (Optimal)

Algorithm

Use the frequency as an index into a bucket array. Since the maximum possible frequency is n (the array length), create n+1 buckets. Then iterate from the highest frequency bucket downward to collect k elements.

Steps:

  1. Build a frequency map
  2. Create an array of buckets where bucket[i] holds all elements with frequency i
  3. Iterate from the highest frequency bucket down to 1
  4. Collect elements until we have k total

Implementation

Python:

from collections import Counter

def topKFrequent(nums, k):
    """
    Find k most frequent elements using bucket sort
    Time: O(n)
    Space: O(n)
    """
    count = Counter(nums)
    n = len(nums)

    # bucket[i] = list of elements that appear exactly i times
    bucket = [[] for _ in range(n + 1)]

    for num, freq in count.items():
        bucket[freq].append(num)

    # Collect from highest frequency to lowest
    result = []
    for freq in range(n, 0, -1):
        for num in bucket[freq]:
            result.append(num)
            if len(result) == k:
                return result

    return result

Java:

import java.util.*;

class Solution {
    /**
     * Find k most frequent elements using bucket sort
     * Time: O(n)
     * Space: O(n)
     */
    public int[] topKFrequent(int[] nums, int k) {
        // Count frequencies
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        int n = nums.length;

        // bucket[i] = list of elements that appear exactly i times
        @SuppressWarnings("unchecked")
        List<Integer>[] bucket = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            bucket[i] = new ArrayList<>();
        }

        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            bucket[entry.getValue()].add(entry.getKey());
        }

        // Collect from highest frequency to lowest
        int[] result = new int[k];
        int idx = 0;
        for (int freq = n; freq >= 1 && idx < k; freq--) {
            for (int num : bucket[freq]) {
                result[idx++] = num;
                if (idx == k) return result;
            }
        }

        return result;
    }
}

Go:

// topKFrequent - Find k most frequent elements using bucket sort
// Time: O(n)
// Space: O(n)
func topKFrequent(nums []int, k int) []int {
    // Count frequencies
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    n := len(nums)

    // bucket[i] = list of elements that appear exactly i times
    bucket := make([][]int, n+1)
    for i := range bucket {
        bucket[i] = []int{}
    }

    for num, freq := range count {
        bucket[freq] = append(bucket[freq], num)
    }

    // Collect from highest frequency to lowest
    result := make([]int, 0, k)
    for freq := n; freq >= 1 && len(result) < k; freq-- {
        for _, num := range bucket[freq] {
            result = append(result, num)
            if len(result) == k {
                return result
            }
        }
    }

    return result
}

JavaScript:

/**
 * Find k most frequent elements using bucket sort
 * Time: O(n)
 * Space: O(n)
 */
function topKFrequent(nums, k) {
    // Count frequencies
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }

    const n = nums.length;

    // bucket[i] = list of elements that appear exactly i times
    const bucket = Array.from({ length: n + 1 }, () => []);

    for (const [num, freq] of count) {
        bucket[freq].push(num);
    }

    // Collect from highest frequency to lowest
    const result = [];
    for (let freq = n; freq >= 1 && result.length < k; freq--) {
        for (const num of bucket[freq]) {
            result.push(num);
            if (result.length === k) return result;
        }
    }

    return result;
}

C#:

using System;
using System.Collections.Generic;

public class Solution {
    /// <summary>
    /// Find k most frequent elements using bucket sort
    /// Time: O(n)
    /// Space: O(n)
    /// </summary>
    public int[] TopKFrequent(int[] nums, int k) {
        // Count frequencies
        var count = new Dictionary<int, int>();
        foreach (int num in nums) {
            count[num] = count.GetValueOrDefault(num, 0) + 1;
        }

        int n = nums.Length;

        // bucket[i] = list of elements that appear exactly i times
        var bucket = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            bucket[i] = new List<int>();
        }

        foreach (var kvp in count) {
            bucket[kvp.Value].Add(kvp.Key);
        }

        // Collect from highest frequency to lowest
        var result = new List<int>();
        for (int freq = n; freq >= 1 && result.Count < k; freq--) {
            foreach (int num in bucket[freq]) {
                result.Add(num);
                if (result.Count == k) return result.ToArray();
            }
        }

        return result.ToArray();
    }
}

Complexity Analysis

  • Time Complexity: O(n) - Counting is O(n), filling buckets is O(m), collecting is O(n) in the worst case
  • Space Complexity: O(n) - For the frequency map and bucket array

Key Insights

  1. Frequency Map First: All three approaches start with a frequency count; the difference is how they select the top k
  2. Bucket Sort Bound: Since frequencies range from 1 to n, we can use frequency as a bucket index for O(n) total time
  3. Heap for Streaming: The min-heap approach naturally handles streaming data where new elements arrive over time
  4. Sorting Simplicity: Sorting is the simplest to code but the slowest at O(n log n)
  5. Min-Heap vs Max-Heap: A min-heap of size k is more efficient than a max-heap of all elements because we only do O(log k) operations per element

Edge Cases

  1. k = 1: Return the single most frequent element
  2. All Elements Same: nums = [5, 5, 5], k = 1 – only one unique element
  3. All Unique: nums = [1, 2, 3, 4], k = 4 – every element has frequency 1
  4. Tied Frequencies: Multiple elements with the same frequency; any k of them is valid
  5. Single Element Array: nums = [1], k = 1 – trivial case
  6. k Equals Unique Count: Return all unique elements

Test Cases

def test_topKFrequent():
    # Standard case
    result = topKFrequent([1, 1, 1, 2, 2, 3], 2)
    assert set(result) == {1, 2}

    # Single element
    assert topKFrequent([1], 1) == [1]

    # All same element
    assert topKFrequent([5, 5, 5, 5], 1) == [5]

    # All unique, return all
    result2 = topKFrequent([1, 2, 3, 4], 4)
    assert set(result2) == {1, 2, 3, 4}

    # Tied frequencies
    result3 = topKFrequent([1, 2, 3], 2)
    assert len(result3) == 2

    # Negative numbers
    result4 = topKFrequent([-1, -1, -2, -2, -2, 3], 1)
    assert result4 == [-2]

    # Larger case
    result5 = topKFrequent([4, 4, 4, 1, 1, 2, 2, 2, 3], 2)
    assert set(result5) == {4, 2}

    print("All tests passed!")

test_topKFrequent()

Follow-up Questions

  1. Top K Frequent Words: How does the solution change if elements are strings and ties are broken alphabetically? (LeetCode #692)
  2. Streaming Data: How would you maintain top-k frequencies in a data stream?
  3. Kth Most Frequent: Return only the single element that is the kth most frequent
  4. K Least Frequent: Find the k least frequent elements instead
  5. Memory Constraint: What if the frequency map does not fit in memory?

Common Mistakes

  1. Wrong Heap Type: Using a max-heap of all elements instead of a min-heap of size k, resulting in O(n log n) instead of O(n log k)
  2. Off-by-One in Buckets: Creating n buckets instead of n+1 (frequency can be n if all elements are the same)
  3. Not Handling Ties: Assuming frequencies are unique when multiple elements can share the same frequency
  4. Forgetting to Count First: Trying to find top-k without building the frequency map first
  5. Bucket Sort Iteration Direction: Iterating from low to high frequency instead of high to low

Interview Tips

  1. Mention All Three Approaches: Show breadth by discussing sorting, heap, and bucket sort
  2. Lead with Bucket Sort: If the interviewer asks for the optimal solution, bucket sort achieves O(n)
  3. Explain the Heap Trade-off: O(n log k) is better than O(n log n) when k is much smaller than n
  4. Trace an Example: Walk through nums = [1,1,1,2,2,3] with k = 2 to show the bucket approach
  5. Discuss Real-World Use: Mention applications like trending topics, popular products, and log analysis

Concept Explanations

Bucket Sort for Bounded Ranges: When values fall in a known range (here, frequencies from 1 to n), bucket sort achieves linear time by using the value itself as an array index.

Min-Heap of Size K: By keeping only k elements in the heap, every push and pop is O(log k). The minimum at the top acts as a threshold: any new element with a higher frequency replaces it.

Frequency Map: The foundational step across all approaches. A hash map provides O(1) amortized insertion and lookup, making the counting phase O(n).

When to Use Each Approach: Use sorting for simplicity. Use a heap when k is much smaller than n or data arrives in a stream. Use bucket sort for guaranteed O(n) time in batch processing.