347. Top K Frequent Elements – Leetcode Solutions

Example 1:

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

Example 2:

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

from collections import Counter
import heapq

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        # Step 1: Count the frequency of each element in nums using a Counter
        freq_map = Counter(nums)
        # The Counter will store elements as keys and their frequencies as values.
        # For example, if nums = [1,1,1,2,2,3], freq_map would be {1: 3, 2: 2, 3: 1}

        # Step 2: Use a heap to keep the top k elements
        # The heapq library can be used to create a min-heap to maintain the top k frequent elements
        # In Python, heapq is by default a min-heap, so we need to use negative frequencies
        # to simulate a max-heap (or simply push/pop tuples where we compare based on frequencies).
        
        # We use nlargest from heapq to get the top k elements based on frequency
        # It internally manages a heap of size k and extracts the largest elements
        return [item for item, freq in heapq.nlargest(k, freq_map.items(), key=lambda x: x[1])]

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        // Step 1: Use a hash map to count the frequency of each element in nums
        unordered_map<int, int> freqMap;
        
        // Loop through the nums array and count the occurrences of each number
        for (int num : nums) {
            freqMap[num]++;
        }
        
        // Step 2: Use a priority queue (min-heap) to keep track of the top k frequent elements
        // The priority queue stores pairs of (frequency, element)
        // We use greater<>() to make it a min-heap based on frequency
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
        
        // Loop through the frequency map
        for (auto& entry : freqMap) {
            // Push the current element and its frequency into the min-heap
            minHeap.push({entry.second, entry.first});
            
            // If the heap size exceeds k, we pop the smallest element (the least frequent one)
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        
        // Step 3: Extract the top k frequent elements from the min-heap
        vector<int> result;
        while (!minHeap.empty()) {
            result.push_back(minHeap.top().second); // Extract the element, not the frequency
            minHeap.pop();
        }
        
        // Step 4: Return the result (it doesn't have to be in any specific order)
        return result;
    }
};

var topKFrequent = function(nums, k) {
    // Step 1: Create a frequency map to count occurrences of each number.
    const frequencyMap = new Map();
    
    // Iterate through each number in the nums array and count their occurrences.
    for (let num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }

    // Step 2: Create an array of buckets where the index represents the frequency.
    // The value at each index will be an array of numbers that have that frequency.
    const bucket = Array(nums.length + 1).fill().map(() => []);

    // Populate the bucket array. For each number and its frequency in the frequencyMap,
    // put the number in the corresponding bucket (at the index equal to its frequency).
    for (let [num, freq] of frequencyMap) {
        bucket[freq].push(num);
    }

    // Step 3: Collect the k most frequent elements.
    const result = [];

    // Start from the highest possible frequency and work backwards.
    for (let i = bucket.length - 1; i >= 0 && result.length < k; i--) {
        if (bucket[i].length > 0) {
            // Add all numbers in the current bucket to the result.
            result.push(...bucket[i]);
        }
    }

    // Step 4: Return the first k elements from the result.
    return result.slice(0, k);
};

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // Step 1: Create a HashMap to store the frequency of each element in the array
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        
        // Traverse through the array and calculate the frequency of each element
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Use a priority queue (min-heap) to store the elements by their frequency
        // The priority queue will store elements in increasing order of frequency
        PriorityQueue<Map.Entry<Integer, Integer>> minHeap = new PriorityQueue<>(
            (a, b) -> a.getValue() - b.getValue() // Comparator to sort entries by frequency
        );

        // Step 3: Add entries from the frequency map to the min-heap
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            minHeap.offer(entry);
            // If the heap size exceeds k, remove the element with the lowest frequency
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // Step 4: Extract the k most frequent elements from the priority queue
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll().getKey();
        }

        // Step 5: Return the result array containing the k most frequent elements
        return result;
    }
}