Top K Frequent Words

LeetCode 692 | Difficulty: Medium

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.

Example 1:

Input: words = ["i","love","leetcode","i","love","coding"], k = 2
Output: ["i","love"]
Explanation: "i" and "love" are the two most frequent words.
Note that "i" comes before "love" due to a lower alphabetical order.

Example 2:

Input: words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
Output: ["the","is","sunny","day"]
Explanation: "the", "is", "sunny" and "day" are the four most frequent words, with the number of occurrence being 4, 3, 2 and 1 respectively.

Constraints:

- `1 <= words.length <= 500`

- `1 <= words[i].length <= 10`

- `words[i]` consists of lowercase English letters.

- `k` is in the range `[1, The number of **unique** words[i]]`

Follow-up: Could you solve it in O(n log(k)) time and O(n) extra space?

Topics: Array, Hash Table, String, Trie, Sorting, Heap (Priority Queue), Bucket Sort, Counting

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Trie (Prefix Tree)

Build a tree where each edge represents a character, and paths from root represent prefixes. Enables O(L) prefix lookups where L is the word length.

When to use

Prefix matching, autocomplete, word search, longest common prefix.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Sorting

Sort the input to bring related elements together or enable binary search. Consider: does sorting preserve the answer? What property does sorting give us?

When to use

Grouping, finding closest pairs, interval problems, enabling two-pointer or binary search.

---

Solutions

Solution 1: C# (Best: 264 ms)

Metric	Value
Runtime	264 ms
Memory	34.4 MB
Date	2020-11-07

Solution

public class Solution {
    public IList<string> TopKFrequent(string[] words, int k) {
            Dictionary<string, int> occurences = new Dictionary<string, int>();
    int m = words.Length;

    for (int i = 0; i < m; i++)
    {
        if (!occurences.ContainsKey(words[i]))
        {
            occurences.Add(words[i], 1);
        }
        else
        {
            occurences[words[i]]++;
        }
    }
    List<string> result = new List<string>();
    int counter = k;
    foreach (var occurence in occurences.OrderByDescending(x => x.Value).ThenBy(x=>x.Key))
    {
        if (counter > 0) result.Add(occurence.Key);
        counter--;
    }
    return result;
    }
}

---

Complexity Analysis

Approach	Time	Space
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$
Trie	$O(L × n)$	$O(L × n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.