Sorting Problem

K Most Frequent Words

Problem

Given a number and a list of words, return the given number of most frequent words.

Example

{
"k": 4,
"words": ["car", "bus", "taxi", "car", "driver", "candy", "race", "car", "driver", "fare", "taxi"]
}

Output:

["car", "driver", "taxi", "bus"]

Solution

function mostFrequentWord(words, k) {

  const freq = new Map();
  let result = [];
  let n = words.length;

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

    let x = 0;
    if (freq.has(words[i]) == true) {
      x = freq.get(words[i]);
    }
    freq.set(words[i], x + 1);
  }

  let freqWordsSorted = new Map([...freq.entries()].sort((a, b) => b[1] - a[1]));

  for (let [key, value] of freqWordsSorted) {
    result.push(key);
    k--;
    if(!k) {
      break;
    }
  }

  console.log(result);
}

// given set of keys
let arr = ["car", "bus", "taxi", "car", "driver", "candy", "race", "car", "driver", "fare", "taxi"];
let n = 4;

mostFrequentWord(arr, n);

Time and Space Complexity

Time Complexity : O(n * log(n))
Space Complexity:  O(n)

Leave a comment