Top K Frequent Words
Rippling● MediumINTERNPHONE SCREENProblem statement
Given an array words and an integer k, return the k most frequent distinct words.
Order the result by decreasing frequency. When frequencies tie, put the lexicographically smaller word first. Each word appears at most once in the result.
Treat the input as one finite dataset. After a full-sort baseline, discuss how a bounded heap reduces the selection work when k is much smaller than the number of distinct words.
Function
topKFrequentWords(words: String[], k: int) → String[]Examples
Example 1
words = ["red","blue","red","green","blue","red"]k = 2return = ["red","blue"]The frequencies are 3, 2 and 1.
Example 2
words = ["pear","apple","pear","apple","plum"]k = 2return = ["apple","pear"]Both selected words occur twice, so lexical order decides.
Example 3
words = ["go","go","go"]k = 1return = ["go"]Return one distinct word.
Constraints
1 <= words.length <= 10^5.- Each word contains between
1and30lowercase English letters. - The total number of word characters is at most
2 * 10^5. 1 <= k <= number of distinct words.