🙏

জয়  শ্রী  রাম

🕉

---

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.



Login to Access Content

Complexity Analysis:

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

Instructor: