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]

Example 2:

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

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

The Problem Statement

The problem at hand is to find the K most frequent elements in an integer array. We are given an array of integers, and our task is to return an array containing the K most frequent elements in descending order of their frequency. In simpler terms, we want to find the K numbers that occur most frequently in the given array.

The Java Solution

To tackle this problem, we will use a combination of data structures:

1. HashMap: We will iterate through the input array, storing each unique number as a key and its frequency as the corresponding value in a HashMap.
2. ArrayList of Pairs: We will create an ArrayList to hold pairs of numbers and their frequencies. Each pair consists of a number and its frequency.
3. PriorityQueue: We will use a PriorityQueue (min heap) to efficiently find the K most frequent elements based on their frequencies. We will compare elements in the queue based on their frequencies.

The Code

The Java code provided above demonstrates the solution. It consists of two classes: Pair and Solution. The Pair class represents a number-frequency pair, and the Solution class contains the logic to find the top K frequent elements.

How It Works

1. We first iterate through the input array, populating the HashMap with each number’s frequency.
2. Next, we create an ArrayList of pairs, where each pair contains a number and its frequency.
3. We use a PriorityQueue to efficiently retrieve the top K frequent elements. The PriorityQueue is ordered based on the frequency of elements, with the most frequent elements at the front.
4. Finally, we extract the top K elements from the PriorityQueue and return them in an array.

class Pair {
    int number, frequency;
    public Pair(int n, int fr) {
        number = n;
        frequency = fr;
    }
}
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0;i<nums.length;i++) {
            if (map.containsKey(nums[i])) {
                map.put(nums[i], map.get(nums[i]) + 1);
            } else {
                map.put(nums[i], 1);
            }
        }
        ArrayList<Pair> pairs = new ArrayList<Pair>();
        for (Map.Entry<Integer,Integer> mapElement : map.entrySet()) {
            Integer key = mapElement.getKey();
            int value = (mapElement.getValue());
            pairs.add(new Pair(key, value));
        }

        PriorityQueue<Pair> queue = new PriorityQueue<Pair>(new PairComparator());
        for(int i=0;i<pairs.size();i++) {
            queue.add(pairs.get(i));
        }
        int arr[] = new int[k];
        for(int i=0;i<k;i++) {
            arr[i] = queue.remove().number;
        }
        return arr;
    }
}

class PairComparator implements Comparator<Pair> {
    public int compare(Pair m1, Pair m2)
    {
        return m2.frequency - m1.frequency;
    }
}

Conclusion

The “Top K Frequent Elements” problem is a common coding challenge that can be efficiently solved using data structures like HashMaps and Priority Queues. This Java solution provides an elegant and effective way to find the K most frequent elements in an integer array, making it a valuable addition to your coding toolkit.

Problem Statement: https://leetcode.com/problems/top-k-frequent-elements/