Top k frequent elements

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 = [4, 1, 2, 2, 3, 3, 3, 5, 5, 5, 5], k = 3

Output: [5, 3, 2]

Explanation:

In this example, the input array contains elements with various frequencies. The most frequent element is 5, which appears four times. The next most frequent element is 3, which appears three times. Finally, the element 1 appears twice. Therefore, the top 3 frequent elements are [5, 3, 1].

Example 2

Input: nums = [10, 10, 10, 20, 20, 20, 30, 30, 40, 40, 50, 50, 60, 70],

          k = 4

Output: [10, 20, 30, 40]

Explanation

In this example, each element in the input array has a unique frequency. The elements 10, 20, 30, and 40 all appear three times, making them the top 4 frequent elements. Therefore, the output is [10, 20, 30, 40].

Approach

We aim to find the k most frequent elements in an integer array. To achieve this, we first count the frequency of each element in the array using a HashMap. Then, we use a PriorityQueue to efficiently retrieve the top k frequent elements based on their frequencies. By adding all entries from the frequency map to the PriorityQueue and using a custom comparator to ensure elements are ordered by frequency count, we can quickly retrieve the top k elements with the highest frequencies. Finally, we return the list containing these top k frequent elements.

1. Iterate through the input array nums.
2. For each element num, update its frequency count in the HashMap frequencyMap. If it's the first occurrence, initialize its count to 1; otherwise, increment its count.
3. Create a PriorityQueue called pq to store the entries from the frequency map.
4. Use a custom comparator to ensure that the PriorityQueue is ordered based on the frequency count in decreasing order.
5. Add all entries from the frequency map to the PriorityQueue pq. This operation is done in linear time.
6. Perform k poll operations on the PriorityQueue pq to retrieve the top k frequent elements.
7. Each poll operation removes the entry with the highest frequency count from the PriorityQueue.
8. Create a list to store the top k frequent elements.
9. After retrieving the top k frequent elements from the PriorityQueue, add their keys (i.e., the elements themselves) to the result list.
10. Return the result list containing the top k frequent elements.

Complexity

• Time Complexity: O(n*logn), where n is the number of elements in the input array.
• Space Complexity: O(n+k), where n is the number of elements in the input array.

Code

import java.util.*;


public class TopKFrequentElements {

    public List<Integer> topKFrequent(int[] nums, int k) {

        // Count the frequency of each element using a HashMap
        Map<Integer, Integer> frequencyMap = new HashMap<>();

        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Use a PriorityQueue to keep track of the top k frequent elements
        PriorityQueue<Map.Entry<Integer, Integer>> pq = new PriorityQueue<>(
            (a, b) -> b.getValue() - a.getValue()); // Max heap based on frequency

        // Add all entries from the frequency map to the priority queue
        for (Map.Entry<Integer, Integer> entry : frequencyMap.entrySet()) {
            pq.offer(entry);
        }

        // Retrieve the top k frequent elements from the priority queue
        List<Integer> result = new ArrayList<>();
        for (int i = 0; i < k; i++) {
            result.add(pq.poll().getKey());
        }
        return result;
    }

    public static void main(String[] args) {
        TopKFrequentElements solution = new TopKFrequentElements();

        int[] nums1 = {4, 1, 2, 2, 3, 3, 3, 5, 5, 5, 5};
        int k1 = 3;
        System.out.println("Input: nums = " + Arrays.toString(nums1) + ", k = " + k1);
        System.out.println("Output: " + solution.topKFrequent(nums1, k1));

        int[] nums2 = {10, 10, 10, 20, 20, 20, 30, 30, 40, 40, 50, 50, 60, 70};
        int k2 = 4;
        System.out.println("\nInput: nums = " + Arrays.toString(nums2) + ", k = " + k2);
        System.out.println("Output: " + solution.topKFrequent(nums2, k2));
    }
}

Output

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

Input: nums = [10, 10, 10, 20, 20, 20, 30, 30, 40, 40, 50, 50, 60, 70], k = 4
Output: [20, 10, 40, 50]