Top K Frequent¶

Problem¶

Given an integer array and an integer k, return the k most frequent elements. The answer is guaranteed to be unique.

Approach¶

Bucket sort by frequency. Count occurrences, then place each number into a bucket indexed by its frequency. Walk buckets from highest frequency downward until k elements are collected.

When to Use¶

Frequency counting + selection — "top K", "most common", "least common". Bucket sort avoids O(n log n); see also heaps/kth_largest for streaming variant.

Complexity¶


Time	`O(n)`
Space	`O(n)`

Implementation¶

SolutionTestsChallenge

top_k_frequent ¶

Top K Frequent Elements — return the k most frequent elements.

Problem

Given an integer array and an integer k, return the k most frequent elements. The answer is guaranteed to be unique.

Approach

Bucket sort by frequency. Count occurrences, then place each number into a bucket indexed by its frequency. Walk buckets from highest frequency downward until k elements are collected.

When to use

Frequency counting + selection — "top K", "most common", "least common". Bucket sort avoids O(n log n); see also heaps/kth_largest for streaming variant.

Complexity

Time: O(n) Space: O(n)

top_k_frequent ¶

top_k_frequent(nums: Sequence[int], k: int) -> list[int]

Return the k most frequent elements in nums.

sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) [1, 2]

Source code in src/algo/arrays/top_k_frequent.py

def top_k_frequent(nums: Sequence[int], k: int) -> list[int]:
    """Return the *k* most frequent elements in *nums*.

    >>> sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2))
    [1, 2]
    """
    if k <= 0:
        return []

    count = Counter(nums)
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result: list[int] = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]

    return result[:k]

tests/arrays/test_top_k_frequent.py

"""Tests for the top-k-frequent-elements problem."""

from hypothesis import given
from hypothesis import strategies as st

from algo.arrays.top_k_frequent import top_k_frequent


class TestTopKFrequent:
    def test_basic(self) -> None:
        assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]

    def test_single_element(self) -> None:
        assert top_k_frequent([1], 1) == [1]

    def test_all_same_frequency(self) -> None:
        result = top_k_frequent([1, 2, 3], 2)
        assert len(result) == 2
        assert all(x in [1, 2, 3] for x in result)

    def test_k_equals_unique_count(self) -> None:
        assert sorted(top_k_frequent([1, 1, 2, 2, 3, 3], 3)) == [1, 2, 3]

    def test_negative_numbers(self) -> None:
        assert sorted(top_k_frequent([-1, -1, 2, 2, 2, 3], 2)) == [-1, 2]

    def test_k_zero(self) -> None:
        assert top_k_frequent([1, 2, 3], 0) == []

    @given(
        data=st.lists(
            st.integers(min_value=-100, max_value=100),
            min_size=1,
            max_size=50,
        ),
    )
    def test_top_1_is_most_frequent(self, data: list[int]) -> None:
        from collections import Counter

        result = top_k_frequent(data, 1)
        assert len(result) == 1
        counter = Counter(data)
        max_freq = counter.most_common(1)[0][1]
        assert counter[result[0]] == max_freq

Implement it yourself

Run: just challenge arrays top_k_frequent

Then implement the functions to make all tests pass. Use just study arrays for watch mode.

Reveal Solution

top_k_frequent ¶

Top K Frequent Elements — return the k most frequent elements.

Problem

Given an integer array and an integer k, return the k most frequent elements. The answer is guaranteed to be unique.

Approach

Bucket sort by frequency. Count occurrences, then place each number into a bucket indexed by its frequency. Walk buckets from highest frequency downward until k elements are collected.

When to use

Frequency counting + selection — "top K", "most common", "least common". Bucket sort avoids O(n log n); see also heaps/kth_largest for streaming variant.

Complexity

Time: O(n) Space: O(n)

top_k_frequent ¶

top_k_frequent(nums: Sequence[int], k: int) -> list[int]

Return the k most frequent elements in nums.

sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) [1, 2]

Source code in src/algo/arrays/top_k_frequent.py

def top_k_frequent(nums: Sequence[int], k: int) -> list[int]:
    """Return the *k* most frequent elements in *nums*.

    >>> sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2))
    [1, 2]
    """
    if k <= 0:
        return []

    count = Counter(nums)
    buckets: list[list[int]] = [[] for _ in range(len(nums) + 1)]
    for num, freq in count.items():
        buckets[freq].append(num)

    result: list[int] = []
    for i in range(len(buckets) - 1, -1, -1):
        result.extend(buckets[i])
        if len(result) >= k:
            return result[:k]

    return result[:k]