MediumNo. 0692

Top K Frequent Words — LeetCode 692 Python Solution

Pattern
Trie
Topics
Trie, Array, Hash Table, String, Bucket Sort, Counting, Sorting, Heap (Priority Queue)
Reading time
2 min

The problem

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.

Example

Input
words = ["i","love","leetcode","i","love","coding"], k = 2
Output
["i","love"]
Explanation
"i" and "love" are the two most frequent words.

Python solution

PythonSolution
class Solution:
    def topKFrequent(self, words: List[str], k: int) -> List[str]:
        cnt = Counter(words)
        return sorted(cnt, key=lambda x: (-cnt[x], x))[:k]

Complexity

Time
O(n × log n)
Space · auxiliary
O(n)

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 692. Top K Frequent Words is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0347Top K Frequent ElementsMedium
0451Sort Characters By FrequencyMedium
0621Task SchedulerMedium
0720Longest Word in DictionaryMedium
0767Reorganize StringMedium
0792Number of Matching SubsequencesMedium

Frequently asked questions

How hard is LeetCode 692. Top K Frequent Words?

LeetCode 692. Top K Frequent Words is rated Medium on LeetCode.

What is the time complexity of LeetCode 692. Top K Frequent Words?

The Python solution on this page runs in O(n × log n).

What is the space complexity of LeetCode 692. Top K Frequent Words?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 692. Top K Frequent Words cover?

LeetCode 692. Top K Frequent Words is tagged Trie, Array, Hash Table, String, Bucket Sort, Counting, Sorting and Heap (Priority Queue) on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.