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, the frequency of 2 is 2, and the frequency of 3 is 1. The two most frequent elements are 1 and 2.

Example 2:

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

Steps to Solve

1. Frequency Counting: Create a HashMap to store the frequency of each element in the input array nums. The key will be the element, and the value will be its frequency.

2. PriorityQueue (Min-Heap): Use a PriorityQueue (min-heap) to store the elements. We'll use a custom comparator to prioritize elements based on their frequency. The min-heap will only hold at most k elements at any time.

3. Populate the Heap: Iterate through the HashMap. 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 root (least frequent element in the heap), remove the root and add the current element.

4. Extract Results: Once the HashMap is processed, the PriorityQueue will contain the k most frequent elements. Extract them into a list and return.

Explanation

The algorithm leverages the properties of a min-heap. By maintaining a heap of size k, we ensure that we always keep track of the k elements with the highest frequencies seen so far. When a new element with a higher frequency is encountered, it replaces the least frequent element in the heap, maintaining the invariant that the heap always contains the k most frequent elements.

Code (Java)

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. Frequency Counting
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 2. PriorityQueue (Min-Heap)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(Comparator.comparingInt(frequencyMap::get));

        // 3. Populate the Heap
        for (int num : frequencyMap.keySet()) {
            if (minHeap.size() < k) {
                minHeap.offer(num);
            } else if (frequencyMap.get(num) > frequencyMap.get(minHeap.peek())) {
                minHeap.poll();
                minHeap.offer(num);
            }
        }

        // 4. Extract Results
        int[] result = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            result[i] = minHeap.poll();
        }
        return result;
    }
}

Complexity Analysis

• Time Complexity: O(N log k), where N is the length of nums. Building the frequency map takes O(N) time. The heap operations (offer and poll) take O(log k) time each, and we perform these at most N times.

• Space Complexity: O(N + k), where N is for the HashMap (in the worst case, all elements are unique) and k is for the PriorityQueue. In practice, the space complexity is often less than O(N) because many elements will have the same frequency.