0005 - Top K Frequent Elements - Revise

Given an integer array nums and an integer k, return the k most frequent elements within the array.

The test cases are generated such that the answer is always unique.

You may return the output in any order.

Example 1:

Input: nums = [1,2,2,3,3,3], k = 2

Output: [2,3] Example 2:

Input: nums = [7,7], k = 1

Output: [7]

Solution¶

1. Creating Frequency Map

• nums = [1,1,1,2,2,3] # example
• numdict = {1:3, 2:2, 3:1} # counts how many times each number appears

2. Bucket Sort Approach - We create a bucket sort structure where:

• Creates a list where index represents frequency (freqlist)

• Each bucket stores numbers that appear that many times

• pythonCopyfreqlist = [[], [3], [2], [1], [], [], []]

  • index 1 has [3] because 3 appears once
  • index 2 has [2] because 2 appears twice
  • index 3 has [1] because 1 appears thrice

3. Collecting Results -

• Iterating through freqlist from end (highest frequency) to start
• Adding numbers to result until we have k elements

Complexity Analysis

- Time Complexity: O(n) where n is length of nums
- Space Complexity: O(n) to store the dictionary and bucket list

In [1]:

def topKFrequent(nums,k):
    numdict={}
    
    for num in nums:
        numdict[num]=1+numdict.get(num,0)
    
    freqlist=[]
    for i in range(len(nums)+1):
        freqlist.append([])        
    for key, val in numdict.items():
        freqlist[val].append(key)
    
    result=[]
    for i in range(len(freqlist)-1,0,-1):
        for num in freqlist[i]:
            result.append(num)
        if len(result)==k:
            return result

In [2]:

topKFrequent([1,2,2,3,3,3],2)

Out[2]:

[3, 2]

In [3]:

{1:2,3:4}.items()

Out[3]:

dict_items([(1, 2), (3, 4)])

In [4]:

freqlist=[]
for i in range(5):
    freqlist.append([])
print(freqlist)

[[], [], [], [], []]