How to Find Top‑K Frequent Elements in O(n) Time Using Bucket Sort

In data processing and algorithm design, it is often necessary to locate the elements with the highest occurrence frequency in a large dataset. This article addresses how to quickly find the top k frequent elements in a given integer array nums and integer k, achieving a time complexity better than O(n log n).

Problem Description

Given an integer array nums and an integer k, return the k elements that appear most frequently. Constraints:

1 ≤ nums.length ≤ 10^5 k is in the range [1, number of distinct elements]

The answer is unique; the set of the top k frequent elements is unique

The algorithm must have a time complexity better than O(n log n)

Algorithm Analysis

Conventional Method

A straightforward solution involves three steps:

Use a hash map to count the frequency of each element – O(n).

Sort the hash map by frequency – O(n log n).

Take the first k elements.

This yields a total time complexity of O(n log n), which does not meet the requirement.

Optimized Method: Bucket Sort

To reduce the complexity to O(n), we apply the bucket‑sort idea:

Count frequencies: Traverse nums and build a hash map of element → count. O(n).

Build buckets: Create an array buckets of size n+1 where the index represents a frequency and each bucket stores the list of elements with that frequency. O(n).

Collect results: Iterate the buckets from high to low, gathering elements until k elements have been collected. O(n).

Code Implementation

Below is the Go language implementation:

package main

import (
    "fmt"
    "strconv"
    "strings"
)

func solution(nums []int, k int) string {
    // 1. Count frequencies
    freqMap := make(map[int]int)
    for _, num := range nums {
        freqMap[num]++
    }

    // 2. Build buckets
    n := len(nums)
    buckets := make([][]int, n+1)
    for num, freq := range freqMap {
        buckets[freq] = append(buckets[freq], num)
    }

    // 3. Collect results
    result := []int{}
    for i := n; i >= 0 && len(result) < k; i-- {
        if len(buckets[i]) > 0 {
            result = append(result, buckets[i]...)
        }
    }

    // Trim to k elements
    result = result[:k]

    // Convert result to string
    strResult := make([]string, len(result))
    for i, num := range result {
        strResult[i] = strconv.Itoa(num)
    }
    return strings.Join(strResult, ",")
}

func main() {
    fmt.Println(solution([]int{1,1,1,2,2,3}, 2) == "1,2")
    fmt.Println(solution([]int{1}, 1) == "1")
}

Code Explanation

Count frequencies: Use map[int]int to record how many times each element appears.

Build buckets: Allocate a two‑dimensional slice of size n+1; buckets[i] stores elements whose frequency equals i.

Collect results: Starting from the highest‑frequency bucket, add elements to the result set until k elements are gathered.

Result conversion: Transform the integer slice into a comma‑separated string.

Time Complexity Analysis

Counting frequencies: O(n)

Building buckets: O(n)

Collecting results: O(n) in the worst case

Total time complexity: O(n)

Test Results

Running the main function prints true for both examples, confirming that the implementation satisfies the problem requirements.

Conclusion

By employing the bucket‑sort technique, we successfully reduce the algorithm’s time complexity to O(n), meeting the problem’s constraints. This approach is highly effective for large‑scale data and performance‑critical applications.