Top K Frequent Elements

Problem

Let’s take a look at the question,

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

Click Here to go through the question in detail

Approach

From the question, it is clear that we need to get the top most elements but according to the value k.

Example (chopped it from leetcode examples hehe):
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
1 Occurs three times, 2 occurs two times and 3 occurs once.
So, the answer would naturally be 1 and 2.
(only if it were that easy to come up with a solution for this question lmao)

1. Create a hashmap to track how many times a number occurs.

2. Create a list containing lists equal to the length of the input list nums

3. Now periodically append the key to the value as the index.
   What this will do is create a list containing lists which hold the numbers from the input nums but since we would be appending in such a way, the index would be the number of times the number has occurred. Hence we got this sorted.
   It will look something like this, [[], [3], [2], [1], [], [], []].

4. Now all we gotta do is iterate over this list in reverse order up to the k value.

Solution

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:

        ele_count = {}

        for ele in nums:
            ele_count[ele] = ele_count.get(ele, 0) + 1

        count_arr = [[] for i in range(len(nums)+1)]
        for key, value in ele_count.items():
            count_arr[value].append(key)


        result = []
        for i in range(len(count_arr)-1, 0, -1):
            for n in count_arr[i]:
                result.append(n)

                if len(result) == k:
                    return result

Do you not get the concept?

hey, it is a complex problem but once you understand why we did what we did and why we chose these particular data structures, things get easy.