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

Explanation

We can count the frequency of each element in the array using a dictionary. Then we sort the dictionary by the counts in descending order and return the first \(k\) elements.

Code

def topKFrequent(nums: list[int], k: int) -> list[int]:
    """Returns the :math:`k` most frequent elements in ``nums``."""
    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]

Complexity

\(n\) is the number of elements in nums

Measure	Complexity	Notes
Time	\(O(n \log n)\)	sorting the array
Auxiliary Space	\(O(n)\)	the dictionary can contain up to the whole array

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

Returns the \(k\) most frequent elements in nums.

Min Heap

Code

import heapq
from collections import Counter


def topKFrequent(nums: list[int], k: int) -> list[int]:
    """Return the ``k`` most frequent elements using bucket sort."""
    counter = Counter(nums)

    heap = []
    for num, count in counter.items():
        heapq.heappush(heap, (count, num))
        if len(heap) > k:
            heapq.heappop(heap)

    return [num for count, num in heap]

Test

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

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

Return the k most frequent elements using bucket sort.