src.top_k_frequent

Classes

Solution()

class src.top_k_frequent.Solution

topKFrequent(nums: list[int], k: int) → list[int]

Thought process

• Place elements into frequency buckets [index -> [n1, ..., n2]] where index is the frequency of the numbers and [n1, ..., n2] are the numbers that have that frequency

• Return the last k elements

Notes

• time complexity: \(O(n) + O(n) = O(n)\)

• space complexity: \(O(2n) = O(n)\)

topKFrequentCompact(nums: list[int], k: int) → list[int]

Thought process

• We can use a dictionary to store the frequency of each number

• We can sort the dictionary by the frequency and return the last k elements

Notes

• time complexity: \(O(n\log n)\)

• space complexity: \(O(n)\)

  I feel like you could use this in an interview, practically speaking its close to the bucket sort solution, I would probably expand the return value though, either that or kind of just explain it to the interviewer