Top K Frequent Elements

There are countless ways to approach this problem and optimize your solution. In this article, we’ll explore various strategies to tackle this problem. Let’s see the problem statement first.

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.

This problem is all about numbers and their frequencies. Let’s dive in and see how we can use our coding skills to find the most popular digits in the array!

---

Approach 1: Hashmap

1. Iterate through the input array and count the frequency of each element in a hashmap.

2. Sort the values of the map in decreasing order of the frequency of each element.

3. Store the top K values in the result array.

4. Return the result array.

// ES6 Arrow Function
const topKFrequent = (nums, k) => {
    let map = new Map();

    for(let i of nums) {
        let count = map.get(i) || 0;
        map.set(i, count + 1);
    }

    let i = 0, 
    result = [], 
    values = [...map.entries()].sort((a,b) => b[1] - a[1]);

    while(i < k) {
        result.push(values[i][0]);
        i++;
    }

    return result;
};

Time Complexity: O(N Log(N))

Space Complexity: O(N)

---

Approach 2: Bucket Sort

In this approach, we use a map to store the frequency of each element and then group elements with the same frequency into a bucket array. Finally, it iterates over the bucket array in reverse order and extracts the top k frequent elements from it, which are returned as the final output.

1. Create a new Map object, bucket array, and result array.

2. Iterate over the input nums array and store the frequency of each element in the Map.

3. Iterate over the Map and group elements with the same frequency together in the bucket array.

4. Iterate through the bucket array in reverse order and push its elements to the result array.

5. Repeat step 4, k times to get the k most frequent elements.

// ES6 Arrow Function
const topKFrequent = (nums, k) => {
    let map = new Map();
    let bucket = [], result = [];

    for(let i of nums) {
        let count = map.get(i) || 0;
        map.set(i, count+1)
    }

    for(let [i, freq] of map) {
        bucket[freq] = (bucket[freq] || new Set()).add(i);
    }

    for(let i = bucket.length - 1; i >= 0; i--) {
        if(bucket[i]) result.push(...bucket[i]);
        if(result.length >= k) break;
    }

    return result;
}

Time Complexity: O(N)

Space Complexity: O(N)

---

Approach 3: Priority Queue

1. Build a hash map of the input array where the keys are the elements of the array and the values are their frequencies. You can use a Map to build the hash map.

2. Create a max binary heap priority queue and enqueue each element from the hash map into it. The priority of each element should be its frequency.

3. Dequeue the top k elements from the priority queue and push them into a results array. You can use a loop to do this k time.

4. Return the results array.

// ES6 Arrow Function
var topKFrequent = (nums, k) => {
    let results = [];
    let map = {};

    nums.forEach(n => map[n] ? map[n] += 1 : map[n] = 1);

    let pq = new PriorityQueue();

    for(let key in map){
        pq.enqueue(key, map[key]);
    }


    for(let i = 0; i < k; i++){
        results.push(pq.dequeue());
    }

    return results;
};

Priority Queue:

// ES6 Arrow Function
class Node {
    constructor(val, priority){
        this.val = val;
        this.priority = priority;
    }
}


class PriorityQueue {
    constructor(){
        this._values = [];
    }

    enqueue(val, priority){
        this._values.push(new Node(val, priority));
        this._traverseUp();
    }

    dequeue(){
        const max = this._values[0];
        const end = this._values.pop();
        if(this._values.length > 0){
            this._values[0] = end;
            this._traverseDown();
        }
        return max.val;

    }

    _traverseUp(){
        let idx = this._values.length - 1;
        const el = this._values[idx];
        while(idx > 0){
            let pIdx = Math.floor((idx - 1) / 2);
            let parent = this._values[pIdx];
            if(el.priority <= parent.priority) break;
            this._values[pIdx] = el;
            this._values[idx] = parent;
            idx = pIdx;
        }
    }

    _traverseDown(){
        let leftChildIdx = null;
        let rightChildIdx = null;
        let leftChild = null;
        let rightChild = null;
        let swapIdx = null;

        let idx = 0;
        const el = this._values[idx];
        while(true){
            swapIdx = null;
            leftChildIdx = 2 * idx + 1;
            rightChildIdx = 2 * idx + 2;

            if(leftChildIdx < this._values.length){
                leftChild = this._values[leftChildIdx];
                if(leftChild.priority > el.priority){
                    swapIdx = leftChildIdx;
                }
            }

            if(rightChildIdx < this._values.length){
                rightChild = this._values[rightChildIdx];
                if(
                    (swapIdx === null && rightChild.priority > el.priority) ||
                    (swapIdx !==null && rightChild.priority > leftChild.priority)
                ) {
                    swapIdx = rightChildIdx;
                }
            }

            if(swapIdx === null) break;
            this._values[idx] = this._values[swapIdx];
            this._values[swapIdx] = el;
            idx = swapIdx
        }
    }
}

Time Complexity: O(N log(K)), where n is the number of elements in the input array and k is the number of most frequent elements to return.

Space Complexity: O(N + K), O(N) for hashmap and O(K) for Priority Queue.

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

---

References- I would like to thank Alex for the Priority Queue answer on leetcode. (Approach 3)

Problem - Leetcode 347