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 = 2Output:[1,2]

**Example 2:**

Input:nums = [1], k = 1Output:[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

*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.