Top K Frequent Elements- LeetCode Solution and Approach

 347. Top K Frequent Elements - LeetCode - Medium

Solve this problem in LeetCode

Problem Description:

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 <= 10^5

-10^4 <= nums[i] <= 10^4

k is in the range [1, the number of unique elements in the array].

It is guaranteed that the answer is unique.

Approach:

1. Frequency Counting using HashMap

• We traverse the array and maintain a frequency map using HashMap<Integer, Integer>.
• This map stores each unique element as a key and its occurrence as the value.
• Time Complexity: O(n) (since we iterate over nums once).

2. Using a Max-Heap (PriorityQueue) for Sorting

• We use a PriorityQueue (max-heap) to sort elements based on their frequency.
• The comparator ensures that the elements with higher frequency are at the top.
• Time Complexity: O(n log n) (due to sorting operations in the heap).

3. Extracting the Top K Frequent Elements

• We poll the top k elements from the heap and store them in the result array.
• Time Complexity: O(k log n) (polling k elements from the heap).

JAVA:

Time Complexity : 0(n log n)  due to heap operations.

Space Complexity: 0(n) for storing the frequency map and heap.

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map < Integer, Integer > map = new HashMap < > ();
        for (int n: nums) map.put(n, map.getOrDefault(n, 0) + 1);
        Queue < Map.Entry < Integer, Integer >> pq = new PriorityQueue < > ((a, b) - > b.getValue() - a.getValue());
        pq.addAll(map.entrySet());
        int[] res = new int[k];
        while (k-- > 0) res[k] = pq.poll().getKey();
        return res;
    }
}

Keep Learning and Practicing with Programming Chaska !!!