Top K Frequent Words - Solution & Explanation

Problem Overview: Given an array of words, return the k most frequent words. Words with higher frequency come first, and when two words have the same frequency, the lexicographically smaller word appears earlier. The challenge is efficiently counting frequencies and ordering results by both frequency and alphabetical order.

Approach 1: Hash Map and Sorting (Time: O(n log n), Space: O(n))

The straightforward solution uses a frequency map. First iterate through the input array and count occurrences using a hash table. This step runs in O(n). Next convert the map entries into a list and sort them using a custom comparator: higher frequency first, and if frequencies match, compare words lexicographically.

The sorting step dominates the runtime at O(m log m), where m is the number of unique words (worst case m = n). The comparator ensures correct ordering without additional passes. After sorting, simply take the first k words. This approach is easy to implement and works well when the number of unique words is moderate.

Because the heavy lifting is done by sorting, this method is reliable and readable. Many interview candidates start with this solution because it clearly separates counting and ordering logic.

Approach 2: Min-Heap (Time: O(n log k), Space: O(n))

When k is much smaller than the number of unique words, a heap reduces unnecessary sorting. First build the same frequency map using a hash table in O(n). Then iterate through each unique word and push it into a size-limited min-heap based on frequency.

The heap stores at most k elements. The comparator prioritizes smaller frequency, and when frequencies tie, the lexicographically larger word is considered smaller in the heap so it gets removed first. Whenever the heap size exceeds k, pop the smallest element. This keeps only the top k candidates.

Each heap insertion or removal costs O(log k), so processing all unique words takes O(m log k). After processing, extract elements from the heap and reverse them to produce the final order. This approach relies on a priority queue to avoid sorting the entire dataset.

Recommended for interviews: Start with the hash map + sorting approach because it demonstrates clear thinking and correct ordering logic. Then mention the min-heap optimization. Interviewers often expect the heap solution when k is small relative to the dataset, since it reduces the ordering cost from O(n log n) to O(n log k) while still using a hash map for counting.