Top K Frequent Elements

mediumFREEArrays & HashingBlind 75

Given an integer array nums and integer k, return the k most frequent elements as a list, in any order.

If several elements tie in frequency for the last of the k places, choose the one whose first occurrence in nums comes earliest.

The tests sort your list and print it space-separated (e.g. 1 2).

Example

Input

1,1,1,2,2,3
2

Output

1 2

Reasoning

The inputs are nums, here the six integers 1,1,1,2,2,3, and $k = 2$ , the number of elements to report.
The frequency of a value $v$ is how many positions of nums hold $v$ : $f(1) = 3$ , $f(2) = 2$ , $f(3) = 1$ . The three counts add up to $6$ , the length of the array.
Ranking the distinct values by frequency from highest to lowest gives $1$ ( $3$ times), then $2$ ( $2$ times), then $3$ ( $1$ time). The top $k = 2$ are $1$ and $2$ ; the value $3$ is left out because two values already rank above it.
The answer is the set $\{1, 2\}$ , printed in ascending order as 1 2. Notice that only the distinct values matter in the output: no value is repeated, and the counts themselves are never shown.
Ties only matter at the cut-off: in $[4, 4, 4, 1, 1, 2, 2, 3]$ with $k = 2$ , both $1$ and $2$ appear twice, and $1$ wins because it shows up first, giving 1 4.

Constraints

1 <= len(nums) <= 10^5
-10^4 <= nums[i] <= 10^4
k is always valid (1 <= k <= number of unique elements)

More from Blind 75

Alien Dictionaryhard Clone Graphmedium Combination Summedium Word Search IIhard Merge K Sorted Listshard

Concept primer

Background Knowledge

The "Top K Frequent Elements" problem involves finding the most frequent elements in an array. To solve this, it's essential to understand hash maps, which are data structures that store key-value pairs. In this context, we can use a hash map to count the frequency of each element in the array. The key concept here is that hash maps allow for efficient lookups, insertions, and deletions, with an average time complexity of $O(1)$ .

Another crucial concept is counting, which is a fundamental technique in algorithm design. Counting involves keeping track of the number of occurrences of each element in the array. This can be done using a hash map, where the keys are the elements and the values are their corresponding counts. Understanding how to iterate through the array, update the counts, and retrieve the top k elements is vital to solving this problem.

The problem also requires an understanding of sorting and priority queues, as we need to return the top k frequent elements in sorted order. However, since the problem statement allows for any order, we can focus on finding the top k elements first and then sorting them if necessary. The key idea is to use a data structure that allows us to efficiently extract the top k elements, such as a heap or a sorted array.

Algorithm/Approach

The general approach to solving this problem involves using a hash map to count the frequency of each element, followed by a priority queue or sorting step to extract the top k elements. The algorithm pattern is as follows:

Count the frequency of each element using a hash map
Use a priority queue or sorting to extract the top k elements
Return the top k elements in the required order

Step-by-Step Strategy

To implement the solution, follow these steps:

Create a hash map to store the frequency of each element
Iterate through the array, updating the frequency count for each element in the hash map
Use a priority queue or sorting to extract the top k elements from the hash map
Return the top k elements in the required order

Common Pitfalls

When implementing the solution, watch out for the following:

Forgetting to handle edge cases, such as an empty array or k = 0
Using an inefficient data structure, such as a linear search, to extract the top k elements
Not considering the time and space complexity of the solution

Time & Space Complexity

The expected time complexity is $O(n \log k)$ , where n is the length of the array and k is the number of top elements to return. The space complexity is $O(n)$ , as we need to store the frequency count for each element in the hash map. Note that the actual time and space complexity may vary depending on the specific implementation and data structure used.

solution.py

Python 3.13

Test results