Coding Interview PatternsTop K Frequent Words
MediumTop K Elements

Top K Frequent Words

Explanation & Solution

Practice Problem

Description

Given an array of strings words and an integer k, return the k most frequent strings.

Return the answer sorted by frequency from highest to lowest. If two words have the same frequency, sort them in alphabetical order.

Examples

Input:words = ["i","love","leetcode","i","love","coding"], k = 2
0
i
1
love
2
leetcode
3
i
4
love
5
coding
Output:["i","love"]
0
i
1
love

Explanation: "i" and "love" are the two most frequent words. "i" appears 2 times and "love" appears 2 times. "i" comes before "love" alphabetically.

Input:words = ["the","day","is","sunny","the","the","the","sunny","is","is"], k = 4
0
the
1
day
2
is
3
sunny
4
the
5
the
6
the
7
sunny
8
is
9
is
Output:["the","is","sunny","day"]
0
the
1
is
2
sunny
3
day

Explanation: "the" appears 4 times, "is" 3 times, "sunny" 2 times, and "day" 1 time. They are sorted by frequency, with ties broken alphabetically.

Input:words = ["a","b","c"], k = 3
0
a
1
b
2
c
Output:["a","b","c"]
0
a
1
b
2
c

Explanation: All words appear once, so they are sorted alphabetically.

Constraints

  • 1 <= words.length <= 500
  • 1 <= words[i].length <= 10
  • words[i] consists of lowercase English letters.
  • k is in the range [1, number of unique words].
  • The answer is guaranteed to be unique.

Approach

Top K Elements pattern

1. Build a Frequency Map

  • Iterate through the words array.
  • Use a hash map to count the frequency of each word.
  • For example, ["i","love","i"] produces { "i": 2, "love": 1 }.

2. Extract Unique Words

  • Get all unique words from the hash map's keys.
  • These are the candidates we need to rank.

3. Sort by Frequency and Alphabetical Order

  • Sort the unique words using a custom comparator:
  • Primary sort: by frequency in descending order (higher frequency first).
  • Secondary sort: by alphabetical order (for words with equal frequency).
  • This ensures ties are broken correctly.

4. Return the Top K Words

  • Slice the first k elements from the sorted array.
  • These are the k most frequent words in the required order.

Key Insight

The core idea is to combine a hash map for counting with a custom sort that handles both frequency and lexicographic ordering. Sorting all unique words takes O(n log n) time where n is the number of unique words, and building the frequency map takes O(m) where m is the total number of words. Overall time complexity: O(m + n log n) and space complexity: O(n) for the hash map and sorted array.

Solution Code

Previous
K Closest Points to Origin
Next
Find K Pairs with Smallest Sums