We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Top K Frequent Words

Difficulty: Medium

Problem Description

Given an array of strings words and an integer k, return the k most frequent strings. Return the answer sorted by the frequency from highest to lowest. Sort the words with the same frequency by their lexicographical order.

Key Insights

  • Use a frequency map to count occurrences of each word.
  • Utilize a priority queue (min-heap) to efficiently retrieve the top k frequent words.
  • Sort words with the same frequency lexicographically to satisfy the problem's requirements.

Space and Time Complexity

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

Solution

To solve this problem, we can follow these steps:

  1. Create a frequency map using a hash table to count the occurrences of each word.
  2. Use a min-heap (priority queue) to keep track of the top k words based on their frequency.
  3. For words with the same frequency, sort them lexicographically.
  4. Extract the words from the heap and return them in the required order.

Code Solutions

from collections import Counter
import heapq

def topKFrequent(words, k):
    # Step 1: Count the frequency of each word
    count = Counter(words)
    
    # Step 2: Use a min-heap to find the top k frequent words
    # We use a tuple (-frequency, word) to sort first by frequency then lexicographically
    min_heap = [(-freq, word) for word, freq in count.items()]
    heapq.heapify(min_heap)
    
    # Step 3: Extract the top k elements
    top_k = heapq.nsmallest(k, min_heap)
    
    # Step 4: Return only the words sorted by the required order
    return [word for freq, word in top_k]
← Back to All Questions