Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

K Most Frequent Words

Moderate

0/80

Average time to solve is 36m

Contributed by

21 upvotes

Asked in companies

Problem statement

You have been given an array/list 'WORDS' of 'N' non-empty words, and an integer 'K'. Your task is to return the 'K' most frequent words sorted by their frequency from highest to lowest.

Note:

If two words have the same frequency then the lexicographically smallest word should come first in your answer.

Follow up:

Can you solve it in O(N * logK) time and O(N) extra space?

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains two integers, N and K, where N is the number of the words and, K denotes the number of words to return.

The next line contains N single space-separated words. Each word consists of only lowercase Latin letters.

Output Format:

For each input, print K single space-separated words, where the ith word denotes the ith most frequent word.

Note:

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= N <= 10^5
1 <= K <= number of unique words

Time Limit: 1sec

Sample Input 1:

6 2
i love codingninjas i love coding

Sample Output 1:

i love

Sample Input 2:

8 3
the sky is blue the weather is hot

Sample Output 2:

is the blue

Explanation for Sample Input 2:

“is” and “the” are words with a frequency of 2.
“sky”, “blue”, “weather”, and “hot” are the words with a frequency of 1.

The words with a frequency of 2 are the most frequent words and the lexicographically smallest word from the words with a frequency of 1 is “blue”.

Hint 1

Hint 2

Use a data structure to store the frequency of all unique strings. The task that remains is to find the k largest frequencies.

Approaches (2)

Approach 1

Approach 2

Using Sorting

We use a hashmap<key, value> to store the frequencies of all unique words in the list, where the key is the word and value is the frequency of that word in the list. While iterating over each word, we will increment the frequency corresponding to that word in the hashmap by 1.

Now, we need to find the K largest frequencies among them. For this, we store each word and its frequency as a pair in a list. We then sort the list based on the criteria that the word having a higher frequency should come first. In case if two words have the same frequency, we compare the words and the lexicographically smaller word should come first.

After sorting, the first K words of the list would be our required answer.

Time Complexity

O(N * logN), where N is the number of the words.

Hashing each word would require O(N) time. Sorting the list would require O(N * logN) time.

Space Complexity

O(N), where N is the number of the words.

In the worst case, we will be storing all the N-words in the map, and in the list, both requires O(N) space.

(100% EXP penalty)

K Most Frequent Words

Shubhanshu Pandey

Interview problems

C++ || Using Map & Priority Queue || Easy || O(NlogK)

#include <iostream>

#include <vector>

#include <string>

#include <unordered_map>

#include <queue>

#include <algorithm>

using namespace std;

class node {

public:

string word;

int count;

node(string w, int c) {

word = w;

count = c;

}

};

class comp {

public:

bool operator()(node a, node b) {

if (a.count == b.count) {

return (a.word > b.word); // Lexicographically smaller first

}

return (a.count < b.count); // Higher frequency first

}

};

vector<string> kMostFreqWords(string words[], int n, int k) {

// Step 1: Frequency counting

unordered_map<string, int> mp;

for (int i = 0; i < n; i++) {

mp[words[i]]++;

}

// Step 2: Maintain a max-heap

priority_queue<node, vector<node>, comp> pq;

for (auto& entry : mp) {

pq.push(node(entry.first, entry.second));

}

// Step 3: Extract the top k elements

vector<string> ans;

while (k-- && !pq.empty()) {

node topNode = pq.top();

pq.pop();

ans.push_back(topNode.word);

}

return ans;

}

57 views

0 replies

0 upvotes

Abhishek Sachdeva

Interview problems

easy c++ code || k most frequent words || upvote if this code helped

#include <bits/stdc++.h>

class node

{

public:

string word;

int count;

node(string word,int count)

{

this->word = word;

this->count = count;

}

};

class opr

{

public:

bool operator()(node a,node b)

{

if(a.count==b.count)

{

return a.word>b.word;

}

return a.count<b.count;

}

};

vector<string> kMostFreqWords(string words[], int n, int k){

// Write your code here.

unordered_map<string,int>mp;

for(int i=0;i<n; ++i)

{

mp[words[i]]++;

}

priority_queue<node,vector<node>,opr>q;

for(auto i:mp)

{

node temp(i.first,i.second);

q.push(temp);

}

vector<string>ans;

while(k--)

{

node temp = q.top();

q.pop();

ans.push_back(temp.word);

}

return ans;

}

62 views

0 replies

1 upvote

kartik garg

Interview problems

K Most Frequent Words

#include <bits/stdc++.h>

bool sortbysec(const pair<int ,string> &a , const pair<int, string> &b)

{

if(a.first==b.first)

{

return (a.second<b.second);

}

if(a.first>b.first)

return true;

else

return false;

}

vector<string> kMostFreqWords(string words[], int n, int k){

sort(words,words+n);

unordered_map<string,int> map1;

for(int i=0; i<n; i++)

map1[words[i]]++;

vector<pair<int,string>> lol;

for(auto x: map1)

{

lol.push_back({x.second, x.first});

}

sort(lol.begin(), lol.end(), sortbysec);

vector<string> ans;

for(int i=0; i<k ;i++)

ans.push_back(lol[i].second);

return ans;

}

143 views

0 replies

2 upvotes

Praveen Mishra

Interview problems

Python solution using Heap

Use Hashmap to store the occurrences of element

Use max heap to store the elements and then pop the top k elements

import heapq

def topKFrequent(words, k):

d={}

for i in words:

if i not in d:

d[i]=1

else:

d[i]+=1

h=[]

for key,val in d.items():

heapq.heappush(h,(-val,key))

res=[]

for i in range(k):

v,k=heapq.heappop(h)

res.append(k)

return res

python

59 views

0 replies

1 upvote

Biswajit Sahoo

Interview problems

C++ Solution using map and priority queue

class node{
    public:
    string word;
    int count;
    node(string w,int c){
        word=w;
        count=c;
    }
};
class comp{
    public:
    bool operator()(node a,node b){
        if(a.count==b.count){
            return (a.word>b.word);
        }
        return (a.count<b.count);
    }
};
vector<string> kMostFreqWords(string words[], int n, int k){
    unordered_map<string,int> mp;
    string temp = "";
    for (int i = 0; i < n; i++)
    {
        temp += words[i];
        mp[temp]++;
        temp = "";
    }
    vector<string>ans;
    priority_queue<node,vector<node>,comp> pq;
    for(auto i:mp){
        node temp(i.first,i.second);
        pq.push(temp);
    }
    while(k--){
        node answer=pq.top();
        pq.pop();
        ans.push_back(answer.word);
    }
    return ans;
}

125 views

0 replies

1 upvote

Deepali Jha

Interview problems

Easy C++ Solution


#include<bits/stdc++.h>
using namespace std;


typedef pair<int,string> pii;
class comp{
    public:
    bool operator()(pii a, pii b){
        if (a.first==b.first)
        {
            return a.second<b.second;
        }
        return a.first>b.first;
    }

};

vector<string> kMostFreqWords(string words[], int n, int k) 
{
    priority_queue<pii,vector<pii>,comp> pq;
    map<string,int>mp;
    for (int i=0;i<n;i++)
    {
        mp[words[i]]++;
    }
    for (auto it: mp)
    {
        pq.push({it.second,it.first});
        if (pq.size()>k) pq.pop();
    }
    vector<string>ans;
    int i=0;
    while(!pq.empty())
    {
        pii temp=pq.top();
        pq.pop();
        ans.push_back(temp.second);
    }
    reverse(ans.begin(),ans.end());
    return ans;
}

127 views

0 replies

0 upvotes

Jaskaran Singh

Interview problems

K Most Frequent Words

#include<bits/stdc++.h>

using namespace std;

class cmp{

public:

bool operator()(pair<int,string> &a,pair<int,string>& b){

if(a.first==b.first){

return a.second>b.second;

}

return a.first<b.first;

}

};

vector<string> kMostFreqWords(string words[], int n, int k){

map<string,int> mp;

for(int i=0;i<n;i++){

mp[words[i]]++;

}

priority_queue<pair<int,string>,vector<pair<int,string>>,

cmp> pq;

for(auto a:mp){

pq.push({a.second,a.first});

}

vector<string> ans;

while(k--){

ans.push_back(pq.top().second);

pq.pop();

}

return ans;

}

datastructures

405 views

0 replies

1 upvote

Jaickey Joy Minj

Interview problems

Java Solution | PriorityQueue

import java.util.*;
public class Solution {
   
   public static List<String> kMostFreqWords(String[] words, int k) {
       // Write your code here.
       
       Map<String,Integer> map = new HashMap<>();
       for(String w:words){
           map.put(w,map.getOrDefault(w,0)+1);
       }
       PriorityQueue<String> pq= new PriorityQueue<>((a,b)->{
           if(map.get(a)==map.get(b))
               return a.compareTo(b);
           return map.get(b)-map.get(a);
       });
       
       for(String s: map.keySet()){
           pq.offer(s);
       }
       List<String> ans = new ArrayList<>();
       for(;k>0&&!pq.isEmpty();k-=1){
           ans.add(pq.poll());
       }
       return ans;
   }
}

java

182 views

0 replies

0 upvotes

Vinay Singh Chouhan

Interview problems

K Most Frequent Words

#include<bits/stdc++.h>
vector<string> kMostFreqWords(string words[], int n, int k){
    // map "m" is for to count the frequency
    map<string,int> m;
    //answer
    vector<string> ans;
    // times is to store frequency
    vector<int> times;
    //mapping of frequency with queue of string in lexicographical of order
     map<int,queue<string>> mapping;
     for(int i=0;i<n;i++){
         m[words[i]]++;
     }
    for(auto itr : m){
        if(mapping.count(itr.second)>0){
            mapping[itr.second].push(itr.first);
            continue;
        }
        mapping[itr.second].push(itr.first);
    }
    for(auto i : mapping){
        times.push_back(i.first);
    }
    // sort in decresing order to get first highest frequency 
    sort(times.begin(),times.end(),greater<int>());
    int i =0;
    while(k!=0){
        while(!mapping[times[i]].empty() && k != 0){
            ans.push_back(mapping[times[i]].front());
            mapping[times[i]].pop();
            k--;
        }
        i++;
    }
    return ans;
    
}

225 views

0 replies

1 upvote

Arjun kaushik

Interview problems

Java

import java.util.*;
public class Solution {
	
	public static List<String> kMostFreqWords(String[] words, int k) {
		// Write your code here.
		 Map<String, Integer> count = new HashMap<>();
        Queue<Map.Entry<String, Integer>> queue = new PriorityQueue<>((a, b) ->{
                                                                          if(a.getValue() == b.getValue())
                                                                              return a.getKey().compareTo(b.getKey());
                                                                          return b.getValue() - a.getValue();
                                                                      });
        List<String> ans = new ArrayList<>();
        
        for(String w : words)
            count.put(w, count.getOrDefault(w, 0) + 1);
        
        for(Map.Entry<String, Integer> e : count.entrySet())
            queue.add(e);
        
        while(k-- > 0)
            ans.add(queue.remove().getKey());
        
        return ans;
	}

}