Generated by Codex with GPT-5

Quick facts

What the problem is really asking

The input is an array of integers and a number k.

The task is not to sort the array itself. It is to:

  1. count how many times each distinct value appears
  2. identify the k values with the largest counts
  3. return those values in any order

That means the problem is really about ranking values by frequency, not about rearranging the original list.

Why the obvious approach is not the best final answer

The most straightforward solution is:

  1. build a frequency map
  2. sort the distinct values by frequency descending
  3. take the first k

That works, and it is often the right first step in an interview because it proves the candidate sees the shape of the problem.

But sorting all distinct values costs O(m log m) time, where m is the number of unique values. Since m can be as large as n, this can become O(n log n).

For this LeetCode problem, the interesting part is doing better than that full sort.

The key insight

Once the frequency map is built, each number has a count between 1 and n.

That bounded range matters. Instead of sorting numbers by frequency, the algorithm can group numbers into buckets where:

  • bucket 1 contains numbers seen once
  • bucket 2 contains numbers seen twice
  • …
  • bucket n contains numbers seen n times

After that, the algorithm simply walks the buckets from high frequency down to low frequency and collects numbers until it has k of them.

This replaces a comparison sort with indexed lookups, which is why the runtime becomes linear.

How to derive the optimal solution

A clean derivation in an interview is:

  1. Any correct solution has to inspect every input value at least once, so O(n) time is the ideal target.
  2. Counting frequencies with a hash map is already O(n).
  3. The remaining challenge is selecting the largest frequencies without sorting everything.
  4. Because a frequency can never exceed n, frequencies live in a small integer range.
  5. That suggests bucket sort: use the frequency itself as an index.
  6. Scan those buckets from the back and stop as soon as k numbers have been collected.

The big mental shift is this:

do not sort the numbers; organize them by count.

Best solution choices

There are two strong approaches worth knowing:

  • Bucket sort: O(n) time and O(n) extra space. This is the best match for the original problem.
  • Min-heap of size k: O(n log k) time and O(m) space. This is a good alternative when k is much smaller than the number of unique values or when the interviewer wants a streaming-friendly direction.

For the standard LeetCode version, bucket sort is usually the strongest final answer because it directly addresses the “better than O(n log n)” follow-up.

A simple mental model

Think of the algorithm as building shelves labeled by frequency.

Each number gets placed onto the shelf matching how often it appears. Once those shelves exist, the answer is just:

  • start at the highest shelf
  • take every number on that shelf
  • keep going downward until k numbers have been picked

That is much simpler than maintaining a fully sorted ranking of everything.

Python solution

from collections import Counter
from typing import Dict, List


class TopKFrequentSelector:
    """Select the k most frequent numbers from an integer array."""

    def top_k_frequent(self, numbers: List[int], k: int) -> List[int]:
        if k <= 0 or not numbers:
            return []

        frequency_by_number = self._count_frequencies(numbers)
        frequency_buckets = self._build_frequency_buckets(
            frequency_by_number=frequency_by_number,
            max_frequency=len(numbers),
        )
        return self._collect_most_frequent(
            frequency_buckets=frequency_buckets,
            k=min(k, len(frequency_by_number)),
        )

    def _count_frequencies(self, numbers: List[int]) -> Dict[int, int]:
        """Map each distinct number to the number of times it appears."""
        return dict(Counter(numbers))

    def _build_frequency_buckets(
        self,
        frequency_by_number: Dict[int, int],
        max_frequency: int,
    ) -> List[List[int]]:
        """
        Group numbers by how often they appear.

        Bucket index i stores all numbers that occur exactly i times.
        """
        buckets: List[List[int]] = [[] for _ in range(max_frequency + 1)]

        for number, frequency in frequency_by_number.items():
            buckets[frequency].append(number)

        return buckets

    def _collect_most_frequent(
        self,
        frequency_buckets: List[List[int]],
        k: int,
    ) -> List[int]:
        """Walk the buckets from high to low frequency until k values are collected."""
        most_frequent_numbers: List[int] = []

        for frequency in range(len(frequency_buckets) - 1, 0, -1):
            if not frequency_buckets[frequency]:
                continue

            for number in frequency_buckets[frequency]:
                most_frequent_numbers.append(number)
                if len(most_frequent_numbers) == k:
                    return most_frequent_numbers

        return most_frequent_numbers


class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        selector = TopKFrequentSelector()
        return selector.top_k_frequent(nums, k)

Why this works

The frequency map is correct because each element contributes exactly one count to its own value.

The bucket array is correct because every distinct number is placed into exactly one bucket: the bucket matching its final frequency.

Scanning the buckets from highest index to lowest means numbers are considered in descending order of frequency. As soon as k numbers have been collected, those must be the k most frequent values because:

  • no skipped bucket has a higher frequency
  • every higher-frequency bucket has already been fully processed

The runtime is O(n):

  • O(n) to count frequencies
  • O(m) to place the m distinct values into buckets
  • O(n) in the worst case to scan the bucket array

The extra space is also O(n) because the hash map and buckets together scale linearly with the input size.

Interview follow-ups

What if the interviewer asks for a heap-based solution instead?

The usual answer is to keep a min-heap of size k while iterating through the frequency map. Each heap entry stores (frequency, number). If the heap grows past size k, the smallest frequency is removed. By the end, the heap contains exactly the k highest-frequency numbers. This works because the heap preserves the current best k candidates seen so far, and any number with a frequency smaller than the heap minimum cannot belong in the final answer once the heap is full. The time complexity is O(m log k) and the extra space is O(m) for the frequency map plus O(k) for the heap. This is worse than bucket sort for the original problem, but often preferable when k is small or when a linear-size bucket array feels wasteful.

What if the data arrives as a stream and the full array is not available up front?

If exact answers are still required, the algorithm must keep the frequency map as items arrive, then apply either the heap or bucket strategy once the stream ends. If the interviewer means the top k must be available continuously during the stream, a min-heap paired with the frequency map is the more natural direction because it supports incremental maintenance better than rebuilding buckets after every update. The tradeoff is that exact real-time maintenance becomes more complex because frequency increases can invalidate old heap entries, so implementations often use lazy deletion or rebuild steps. If approximate answers are acceptable, this turns into a different class of problem and sketches like Misra-Gries or Count-Min Sketch become relevant.

What if the interviewer wants the result ordered by frequency descending?

The core selection logic stays the same, but the output format changes. With bucket sort, the algorithm can still walk buckets from high frequency to low frequency and append numbers in that order, which naturally yields descending frequency groups. If the interviewer also wants a stable order within ties, then an additional ordering rule has to be applied inside each bucket, such as sorting the tied values numerically. That extra tie-handling can raise the effective runtime, so it is important to clarify whether exact intra-bucket ordering is required or whether any order is acceptable as in the original problem.

What if the value range is tiny but the array is huge?

In that setting, the problem becomes even more favorable for counting-based methods. A direct counting array may replace the hash map if the value range is known and compact, which reduces hashing overhead and can improve constants in practice. After counting, the same bucket idea still works, or the algorithm can scan the compact count array and keep the best k values. The tradeoff is flexibility: this optimization only applies when the domain is bounded and reasonably small, while the hash-map solution works for arbitrary integers without assumptions about range.