This content originally appeared on Level Up Coding - Medium and was authored by Ruslan Rakhmedov
Task description:
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]
Constraints:
- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^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.
Reasoning:
So task asks us to calculate top K frequent elements, the very first step we should do is to calculate how many time each elements appears in a given array. The following code solves this sub problem:
Having this information collected we now can use it in order to sort elements based on counts in descending order and return first K elements. First we need to create a Priority Queue and provide it with the reversed order comparator which uses information from Map we just created
Next we push all keys from the valueToCount Map to our Priority Queue, it forces them to be sorted in descending order based on count. After that we make K iterations, on every iteration we remove top element from the Priority Queue and put it to our answer.
So our solution should look look this:
It works and gives us the following result:
Although it works, result doesn’t look impressive we can and should do better. Moreover if you take closer look to the problem statement it has the follow up question
Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
Now it’s time to optimize and speed up our algorithm.
Solution:
In order to achieve the better performance let’s start from introducing just one additional variable which will be holding the maximum number of occurrences throughout all elements in a provided array.
We cannot longer use our Priority Queue because it gives us n log n time complexity when we add all keys from the valueToCount Map. Instead we want to do it faster. Let’s introduce List of Lists of integers and call it buckets. Don’t be scarry, I’ll explain this logic later.
As you can see we did some small optimization — we limited the size of our buckets to be the maximum value we have seen during counting phase.
Next step could be difficult to grasp from the first attempt, please give yourself some time and read it again.
Let’s recap our valueToCount Map holds keys which represent elements from a given array and values represent a number of occurrences per each key. Keeping this information in mind we are going to iterate though values of the valueToCount Map and put in a specific positions keys from the same map.
Let’s look at the example and try to visualize the steps we made. Let’s look at this array
[4,1,-1,2,-1,2,3,5,5,5]
Numbers 4, 1, 3 have 1 occurrence per each number. Numbers -1, 2 have 2 occurrences per each number. Number 5 has 3 occurrences. Our map should hold the following information
{-1=2, 1=1, 2=2, 3=1, 4=1, 5=3}Now let’s visualize buckets
Top row reflects the number of occurrences. There is only one step left — we need to collect and return result array
The full solution should look like this
The result looks much better now
Top K Frequent Elements Blind 75 LeetCode Question was originally published in Level Up Coding on Medium, where people are continuing the conversation by highlighting and responding to this story.
This content originally appeared on Level Up Coding - Medium and was authored by Ruslan Rakhmedov
Ruslan Rakhmedov | Sciencx (2022-10-20T15:43:51+00:00) Top K Frequent Elements Blind 75 LeetCode Question. Retrieved from https://www.scien.cx/2022/10/20/top-k-frequent-elements-blind-75-leetcode-question/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.