Top K Frequent Elements

Problem

https://leetcode.com/problems/top-k-frequent-elements/

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]

Example 3:

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

Output: [1,2]

Constraints:

• 1 <= nums.length <= 10:sup:`5`

• -10:sup:`4`<= nums[i] <= 10:sup:`4`

• 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.

Pattern

Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue)

Approaches

Sorting

Code

def topKFrequent(nums: list[int], k: int) -> list[int]:
    counter = {}
    for n in nums:
        if n in counter:
            counter[n] += 1
        else:
            counter[n] = 1

    counter_list = [(n, count) for n, count in counter.items()]
    counter_list = sorted(counter_list, key=lambda tup: tup[1], reverse=True)
    topk = counter_list[:k]
    return [n for n, count in topk]

Test

>>> from top_k_frequent_elements__sorting import topKFrequent
>>> sorted(topKFrequent([1, 1, 1, 2, 2, 3], 2))
[1, 2]
>>> topKFrequent([1], 1)
[1]

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