Top K Frequent Elements

Objective:

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

---

Pattern: Arrays and Hashing

---

Approach:

1. Create a HashMap that holds the element as the key and frequency as the value.
2. Iterate through the input array and store in HashMap.
3. Since HashMap is not ordered, use a Priority Queue to keep track of the K most frequent elements.

For Priority Queue:

Queue <Integer> pq = new PriorityQueue<>((a, b) -> hashMap.get(b) - hashMap.get(a)); 

The PriorityQueue is initialized with a custom comparator using a lambda expression (a, b) -> hashMap.get(b) - hashMap.get(a).

Here's what each part does:

hashMap.get(b) - hashMap.get(a): This is the custom comparator. It compares two integers a and b based on their corresponding values in a HashMap named hashMap. The elements with higher values in the HashMap will have a higher priority in the PriorityQueue. So, the PriorityQueue will be a min-heap based on the frequencies stored in the HashMap.
(a, b) -> ...: This is a lambda expression defining a Comparator. It takes two parameters a and b (representing elements in the PriorityQueue) and returns the result of the subtraction of their corresponding values in the HashMap. If the result is negative, a has a higher priority; if positive, b has a higher priority; if zero, they have equal priority.

So, in summary, this line of code creates a PriorityQueue of integers (Queue pq) with a custom comparator based on the frequencies stored in the HashMap (hashMap). The elements with higher frequencies will have higher priority in the PriorityQueue.

---

Big-O Notation:

Time Complexity: O(N + M * log(M) + K * log(M))
Counting frequency = O(N)
Priority Queue = O(M * log(M))
Result array = O(K * log(M))

Space Complexity: O(M)
HashMap = O(M)
Priority Queue = O(M)

Note: N is total/all elements in input array, M is unique elements in input array, and K is specified value.

---

Code:

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // input: array and k value. 
        // output: top k frequency 
        int [] result = new int [k];

        // hashmap <num, freq>
        Map <Integer, Integer> hashMap = new HashMap<>();

        // go through nums array, add freq to hashmap
        for(int i = 0; i < nums.length; i++){
            hashMap.put(nums[i], hashMap.getOrDefault(nums[i],0)+1);
        }

        // priority queue
        Queue <Integer> pq = new PriorityQueue<>((a, b) -> hashMap.get(b) - hashMap.get(a)); 

        // go through hashmap, add to priority queue
        for(int key: hashMap.keySet()){
            pq.add(key);
        }

        // return k max values and add to result array
        for(int i = 0; i < k; i++){
            result[i] = pq.poll();
        }

        return result;
    }
}