# [Top K Frequent Elements](https://leetcode.com/problems/top-k-frequent-elements/)
###### tags: `Leetcode`, `Medium`, `Arrays and Hashing`

## Approach
* Add the count of every element in input to a hashmap where the key is the number and the value is the count
* Initialize a List where the index position is the count and value is the list of numbers occurring that many times in the input
* Iterate the list in descending order and keep adding numbers to the result array until the length of the array is equal to `k`

## Asymptotic Analysis
### Time Complexity: **O(N)**
### Space Complexity: **O(N)**

## Code

from typing import List


class TopKFrequentElements:

    @staticmethod
    def top_k_frequent(numbers: List[int], k: int) -> List[int]:
        result = []
        frequency_map = {}
        frequency_list = [[] for _ in range(len(numbers) + 1)]

        # map number to its frequency of occurrence
        for number in numbers:
            frequency_map[number] = 1 + frequency_map.get(number, 0)

        # create a list where index is the count and value is the number
        for number, count in frequency_map.items():
            frequency_list[count].append(number)

        # iterate through frequency_list in descending order and append to
        # result
        for index in range(len(frequency_list) - 1, -1, -1):
            for num in frequency_list[index]:
                result.append(num)
                if len(result) == k:
                    return result
        return result


nums, k = [1, 1, 1, 2, 2, 3], 2
print(TopKFrequentElements.top_k_frequent(nums, k))