TopKFrequentWords.js

// Source : https://leetcode.com/problems/top-k-frequent-words
// Author : Dean Shi
// Date   : 2017-10-15

/***************************************************************************************
 *
 * 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: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
 * Output: ["i", "love"]
 * Explanation: "i" and "love" are the two most frequent words.
 * Note that "i" comes before "love" due to a lower alphabetical order.
 *
 * Example 2:
 * 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.
 *
 * Note:
 *
 * You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
 * Input words contain only lowercase letters.
 *
 * Follow up:
 *
 * Try to solve it in O(n log k) time and O(n) extra space.
 * Can you solve it in O(n) time with only O(k) extra space?
 *
 ***************************************************************************************/

/**
 * @param {string[]} words
 * @param {number} k
 * @return {string[]}
 */
var topKFrequent = function(words, k) {
    const dp = {}

    words.forEach((word) => dp[word] = (dp[word] || 0) + 1)

    const result = Object
        .entries(dp)
        .sort(([aWord, aCount], [bWord, bCount]) => (aCount !== bCount) ? bCount - aCount : aWord.localeCompare(bWord))

    result.length = k

    return result.map(([word]) => word)
};