Top K Frequent Elements

Leetcode Daily Challenge (22nd May, 2023)

22 May, 2023

Contributors

Lakshit Chiranjiv Sagar

@lakshit-cs

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.

Link: https://leetcode.com/problems/top-k-frequent-elements/description/

Problem Explanation with examples:-

Example 1

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Explanation: The frequency map is {1: 3, 2: 2, 3: 1}. The sorted frequency map is {3: 1, 2: 2, 1: 3}. The keys with the highest frequencies are 1 and 2. The first 2 elements of the keys array are 1 and 2.

Example 2

Input: nums = [1], k = 1
Output: [1]
Explanation: The frequency map is {1: 1}. The sorted frequency map is {1: 1}. The key with the highest frequency is 1. The first 1 element of the keys array is 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.

Intuition:-

Keep a frequency map of all the elements in the array.
Sort the frequency map in ascending order.
Return the last k elements of the sorted frequency map.

Solution:-

Create a frequency map of all the elements in the array by iterating over the array once.
Extract the keys and values of the frequency map and store them in two separate arrays.
Sort the values array in ascending order and store the sorted indices in a separate array using argsort() function.
Create a new dictionary and store the keys and values in the sorted order of the values array using the sorted indices array.
Extract the keys from the sorted dictionary and store them in a separate array.
Reverse the keys array and return the first k elements of the array.

Code:-

JAVA Solution

class Solution {
    
    public static HashMap<Integer, Integer> sortByValue(HashMap<Integer, Integer> hm)
    {
        List<Map.Entry<Integer, Integer> > list =
               new LinkedList<Map.Entry<Integer, Integer> >(hm.entrySet());

        Collections.sort(list, new Comparator<Map.Entry<Integer, Integer> >() {
            public int compare(Map.Entry<Integer, Integer> o1,
                               Map.Entry<Integer, Integer> o2)
            {
                return (o1.getValue()).compareTo(o2.getValue());
            }
        });
         
        HashMap<Integer, Integer> temp = new LinkedHashMap<Integer, Integer>();
        for (Map.Entry<Integer, Integer> aa : list) {
            temp.put(aa.getKey(), aa.getValue());
        }
        return temp;
    }
    
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer,Integer> mp = new HashMap<>();
        
        for(int i:nums){
            mp.put(i,mp.getOrDefault(i,0)+1);
        }

        Map<Integer,Integer> m = sortByValue(mp); 
        
        int[] ans = new int[k];

        int j = 0;
        ArrayList<Integer> keys = new ArrayList<Integer>(m.keySet());

        for(int i=keys.size()-1; i>=(keys.size()-k);i--){
            ans[j++] = keys.get(i);
        }

        
        return ans;
    }
}

Python Solution

import numpy as np
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        mp = {}
        for i in nums:
            if mp.get(i,0) == 0:
                mp[i] = 1
            else:
                mp[i] += 1

        keys = list(mp.keys())
        values = list(mp.values())
        sorted_value_index = np.argsort(values)
        sorted_dict = {keys[i]: values[i] for i in sorted_value_index}

        keys = list(sorted_dict.keys())

        ans = []
        keys.reverse()
        for i in range(k):
            ans.append(keys[i])

        return ans

Complexity Analysis:-

TIME:-

The time complexity is O(nlogn) where n is the number of elements in the array. The time complexity is dominated by the sorting step. The rest of the steps take O(n) time.

SPACE:-

The space complexity is O(n) where n is the number of elements in the array. The frequency map will contain n entries at most. The sorted indices array will contain n entries. The sorted dictionary will contain n entries. The keys array will contain n entries.

References:-

Connect with me:-

java

python

leetcode

dsa