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] Explanation: The frequency of 1 is 3, and the frequency of 2 is 2. The most frequent two elements are 1 and 2. Note that even if we have multiple occurrences of the same number, we should only include it once in our output.

Example 2:

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

Steps:

1. Frequency Counting: Create a map (or object in JavaScript/TypeScript) to store the frequency of each element in the input array nums.
2. Heap (Priority Queue): Use a min-heap data structure to store the elements. The heap will be ordered by frequency. We only need to keep track of the k most frequent elements, so we limit the heap size to k.
3. Iterate and Update Heap: Iterate through the frequency map. For each element and its frequency:
   • If the heap size is less than k, add the element to the heap.
   • If the heap size is equal to k, and the current element's frequency is greater than the frequency of the least frequent element in the heap (the root of the min-heap), remove the root and add the current element.
4. Extract Results: After iterating through the entire frequency map, the heap will contain the k most frequent elements. Extract them from the heap and return.

Explanation:

The solution uses a min-heap to efficiently maintain the k most frequent elements encountered so far. A min-heap ensures that the element with the lowest frequency is always at the root. By comparing the frequency of each element with the root's frequency, we can efficiently decide whether to add the element to the heap (if it's more frequent than the least frequent element currently in the heap) or not. This approach avoids sorting the entire array, resulting in a better time complexity.

Code:

import { MinPriorityQueue } from '@datastructures-js/priority-queue';

function topKFrequent(nums: number[], k: number): number[] {
    const frequencyMap: Map<number, number> = new Map();

    // Count frequencies
    for (const num of nums) {
        frequencyMap.set(num, (frequencyMap.get(num) || 0) + 1);
    }

    // Min-heap to store k most frequent elements
    const minHeap = new MinPriorityQueue({ priority: (x) => x[1] }); //Priority based on frequency


    // Iterate through the frequency map and update the heap
    for (const [num, freq] of frequencyMap) {
        minHeap.enqueue([num, freq]);
        if (minHeap.size() > k) {
            minHeap.dequeue();
        }
    }

    // Extract the k most frequent elements from the heap
    const result: number[] = [];
    while (!minHeap.isEmpty()) {
        result.push(minHeap.dequeue().element[0]);
    }

    return result.reverse(); //Reverse to get decreasing order of frequency.
};

Note: This code uses the @datastructures-js/priority-queue library for the min-heap implementation. You'll need to install it using: npm install @datastructures-js/priority-queue

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 operations at most N times.
• Space Complexity: O(N + k), where N is for the frequency map and k is for the heap. In the worst case, the frequency map could store all unique numbers, and the heap will store at most k elements.