Medium

Top K Frequent Words

LAB

Return the k most frequent words, breaking ties lexicographically ascending.

EXAMPLES

Example 1

Input
{
  "words": [
    "i",
    "love",
    "leetcode",
    "i",
    "love",
    "coding"
  ],
  "k": 2
}

Output
[
  "i",
  "love"
]

FUNCTION SHAPE

words: stringArrayk: int→stringArray

SOLUTION NOTE

Note: Doing this in O(n log k) with a heap of size k is tricky because of the lexicographical tiebreaker requirement.

Reveal reference solution +

pythonREFERENCE

# Solution 1: Sort
def topKFrequent(self, words: List[str], k: int) -> List[str]:
    freq = Counter(words)
    words = sorted((-freq[word], word) for word in set(words))
    return [word for _, word in words[:k]]

# Solution 2: Heap (push all, pop k times)
def topKFrequent(self, words: List[str], k: int) -> List[str]:
    freq = Counter(words)
    heap = []
    for word in set(words):
        heappush(heap, (-freq[word], word))
    res = []
    for _ in range(k):
        res.append(heappop(heap)[1])
    return res

TimeO(n log n)

SpaceO(n)

Open on LeetCode ↗