How do you solve Top K Frequent Words on LeetCode?

Top K Frequent Words (LeetCode #692) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log k) time complexity and O(n) space complexity. Key insight: Using a heap allows us to efficiently manage the top k elements without sorting the entire list.

What is the brute force solution for Top K Frequent Words?

The brute force approach for Top K Frequent Words is Brute Force, with O(n²) time complexity and O(n) space complexity. The brute force approach involves counting the frequency of each word and then sorting the entire list of words based on their frequency and lexicographical order. This method is straightforward but inefficient for larger datasets. The optimal Optimal Solution approach improves this to O(n log k).

What are the interview tips for Top K Frequent Words?

Always clarify the problem requirements and constraints before jumping into coding. Discuss your thought process and potential approaches with the interviewer. Consider edge cases, such as when k equals the number of unique words.

What are common mistakes when solving Top K Frequent Words?

Not considering how to handle ties in frequency correctly. Forgetting to reverse the result after extracting from a min-heap.

#692

Top K Frequent Words

Medium

ArrayHash TableStringTrieSortingHeap (Priority Queue)Bucket SortCountingHash MapHeap (Priority Queue)

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log k)
Space	O(n)	O(n)

💡

Intuition

Time O(n log k)Space O(n)

The optimal approach uses a heap (priority queue) to efficiently keep track of the top k frequent words. This reduces the sorting overhead and allows us to maintain only the necessary elements.

⚙️

Algorithm

3 steps

1Step 1: Count the frequency of each word using a dictionary.
2Step 2: Use a min-heap to keep track of the top k elements based on frequency and lexicographical order.
3Step 3: Extract the elements from the heap and return them in the required order.

solution.py6 lines

1from collections import Counter
2import heapq
3
4def topKFrequent(words, k):
5    count = Counter(words)
6    return heapq.nsmallest(k, count.keys(), key=lambda x: (-count[x], x))

ℹ

Complexity note: The time complexity is O(n log k) because we maintain a min-heap of size k, which allows us to efficiently keep track of the top k elements. Counting frequencies takes O(n), and each insertion into the heap takes O(log k).

1Using a heap allows us to efficiently manage the top k elements without sorting the entire list.
2Sorting by frequency and then lexicographically can be achieved with custom sorting functions.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.