Published: Sep 24, 2022

## Introduction

The problem asks about a frequency of array elements. This means we should start from getting the frequency. Then, sort the elements based on the frequencies.

## Problem Description

Given an integer array

`nums`

and an integer`k`

, return the k most frequent elements. You may return the answer in any order.Constraints:

`1 <= nums.length <= 10**5`

`-10**4 <= nums[i] <= 10**4`

`k`

is in the range`[1, the number of unique elements in the array]`

.- It is guaranteed that the answer is unique.

## Examples

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

```
Example 2
Input: nums = [1], k = 1
Output: [1]
```

## Analysis

The first step is to get a frequency list.
The following steps are: sort by frequency, then get first k elements.
The first solution uses heap’s push and pop, which is a basic approach.
The second solution uses Python heap’s `nlargest`

function.
It is straightforward and effective, but only when the function came up in our mind.

## Solution

```
class TopKFrequentElements:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
counter = collections.Counter(nums)
queue = []
for num, counts in counter.items():
heapq.heappush(queue, (-counts, num))
result = []
for _ in range(k):
_, num = heapq.heappop(queue)
result.append(num)
return result
```

```
class TopKFrequentElements:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
counter = collections.Counter(nums)
return heapq.nlargest(k, counter.keys(), key=counter.get)
```

## Complexities

- Time:
`O(nlog(n))`

- Space:
`O(n)`