# Top K Frequent Elements

#### 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 = , k = 1
Output: ```

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>());
}
}```

## Step 3:

Finally,

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

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>());
}
}

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

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.

### 0 thoughts on “Top K Frequent Elements”

1. I really like your writing style, fantastic info , regards for posting : D.