• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



Problem Statement:


Given a non-empty list of words, return the k most frequent elements.
Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, then the word with the lower alphabetical order comes first.

Example 1:
Input: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
Output: ["the", "is", "sunny", "day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Solution:



The concept introduced in the chapter Kth Largest Element is prerequisite for solving this problem.

To solve this problem, we use a min heap of size k to store k most frequent words. Once we have processed all words, we take a list and go on removing min from the mon heap and add the element in the list until the min heap is empty. Notice that this would give us the k most frequent words in the increasing order of the frequency. But according to the problem statement, we need the k most frequent words in decreasing order of the frequency. So we would reverse the list to get the desired answer.

Now one thing to consider: what happens when two strings have same frequency ? Then the alphabetically lower string needs to come first in the final list. Since we are reversing the list as mentioned above, in the min heap the alphabetically higher string needs to get higher priority so that after reversing the list we get the strings in correct order.

The code below implements the above discussed algorithm.



This is a Premium content. Please subscribe to access the code.
After subscribing please come back and refresh this page.



Complexity Analysis:

Time Complexity: O(Nlogk), where N = words.length = length of given words array.
Space Complexity: O(N)



The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave