347. Top K Frequent Elements

Description

The topKFrequent function returns the k most frequent elements from a given list of integers.

Intuition

To determine the k most frequent elements, we need to first count the occurrences of each element. Once we have the frequencies, we can sort the elements based on their frequencies and select the top k.

Approach

1. Count Frequencies: Use a hash map to count the occurrences of each element in the list.
2. Sort by Frequency: Convert the frequency map to a list of pairs and sort it based on the frequency in descending order.
3. Extract Top K: Extract the top k elements from the sorted list.

Complexity

Time Complexity:

O(n log n), where n is the number of elements in the input list. This is due to sorting the frequency list.

Space Complexity:

O(n) for storing the frequency map and the result list.

Code

C++

class Solution {
public:
    std::vector topKFrequent(std::vector& nums, int k) {
        std::unordered_map countMap;
        for (const int& num : nums) {
            countMap[num]++;
        }

        std::vector> freqVec(countMap.begin(), countMap.end());
        std::sort(freqVec.begin(), freqVec.end(), [](const std::pair& a, const std::pair& b) {
            return a.second > b.second;
        });

        std::vector result;
        for (int i = 0; i < k; ++i) {
            result.push_back(freqVec[i].first);
        }

        return result;
    }
};

Python

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        # Sort by frequency and get the top k elements
        return [item for item, freq in count.most_common(k)]

Java

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Create a frequency map
        Map countMap = new HashMap<>();
        for (int num : nums) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        PriorityQueue> maxHeap = 
            new PriorityQueue<>((a, b) -> b.getValue() - a.getValue());
        
        // Add all entries to the max heap
        maxHeap.addAll(countMap.entrySet());
        
        // Extract the top k frequent elements
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = maxHeap.poll().getKey();
        }
        return result;
    }
}

JavaScript

var topKFrequent = function (nums, k) {
    // return k most freq elements
    const maxCount = 0;
    // create map of freq
    const map = {};
    const freqs = [];
    for (const num of nums) {
        map[num] = (map[num] || 0) + 1
    }

    for (const key in map) {
        freqs.push([key, map[key]]);
    }
    const result = freqs.sort((a, b) => b[1] - a[1]).map(arr => parseInt(arr[0]));


    return result.slice(0, k);
};