Day 7: Top K Frequent Elements - leetcode - Python3

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

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

SOLUTION:

class Solution:

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

        count: dict[int, int] = {}

        freq: List[List[int]] = [[] for i in range(len(nums) + 1)]

        result: List[int] = []

        for n in nums:

            count[n] = count.get(n,0) + 1

            # using hashmap to find the frequency

            #of each occurance

        for val, key in count.items():

            freq[key].append(val)

        for i in range(len(freq) -1,0,-1):

            for n in freq[i]:

                result.append(n)

                if len(result)==k:

                    return result

• Time complexity:
• O(n), where n is the number of elements in the nums list.

Let's go through the code step by step:

1. The count dictionary is created to store the frequencies of each element in the nums list.

2. The freq list is initialized as an empty list with a length of len(nums) + 1. This list will be used to store the elements grouped by their frequencies.

3. A loop is used to iterate over each element n in the nums list.

4. Inside the loop, the frequency of each element is calculated and stored in the count dictionary. The count.get(n, 0) retrieves the current frequency of the element n and increments it by 1. If the element is not present in the dictionary, it defaults to 0 and adds 1 to it.

5. Another loop iterates over the key-value pairs in the count dictionary.

6. Inside this loop, the element val and its frequency key are retrieved.

7. The element val is appended to the freq list at the index corresponding to its frequency key. This means that elements with the same frequency will be grouped together in the freq list.

8. After populating the freq list, another loop is used to iterate over the elements in reverse order, starting from the last index.

9. Inside this loop, another nested loop iterates over the elements n in the freq[i] list, where i represents the frequency.

10. Each element n is appended to the result list, which stores the k most frequent elements.

11. After appending an element to the result list, the length of the result list is checked. If it equals k, the desired number of elements has been added, and the result list is returned as the final output.

12. If the loop completes without returning the result, it means that there are fewer than k distinct elements in the input list, and the function will return the result list containing the available distinct elements.