Top K Frequent Elements

Hi Geeks! Welcome to 100 Days Leetcode Challenge.

Day 1

Here is our given problem,

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

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

Example 2:

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

Note:

  • You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
  • Your algorithm’s time complexity must be better than O(n * n), where n is the array’s size.

Problem explanation

In our problem, they asked to return the k most frequent elements.

k most frequent elements

If k is 2, then we have to return the two elements which should have the same frequency.

In our case, 1 and 3 have the same frequency. So we want to return 1 and 3.

How to approach this problem?

We going to solve this problem by using HashMap and TreeMap.

3 Steps to Solve this problem

step 1:

Use HashMap, store keys as elements and values as frequencies.


        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums)
        {
            if(map.containsKey(num))
            {
                int value = map.get(num);
                map.put(num,++value);
            }
            else
                map.put(num,1);
        }

STEP 2:

Use TreeMap, store keys as frequencies and values as respective elements.

That is, in the above example, we have

1 has Frequency 3

2 has Frequency 2

3 has Frequency 3

Now, we going to store frequency in key, respective elements in values.

        TreeMap<Integer,List<Integer>> freqMap = new TreeMap<>();
        for(int num : map.keySet())
        {
            int freq = map.get(num);
            if(!freqMap.containsKey(freq))
            {
               freqMap.put(freq,new ArrayList<Integer>());
            }
            freqMap.get(freq).add(num);
        }

Step 3:

Finally,

       List<Integer> res = new ArrayList<>();
        while(res.size() < k)
        {
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            res.addAll(entry.getValue());
        }

With simple logic, declare a list to store the K most frequent elements.

.pollLastEntry()

This method returns the last key and value’s in the map. Here, we just returning from the treemap.

According to our example, this .pollLastEntry() method returns the last key as 3 and values as 1,3. We capturing that in Map.Entry<Integer,List<Integer>> entry;

entry.getValue()

This method returns the values of the map. In our case, it returns the 1,2. Add these elements in our list res.

Check if res.size() < k, then come out of while loop. Because, we already got K most frequent elements.

Solution

    class Solution {
    public List<Integer> topKFrequent(int[] nums, int k) {
        //Store it in map 
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int num : nums)
        {
            if(map.containsKey(num))
            {
                int value = map.get(num);
                map.put(num,++value);
            }
            else
                map.put(num,1);
        }
        
        //Use TreeMap to store the frequency with respective elements
        TreeMap<Integer,List<Integer>> freqMap = new TreeMap<>();
        for(int num : map.keySet())
        {
            int freq = map.get(num);
            if(!freqMap.containsKey(freq))
            {
               freqMap.put(freq,new ArrayList<Integer>());
            }
            freqMap.get(freq).add(num);
        }
        
        //result
        List<Integer> res = new ArrayList<>();
        while(res.size() < k)
        {
            Map.Entry<Integer, List<Integer>> entry = freqMap.pollLastEntry();
            res.addAll(entry.getValue());
        }
        
        return res;
    }
}

Time Complexity: O(nLogn)

Because we have used treemap, which takes O(nlogn) times to store the elements in the map.

Space complexity: O(n)

Since, we have used two maps, so it takes O(n) space.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s