Top K Frequent Elements - Java Solution

1. Introduction

This blog post discusses the "Top K Frequent Elements" problem, a notable challenge in data structure optimization and frequency analysis. The goal is to identify the most frequently occurring elements in an array, a common task in data analytics and algorithm design.

Problem

Given an integer array nums and an integer k, the task is to return the k most frequent elements in the array. The result can be returned in any order.

Examples:

1. Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

2. Input: nums = [1], k = 1

Output: [1]

2. Solution Steps

1. Use a hash map to count the frequency of each element in the array.

2. Create a min heap (priority queue) to keep track of the top k frequent elements.

3. Iterate through the hash map and add each element to the heap, maintaining the heap size to k.

4. If the heap size exceeds k, remove the element with the lowest frequency.

5. The heap will contain the k most frequent elements once all elements are processed.

6. Extract these elements from the heap and return them.

3. Code Program

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.List;
import java.util.ArrayList;

public class TopKFrequentElements {
    public static void main(String[] args) {
        int[] nums = {1, 1, 1, 2, 2, 3};
        int k = 2;
        System.out.println(topKFrequent(nums, k)); // Test the function
    }

    // Function to find the k most frequent elements
    public static List<Integer> topKFrequent(int[] nums, int k) {
        // Count the frequency of each element
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // Create a min heap
        PriorityQueue<Integer> heap = new PriorityQueue<>((n1, n2) -> frequencyMap.get(n1) - frequencyMap.get(n2));

        // Keep only the k most frequent elements in the heap
        for (int num : frequencyMap.keySet()) {
            heap.add(num);
            if (heap.size() > k) {
                heap.poll();
            }
        }

        // Extract the elements from the heap
        List<Integer> topKElements = new ArrayList<>();
        while (!heap.isEmpty()) {
            topKElements.add(heap.poll());
        }

        return topKElements;
    }
}

Output:

[1, 2]

Explanation:

1. topKFrequent: This function identifies the k most frequent elements in the array nums.

2. It uses a hash map to count the frequency of each element.

3. A min heap (priority queue) is then used to keep track of the most frequent elements. The heap compares elements based on their frequency in the hash map.

4. The function iterates over the hash map, adding each element to the heap. If the heap's size exceeds k, it removes the element with the lowest frequency.

5. After processing all elements, the heap contains the k most frequent elements.

6. The function then constructs a list from these elements and returns it.

7. This approach effectively combines a hash map and a min heap to solve the problem efficiently, ensuring only the top k frequent elements are retained.