Top K Frequent Elements medium

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.

Example 1:

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

Example 2:

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

Steps

1. Count Frequencies: Create a dictionary to store the frequency of each element in the input array nums.
2. Create Priority Queue: Use a min-heap priority queue (or similar data structure) to store the elements along with their frequencies. We'll use a custom class or tuple to represent this pairing. The priority queue will be ordered by frequency (ascending order). This means elements with lower frequencies will be at the top of the queue.
3. Populate Priority Queue: Iterate through the frequency dictionary. For each element and its frequency, add it to the priority queue. If the queue's size exceeds k, remove the element with the lowest frequency (the root of the min-heap).
4. Extract Top K: After iterating through all elements, the priority queue will contain the k elements with the highest frequencies. Extract and return these elements.

Explanation

The key idea is to use a min-heap to efficiently track the k most frequent elements. A min-heap ensures that the element with the lowest frequency is always at the top. When we encounter a new element with a higher frequency than the current lowest frequency element in the heap, we remove the lowest and add the new element. This way, the heap always contains the top k most frequent elements encountered so far. This avoids sorting the entire frequency list, making it more efficient for large inputs.

Code

using System;
using System.Collections.Generic;
using System.Linq;

public class Solution {
    public int[] TopKFrequent(int[] nums, int k) {
        // Count frequencies
        Dictionary<int, int> freqMap = new Dictionary<int, int>();
        foreach (int num in nums) {
            freqMap[num] = freqMap.GetValueOrDefault(num, 0) + 1;
        }

        // Use a min-heap to store (element, frequency) pairs
        PriorityQueue<(int, int), int> minHeap = new PriorityQueue<(int, int), int>(); // (element, frequency), priority = frequency

        // Populate the min-heap
        foreach (KeyValuePair<int, int> entry in freqMap) {
            minHeap.Enqueue(entry, entry.Value); 
            if (minHeap.Count > k) {
                minHeap.Dequeue(); // Remove the least frequent if size exceeds k
            }
        }

        // Extract top k frequent elements
        int[] result = new int[k];
        int i = k - 1;
        while (minHeap.Count > 0) {
            result[i--] = minHeap.Dequeue().Item1;
        }

        return result;
    }
}

Complexity

• Time Complexity: O(N log k), where N is the length of nums. Building the frequency map takes O(N) time. The heap operations (enqueue and dequeue) take O(log k) time each, and we perform these at most N times.
• Space Complexity: O(N) in the worst case, to store the frequency map. The heap's space complexity is O(k). Therefore, the overall space complexity is dominated by the frequency map.

Note: This solution utilizes C#'s built-in PriorityQueue. If you're using a version of C# that doesn't have a built-in priority queue, you'll need to implement your own min-heap using a binary heap or a similar data structure. The core logic remains the same.