Top K Frequent Words

📋

Problem

Imagine you run a social media platform and want to display the top trending hashtags or words used by users in real-time.

Given a list of words, return the k most frequent words. The answer should be sorted by frequency from highest to lowest. If two words have the same frequency, the word with the lower alphabetical order comes first.

1 ≤ words.length ≤ 10^51 ≤ words[i].length ≤ 10k is in the range [1, number of unique words]Words contain only lowercase English letters

Edge cases: All words are unique → output is the first k words sorted lexicographicallyAll words are the same → output is that word repeated oncek equals number of unique words → output all words sorted by frequency and lex order

</>

IDE

def topKFrequent(words: list[str], k: int) -> list[str]:public List<String> topKFrequent(String[] words, int k)vector<string> topKFrequent(vector<string>& words, int k)function topKFrequent(words, k)

def topKFrequent(words, k):
    # Write your solution here
    pass

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        // Write your solution here
        return new ArrayList<>();
    }
}

#include <vector>
#include <string>
using namespace std;

vector<string> topKFrequent(vector<string>& words, int k) {
    // Write your solution here
    return {};
}

function topKFrequent(words, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: ["love", "i"]Sorting words lexicographically ascending but ignoring frequency order.✅ Sort words by (-freq[word], word) to prioritize frequency descending first.

Wrong: ["b", "a"]Greedy approach picking first k words without sorting or tie-break logic.✅ Implement sorting by frequency descending and lex ascending to break ties.

Wrong: ["a", "b", "c", "d"]Fails to handle k less than number of unique words; returns all words unsorted.✅ Sort all unique words by frequency and lex order, then return first k elements.

Wrong: Runtime error or crashNo handling for empty input list or k=0.✅ Add guard clause to return empty list if input words list is empty.

Wrong: Timeout on large inputFull sorting of all unique words instead of using min heap of size k.✅ Use a min heap of size k to maintain top k frequent words for O(n log k) time.

✓

Test Cases

Try testing your code with empty and single-element inputs to catch base case bugs.

Focus on tie-break conditions and frequency counting correctness for tricky inputs.

Optimize your solution to avoid full sorting on large inputs; use a heap or bucket sort.

t1_01basic

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

Expected["i","love"]

⏱ Performance - must finish in 2000ms

"i" and "love" both appear twice, but "i" comes before "love" lexicographically.

💡 Count the frequency of each word first.

💡 Sort words by frequency descending, then lexicographically ascending.

💡 Return the first k words after sorting by (-freq, word).

Why it failed: Failed to order by frequency and lexicographic tie-break. Fix sorting key to (-freq[word], word).

✓ Correctly returns top k frequent words with lexicographic tie-break.

t1_02basic

Input{"words":["the","day","is","sunny","the","the","the","sunny","is","is"],"k":4}

Expected["the","is","sunny","day"]

⏱ Performance - must finish in 2000ms

"the" appears 4 times, "is" 3 times, "sunny" 2 times, "day" 1 time; sorted by frequency then lex order.

💡 Aggregate frequencies for all words.

💡 Sort by frequency descending and lex ascending for ties.

💡 Return the top k words after sorting.

Why it failed: Incorrect frequency counting or sorting order. Ensure sorting by (-freq[word], word).

✓ Correctly identifies top k frequent words with proper ordering.

t2_01edge

Input{"words":[],"k":1}

Expected[]

⏱ Performance - must finish in 2000ms

Empty input list returns empty output regardless of k.

💡 Check if input list is empty before processing.

💡 Return empty list immediately if no words.

💡 Avoid errors from empty frequency map or sorting empty list.

Why it failed: Code crashes or returns non-empty output on empty input. Add guard for empty input.

✓ Handles empty input gracefully by returning empty list.

t2_02edge

Input{"words":["hello"],"k":1}

Expected["hello"]

⏱ Performance - must finish in 2000ms

Single word input returns that word as top frequency.

💡 Frequency map will have one entry with count 1.

💡 Sorting a single element list returns the same list.

💡 Return the single word as top k=1.

Why it failed: Fails on single element input, possibly empty output or wrong sorting. Fix frequency counting and sorting for single element.

✓ Correctly returns single word for single element input.

t2_03edge

Input{"words":["a","b","c","d"],"k":4}

Expected["a","b","c","d"]

⏱ Performance - must finish in 2000ms

All words unique with frequency 1; output is all words sorted lexicographically.

💡 All frequencies equal, so lexicographic order decides.

💡 Sort words lexicographically ascending.

💡 Return all words since k equals number of unique words.

Why it failed: Fails to sort lexicographically when frequencies tie. Fix sorting key to handle tie-break by word.

✓ Correctly sorts all unique words lexicographically when frequencies tie.

t3_01corner

Input{"words":["a","a","b","b","c"],"k":2}

Expected["a","b"]

⏱ Performance - must finish in 2000ms

"a" and "b" both appear twice; "a" comes before "b" lexicographically.

💡 Check tie-break when frequencies are equal.

💡 Use lexicographic order ascending to break ties.

💡 Sort by (-freq[word], word) to get correct order.

Why it failed: Greedy approach picking first encountered words fails tie-break. Fix sorting to use lex order for ties.

✓ Correctly handles tie-breaks by lexicographic order.

t3_02corner

Input{"words":["a","b","a","b","c","c","c"],"k":3}

Expected["c","a","b"]

⏱ Performance - must finish in 2000ms

"c" appears 3 times, "a" and "b" twice each; "a" before "b" lexicographically.

💡 Check frequency counts carefully.

💡 Sort by frequency descending, then lex ascending.

💡 Return top k words after sorting.

Why it failed: Confuses 0/1 vs unbounded frequency counting, missing correct counts. Fix frequency counting logic to count all occurrences.

✓ Correctly counts frequencies and sorts accordingly.

t3_03corner

Input{"words":["apple","app","apple","app","apricot","apricot","apricot"],"k":2}

Expected["apricot","app"]

⏱ Performance - must finish in 2000ms

"apricot" appears 3 times, "app" and "apple" twice each; "app" before "apple" lexicographically.

💡 Check lexicographic order when frequencies tie.

💡 Sort by (-freq[word], word) to break ties.

💡 Return top k words after sorting.

Why it failed: Incorrect lexicographic tie-break when frequencies tie. Fix sorting key to use word ascending for ties.

✓ Correctly applies lexicographic tie-break for words with same frequency.

t4_01performance

Input{"words":["word0","word1","word2","word3","word4","word5","word6","word7","word8","word9","word10","word11","word12","word13","word14","word15","word16","word17","word18","word19","word20","word21","word22","word23","word24","word25","word26","word27","word28","word29","word30","word31","word32","word33","word34","word35","word36","word37","word38","word39","word40","word41","word42","word43","word44","word45","word46","word47","word48","word49","word50","word51","word52","word53","word54","word55","word56","word57","word58","word59","word60","word61","word62","word63","word64","word65","word66","word67","word68","word69","word70","word71","word72","word73","word74","word75","word76","word77","word78","word79","word80","word81","word82","word83","word84","word85","word86","word87","word88","word89","word90","word91","word92","word93","word94","word95","word96","word97","word98","word99"],"k":50}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 unique words, must complete in O(n log k) or better within 2 seconds.

💡 Use a min heap of size k to maintain top k frequent words.

💡 Avoid full sorting of all unique words to reduce complexity.

💡 Heap operations are O(log k), total O(n log k) time.

Why it failed: TLE due to O(n log n) full sorting instead of O(n log k) heap approach. Fix by using min heap of size k.

✓ Efficient heap-based approach confirmed with O(n log k) complexity.

Practice

1. You are given a 2D matrix and need to find the kth largest value among all XOR coordinate values, where each coordinate value is the XOR of all elements from the top-left corner to that coordinate. Which approach guarantees an optimal solution in terms of time complexity?

easy

A. Use nested loops to compute XOR for each coordinate independently, then sort all values.

B. Apply dynamic programming with memoization to store XOR values and then sort them.

C. Use a greedy approach to pick the largest elements first and XOR them until k values are found.

D. Compute a prefix XOR matrix and maintain a min-heap of size k to track the kth largest value.

Solution

1. Step 1: Understand the problem constraints

   Computing XOR values for each coordinate independently with nested loops leads to O(m^2 * n^2) time, which is inefficient.

2. Step 2: Recognize prefix XOR and min-heap usage

   Using a prefix XOR matrix allows O(m * n) computation of all XOR coordinate values. Maintaining a min-heap of size k ensures we track the kth largest value efficiently, leading to O(m * n * log k) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Prefix XOR + min-heap is optimal for kth largest XOR coordinate value [OK]

Hint: Prefix XOR + min-heap is optimal for kth largest XOR values [OK]

Common Mistakes:

• Thinking nested loops with sorting is efficient enough
• Assuming greedy selection works for XOR
• Confusing DP with prefix XOR usage

2. Consider the following Python code implementing the optimal bucket sort approach for top k frequent elements. What is the value of buckets[2] after the frequency dictionary is built for input nums = [1,1,2,2,3] and k = 2?

easy

A. [2]

B. [1, 2]

C. [1]

D. [3]

Solution

1. Step 1: Build frequency dictionary for nums = [1,1,2,2,3]

   Frequencies: 1 -> 2, 2 -> 2, 3 -> 1

2. Step 2: Assign elements to buckets by frequency

   buckets[1] = [3], buckets[2] = [1, 2]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Both 1 and 2 appear twice, so they share bucket 2 [OK]

Hint: Elements grouped by frequency in buckets [OK]

Common Mistakes:

• Confusing frequency counts
• Misindexing buckets by frequency

3. The following code attempts to implement the optimal frequency stack using a max-heap with timestamp. Identify the bug that causes incorrect behavior when popping elements.

import heapq

class FreqStack:
    def __init__(self):
        self.freq = {}
        self.heap = []
        self.time = 0

    def push(self, val: int) -> None:
        self.freq[val] = self.freq.get(val, 0) + 1
        self.time += 1
        heapq.heappush(self.heap, (-self.freq[val], -self.time, val))

    def pop(self) -> int:
        freq, time, val = heapq.heappop(self.heap)
        # BUG: Missing frequency decrement
        if self.freq[val] == 0:
            del self.freq[val]
        return val

medium

A. Line with heapq.heappop(self.heap) does not pop the correct element.

B. Frequency map deletion condition is incorrect; should delete when freq[val] == 1.

C. Timestamp is not updated on push, so recency is lost.

D. Frequency map is not decremented after popping, causing stale frequencies.

Solution

1. Step 1: Identify frequency update after pop

   The code does not decrement frequency after popping an element, so freq[val] remains stale.

2. Step 2: Consequences of missing decrement

   Without decrement, future pushes and pops will have incorrect frequency counts, breaking the max frequency logic.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Frequency must be decremented after pop to maintain correctness [OK]

Hint: Always decrement frequency after popping an element [OK]

Common Mistakes:

• Forgetting to update frequency map after pop
• Mismanaging timestamp updates
• Incorrect deletion condition for frequency map

4. Suppose the problem changes: you want to find the kth largest XOR coordinate value, but now the matrix can contain negative integers. Which modification to the optimal prefix XOR + min-heap approach is necessary to handle this correctly?

hard

A. Use a 64-bit integer type to store prefix XOR values to avoid sign issues.

B. Convert all negative integers to positive before computing prefix XOR.

C. No modification needed; XOR works the same with negative integers.

D. Use bitwise AND instead of XOR to handle negative values correctly.

Solution

1. Step 1: Understand XOR with negative integers

   In Python, integers are unbounded but negative numbers use two's complement representation internally, which can cause sign extension issues if stored in fixed-width types.

2. Step 2: Use 64-bit integer type for prefix XOR

   To correctly handle negative values and avoid sign extension or overflow, use a 64-bit integer type (e.g., numpy.int64) for prefix XOR computations and heap storage.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Handling negative integers requires careful data type choice, not changing XOR logic [OK]

Hint: XOR logic unchanged; data type must handle sign correctly [OK]

Common Mistakes:

• Assuming XOR fails with negatives
• Replacing XOR with AND
• Ignoring integer overflow/sign issues

5. Suppose the problem changes: the matrix is no longer sorted by columns, only rows are sorted, and you still need to find the kth smallest element. Which approach is the most suitable to solve this variant efficiently?

hard

A. Use binary search on the value range with the same counting method as before.

B. Use a greedy approach picking the smallest element from each row repeatedly.

C. Flatten the matrix and sort all elements to find the kth smallest.

D. Use a min heap to merge the k sorted rows, extracting the kth smallest element.

Solution

1. Step 1: Understand changed constraints

   Only rows are sorted, columns are not sorted, so binary search counting on columns is invalid.

2. Step 2: Identify suitable approach

   Min heap merging k sorted lists (rows) efficiently finds kth smallest in O(k log n) time.

3. Step 3: Reject other approaches

   Binary search counting fails without column sorting; flattening is O(n² log n²); greedy is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Min heap merge exploits row sorting without column sorting [OK]

Hint: Without column sorting, binary search counting fails [OK]

Common Mistakes:

• Trying binary search counting without column sorting
• Assuming greedy works