# Top K Frequent Elements LeetCode Solution

Difficulty Level Medium
Arista Networks Array Cashfree Hashing HBO Heap Shopee Sorting WalmartViews 2501

## Problem Statement

Top K Frequent Elements LeetCode Solution Says that – 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 = , k = 1
```

Output:

``` 
```

Constraints:

• `1 <= nums.length <= 10`5
• `k` is in the range `[1, the number of unique elements in the array]`.
• It is guaranteed that the answer is unique.

## Algorithm:

### Idea:

• In order to find the Top k Frequent Elements. First, we will focus on the frequency of each element present in an array.
• After finding the Frequency of Each element we will make one maximum heap and push all elements into the heap with their Frequency.
• At last, we will make one result list and will pop out the k element from the heap and append that element into the result and return the result.

### Approach:

• At first, We will make one Hashmap and will traverse through the whole array and set the frequency of each element as value and element as Key in the Hashmap.
• After that, we will make one priority queue(maxheap) and again traverse through the whole array and push all the elements as tuple pairs (-value, key) into the maxheap.
• Then, we will run a loop from 0 to K and pop out the elements from maxheap and append the Key of each tuple into the result and return the result.
• Hence We will find the Top K frequent Elements. ```class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
dic = {}

for i in nums:
if i in dic:
dic[i] += 1

else:
dic[i] = 1

max_heap = []
for i in dic:
heapq.heappush(max_heap,(-dic[i],i))

result = []
for i in range(k):
result.append(heapq.heappop(max_heap))

return result

```
```class Solution {
public int[] topKFrequent(int[] nums, int k) {

Map<Integer, Integer> dic = new HashMap<>();
for(int num : nums){ dic.put(num, dic.getOrDefault(num, 0) + 1); }

Queue<Integer> max_heap = new PriorityQueue<>((a, b) -> dic.get(b) - dic.get(a));
for(int key : dic.keySet()){ max_heap.add(key); }

int[] result = new int[k];
for(int i = 0; i < k; i++){
result[i] = max_heap.poll();
}

return result;
}
}```

## Complexity Analysis of Top K Frequent Elements Leetcode Solution:

### Time complexity:

The Time Complexity of the above solution is O(nlogn) where n = the size of the input array. We have traversed the entire array and for each element, we are doing the heapify operation.

### Space complexity:

The Space Complexity of the above solution is O(n) since we are creating a max heap of size n.

SIMILAR QUESTION                 https://leetcode.com/problems/word-frequency/

https://leetcode.com/problems/kth-largest-element-in-an-array/

Translate »