LeetCode 692: Top K Frequent Words Solution in Python – A Step-by-Step Guide

What Is LeetCode 692: Top K Frequent Words?

In LeetCode 692: Top K Frequent Words, you’re given a list of strings words and an integer k, and your task is to return the k most frequent words in the list. The result should be sorted by frequency in descending order (most frequent first), and for words with the same frequency, sorted lexicographically in ascending order (alphabetically). Return the answer as a list of strings. For example, with words = ["i", "love", "leetcode", "i", "love", "coding"] and k = 2, "i" appears 2 times, "love" 2 times, and "leetcode" and "coding" 1 time each, so return ["i", "love"] (tied frequencies sorted alphabetically). This problem tests your ability to count frequencies and sort efficiently.

Problem Statement

• Input:
• words: List of strings.
• k: Integer (number of top words to return).
• Output: A list of strings—k most frequent words.
• Rules:
• Sort by frequency (descending).
• For equal frequencies, sort lexicographically (ascending).
• Return exactly k words.
• Words are lowercase English letters.

Constraints

• 1 ≤ words.length ≤ 500.
• 1 ≤ words[i].length ≤ 10.
• words[i] consists of lowercase English letters.
• 1 ≤ k ≤ number of unique words.

Examples

• Input: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
• Output: ["i", "love"] (Both 2 times, "i" < "love")
• Input: words = ["the", "day", "is", "sunny", "the", "the", "sunny", "is", "is"], k = 4
• Output: ["the", "is", "sunny", "day"] (3, 3, 2, 1 times)
• Input: words = ["i", "i", "i"], k = 1
• Output: ["i"] (3 times)

These examples set the word list—let’s solve it!

Understanding the Problem: Finding Top K Words

To solve LeetCode 692: Top K Frequent Words in Python, we need to identify the k most frequent words in words, sorting by frequency (descending) and then alphabetically (ascending) for ties. A brute-force approach—counting frequencies and sorting all words—would be O(n log n), reasonable for n ≤ 500 but not optimal for k << n. Since we only need the top k, a heap or partial sort can optimize this. We’ll use:

• Best Solution (Heap with Frequency Counter): O(n + k log n) time, O(n) space—fast and scalable.
• Alternative Solution (Sorting with Counter): O(n log n) time, O(n) space—simple but less efficient for small k.

Let’s start with the heap solution, breaking it down for beginners.

Best Solution: Heap with Frequency Counter

Why This Is the Best Solution

The heap with frequency counter approach is the top choice for LeetCode 692 because it’s highly efficient—O(n + k log n) time with O(n) space—and uses a min-heap to maintain the top k frequent words, leveraging Python’s heapq to extract them in sorted order without sorting the entire list. It fits constraints (n ≤ 500, k ≤ unique words) perfectly and is intuitive once you see the heap logic. It’s like sifting through words and keeping only the k heaviest hitters in a neat pile!

How It Works

Think of this as a word sifter:

• Step 1: Count Frequencies:
• Use Counter to count occurrences of each word.
• Step 2: Build Min-Heap:
• Heapify entries: (-frequency, word) for max-heap effect (negative freq).
• Maintain size k, pop smallest if > k.
• Step 3: Extract Top K:
• Pop k items, reverse to get descending frequency order.
• Words with same frequency auto-sorted lexicographically.
• Step 4: Return Result:
• List of k words.

It’s like a heap sorter—count and heapify!

Step-by-Step Example

Example: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2

• Step 1: Count:
• Counter: {"i": 2, "love": 2, "leetcode": 1, "coding": 1}.
• Step 2: Build heap:
• Entries: [(-2, "i"), (-2, "love"), (-1, "leetcode"), (-1, "coding")].
• Heapify: Min-heap on (-freq, word).
• Push all, keep k=2:
• Push (-2, "i"), (-2, "love"), (-1, "leetcode"): Pop (-1, "leetcode").
• Push (-1, "coding"): Pop (-1, "coding").
• Heap: [(-2, "i"), (-2, "love")].
• Step 3: Extract:
• Pop: (-2, "love"), (-2, "i").
• Reverse: ["i", "love"] (i < love lexicographically).
• Step 4: Return ["i", "love"].
• Output: ["i", "love"].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

Copy codefrom collections import Counter
import heapq

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[int]:
        # Step 1: Count frequencies
        word_count = Counter(words)

        # Step 2: Build min-heap with (-freq, word)
        heap = []
        for word, freq in word_count.items():
            heapq.heappush(heap, (-freq, word))
            if len(heap) > k:
                heapq.heappop(heap)

        # Step 3: Extract top k
        result = []
        while heap:
            freq, word = heapq.heappop(heap)
            result.append(word)
        result.reverse()  # Reverse to get descending freq order

        # Step 4: Return result
        return result

• Lines 1-2: Import: Counter and heapq.
• Line 6: Count: Use Counter for word frequencies.
• Lines 9-13: Build heap:
• Push (-freq, word), keep size k by popping smallest.
• Lines 16-20: Extract:
• Pop heap items, append words, reverse for order.
• Line 23: Return k words.
• Time Complexity: O(n + k log n)—n to count, k log n to heapify/extract.
• Space Complexity: O(n)—Counter and heap.

This is like a word weigher—count and heap!

Alternative Solution: Sorting with Counter

Why an Alternative Approach?

The sorting with counter approach sorts all words—O(n log n) time, O(n) space. It’s simpler, counting frequencies and sorting directly, but less efficient for k << n since it sorts the entire list. It’s like lining up all words by weight and picking the top k!

How It Works

Picture this as a word ranker:

• Step 1: Count frequencies with Counter.
• Step 2: Sort items:
• Sort by (-frequency, word) for descending freq, ascending word.
• Step 3: Take top k:
• Extract k words from sorted list.
• Step 4: Return result.

It’s like a list sorter—count and rank!

Step-by-Step Example

Example: Same as above

• Step 1: Counter: {"i": 2, "love": 2, "leetcode": 1, "coding": 1}.
• Step 2: Sort:
• Items: [(-2, "i"), (-2, "love"), (-1, "coding"), (-1, "leetcode")].
• Sorted: [(-2, "i"), (-2, "love"), (-1, "coding"), (-1, "leetcode")].
• Step 3: Top k=2: ["i", "love"].
• Step 4: Return ["i", "love"].
• Output: ["i", "love"].

Code for Sorting Approach

Copy codefrom collections import Counter

class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[int]:
        # Step 1: Count frequencies
        word_count = Counter(words)

        # Step 2: Sort by (-freq, word)
        sorted_words = sorted(word_count.items(), key=lambda x: (-x[1], x[0]))

        # Step 3: Take top k
        result = [word for word, _ in sorted_words[:k]]

        # Step 4: Return result
        return result

• Line 1: Import Counter.
• Line 6: Count: Use Counter.
• Line 9: Sort: By descending freq, ascending word.
• Line 12: Extract: Top k words.
• Line 15: Return result.
• Time Complexity: O(n log n)—full sort.
• Space Complexity: O(n)—Counter and list.

It’s a word lister—count and sort!

Comparing the Two Solutions

• Heap (Best):
• Pros: O(n + k log n) time, O(n) space, efficient for k << n.
• Cons: Heap logic less obvious.
• Sorting (Alternative):
• Pros: O(n log n) time, O(n) space, straightforward.
• Cons: Slower for small k.

Heap wins for efficiency.

Additional Examples and Edge Cases

• Input: words = ["a"], k = 1
• Output: ["a"].
• Input: words = ["b", "a", "b", "a"], k = 2
• Output: ["a", "b"].

Heap handles these well.

Complexity Breakdown

• Heap: Time O(n + k log n), Space O(n).
• Sorting: Time O(n log n), Space O(n).

Heap is optimal for k < n.

Key Takeaways

• Heap: Frequency heaping—smart!
• Sorting: List ranking—clear!
• Words: Counting is fun.
• Python Tip: Heaps rock—see Python Basics.

Final Thoughts: Crack That Case

LeetCode 692: Top K Frequent Words in Python is a fun word challenge. Heap with frequency counter offers speed and elegance, while sorting with counter provides a clear baseline. Want more? Try LeetCode 347: Top K Frequent Elements or LeetCode 215: Kth Largest Element in an Array. Ready to sift? Head to Solve LeetCode 692 on LeetCode and find those top words today!