347. Top K Frequent Elements

Problem Description

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= nums.length <= 10⁵
• -10⁴ <= nums[i] <= 10⁴
• k is in the range [1, the number of unique elements in the array]
• It is guaranteed that the answer is unique.

Follow up:

Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

Python Solution

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Count frequencies
        count = Counter(nums)
        
        # Create bucket array where index represents frequency
        bucket = [[] for _ in range(len(nums) + 1)]
        for num, freq in count.items():
            bucket[freq].append(num)
        
        # Collect k most frequent elements
        result = []
        for freq in range(len(bucket) - 1, -1, -1):
            for num in bucket[freq]:
                result.append(num)
                if len(result) == k:
                    return result

Java Solution

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Count frequencies
        Map count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        
        // Create bucket array where index represents frequency
        List[] bucket = new List[nums.length + 1];
        for (int i = 0; i < bucket.length; i++) {
            bucket[i] = new ArrayList<>();
        }
        for (Map.Entry entry : count.entrySet()) {
            bucket[entry.getValue()].add(entry.getKey());
        }
        
        // Collect k most frequent elements
        int[] result = new int[k];
        int index = 0;
        for (int freq = bucket.length - 1; freq >= 0 && index < k; freq--) {
            for (int num : bucket[freq]) {
                result[index++] = num;
                if (index == k) break;
            }
        }
        
        return result;
    }
}

C++ Solution

class Solution {
public:
    vector topKFrequent(vector& nums, int k) {
        // Count frequencies
        unordered_map count;
        for (int num : nums) {
            count[num]++;
        }
        
        // Create bucket array where index represents frequency
        vector> bucket(nums.size() + 1);
        for (const auto& pair : count) {
            bucket[pair.second].push_back(pair.first);
        }
        
        // Collect k most frequent elements
        vector result;
        for (int freq = bucket.size() - 1; freq >= 0 && result.size() < k; freq--) {
            for (int num : bucket[freq]) {
                result.push_back(num);
                if (result.size() == k) break;
            }
        }
        
        return result;
    }
};

JavaScript Solution

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    // Count frequencies
    const count = new Map();
    for (const num of nums) {
        count.set(num, (count.get(num) || 0) + 1);
    }
    
    // Create bucket array where index represents frequency
    const bucket = Array.from({length: nums.length + 1}, () => []);
    for (const [num, freq] of count) {
        bucket[freq].push(num);
    }
    
    // Collect k most frequent elements
    const result = [];
    for (let freq = bucket.length - 1; freq >= 0 && result.length < k; freq--) {
        for (const num of bucket[freq]) {
            result.push(num);
            if (result.length === k) break;
        }
    }
    
    return result;
};

C# Solution

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        // Count frequencies
        Dictionary count = new Dictionary();
        foreach (int num in nums) {
            if (!count.ContainsKey(num)) count[num] = 0;
            count[num]++;
        }
        
        // Create bucket array where index represents frequency
        List[] bucket = new List[nums.Length + 1];
        for (int i = 0; i < bucket.Length; i++) {
            bucket[i] = new List();
        }
        foreach (var pair in count) {
            bucket[pair.Value].Add(pair.Key);
        }
        
        // Collect k most frequent elements
        List result = new List();
        for (int freq = bucket.Length - 1; freq >= 0 && result.Count < k; freq--) {
            foreach (int num in bucket[freq]) {
                result.Add(num);
                if (result.Count == k) break;
            }
        }
        
        return result.ToArray();
    }
}