Code โ€บ algorithm-study

LeetCode 347 - Top K Frequent Elements

Using frequency counting and bucket arrays to return the top k frequent elements

algorithmleetcodearrayhash-mapbucket-sortpythonlearning

This is a Medium array problem: return the k most frequent values. Sorting by frequency works, but this solution uses bucket arrays where the frequency itself becomes the bucket index.

  • Problem link: 347. Top K Frequent Elements
  • Summary: Given an integer array nums and an integer k, return the k values that appear most often.

For example:

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

The value 1 appears three times, and 2 appears twice, so the result can be [1, 2]. The order does not matter.

Approach

First, count how often each value appears.

freq_map = {}
for num in nums:
    freq_map[num] = freq_map.get(num, 0) + 1

Then create buckets where the index represents the frequency. If the length of nums is n, no value can appear more than n times, so n + 1 buckets are enough.

buckets = [[] for i in range(len(nums) + 1)]

for num, freq in freq_map.items():
    buckets[freq].append(num)

Finally, scan the buckets from high frequency to low frequency and return as soon as k values are collected.

top_list = []
for i in range(len(nums), -1, -1):
    for num in buckets[i]:
        top_list.append(num)
        if len(top_list) == k:
            return top_list

The point is to avoid comparing every value by frequency during sorting. A value with frequency 3 goes into buckets[3], a value with frequency 2 goes into buckets[2], and scanning backward visits higher-frequency values first.

Complexity analysis

  • Time complexity: O(n)

    • One pass counts frequencies, one pass fills buckets, and the final scan is linear in the bucket array and collected values.

  • Space complexity: O(n)

    • The frequency map and bucket array both scale with the input size.

Sorting by frequency usually costs O(n log n). The bucket array solution stays linear by using the bounded frequency range from 0 to n.

Optimized code

from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq_map = {}

        for num in nums:
            freq_map[num] = freq_map.get(num, 0) + 1

        buckets = [[] for _ in range(len(nums) + 1)]

        for num, freq in freq_map.items():
            buckets[freq].append(num)

        top_list = []
        for i in range(len(nums), -1, -1):
            for num in buckets[i]:
                top_list.append(num)
                if len(top_list) == k:
                    return top_list

        return top_list

Summary and reflection

Counting frequencies with a hash map is the straightforward first step. Sorting by frequency works, but because the maximum frequency is bounded by the length of nums, the counts can be moved into buckets and the solution can stay at O(n) time without sorting.