Skip to main content

🟨 Top K Frequent Elements (#347)

🔗 Problem Link​

📋 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]

Example 2​

Input: nums = [1], k = 1
Output: [1]

🔑 Key Insights & Approach​

Core Observation: We need to count frequencies and then find the k elements with highest counts.

Why Bucket Sort?

  • O(n) time complexity vs O(n log n) for sorting
  • Frequency values are bounded by array length
  • Can use bucket sort where index = frequency

Approaches:

  1. HashMap + Heap: O(n log k)
  2. HashMap + Bucket Sort: O(n) - optimal
  3. HashMap + Sorting: O(n log n)

Pattern: "Top K Elements" pattern using bucket sort optimization.

🐍 Solution: Python​

Approach 1: Bucket Sort (Optimal)​

Time Complexity: O(n) | Space Complexity: O(n)

from typing import List
from collections import Counter

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count frequencies
        count = Counter(nums)

        # Create buckets where index = frequency
        buckets = [[] for _ in range(len(nums) + 1)]
        for num, freq in count.items():
            buckets[freq].append(num)

        # Collect k most frequent elements
        result = []
        for i in range(len(buckets) - 1, 0, -1):
            for num in buckets[i]:
                result.append(num)
                if len(result) == k:
                    return result

        return result

Approach 2: Heap​

Time Complexity: O(n log k) | Space Complexity: O(n)

from typing import List
from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)

        # Use heap to find k most frequent
        return heapq.nlargest(k, count.keys(), key=count.get)

🔵 Solution: Golang​

Approach 1: Bucket Sort​

Time Complexity: O(n) | Space Complexity: O(n)

func topKFrequent(nums []int, k int) []int {
    // Count frequencies
    count := make(map[int]int)
    for _, num := range nums {
        count[num]++
    }

    // Create buckets
    buckets := make([][]int, len(nums)+1)
    for num, freq := range count {
        buckets[freq] = append(buckets[freq], num)
    }

    // Collect k most frequent
    result := make([]int, 0, k)
    for i := len(buckets) - 1; i >= 0 && len(result) < k; i-- {
        result = append(result, buckets[i]...)
    }

    return result[:k]
}

📚 References​