347. Top K Frequent Elements
Top K Frequent Elements (LeetCode 347) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.
- Blind 75 · #5 of 75 · Arrays & Hashing
- NeetCode 150 · #5 of 150 · Arrays & Hashing
- NeetCode 250 · #13 of 250 · Arrays & Hashing
How to solve Top K Frequent Elements
Top K Frequent Elements is a Top K Elements problem, part of Heap (Priority Queue) Patterns. Find top K elements using heap. Solve kth largest, top K frequent, and k closest points problems.
Work towards the solution in these steps:
- Start by thinking about how to efficiently count the frequency of each element in the array.
- Once you have the frequencies, consider a data structure that can help you quickly access the elements with the highest frequency.
- A min-heap (priority queue) can be used to keep track of the top k elements by frequency as you iterate through the unique elements.
The reference solution runs in O(n) time and O(n) space.
The Top K Frequent Elements solution and editorial walks through the full approach with reference code.
Problem statement
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
- k is in the range [1, the number of unique elements in the array].
- It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
Topics and companies
Topics: Array, Hash Table, Divide and Conquer, Sorting, Heap (Priority Queue), Bucket Sort, Counting, Quickselect.
Reported in interviews at Amazon, Apple, Bloomberg, ByteDance, Capital One, eBay, Facebook, Google, Microsoft, Oracle, Uber, Walmart Labs and others.
How to practise Top K Frequent Elements on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.
Open Top K Frequent Elements in the code editor, or read the Top K Frequent Elements editorial for a worked solution with its approach and complexity analysis.
Where Top K Frequent Elements sits in the DSA pattern sheet
- Heap (Priority Queue) Patterns pattern guide
- Top K Elements (Selection/Frequency) subpattern
- The full DSA patterns sheet
Problems related to Top K Frequent Elements
Other problems that use the same Top K Elements (Selection/Frequency) and Heap (Priority Queue) Patterns techniques:
- K Closest Points to Origin — Medium, same subpattern
- Kth Largest Element in an Array — Medium, same subpattern
- Kth Largest Element in a Stream — Easy, same subpattern
- Last Stone Weight — Easy, same subpattern
- Relative Ranks — Easy, same subpattern
- Sort Characters By Frequency — Medium, same subpattern
Top K Frequent Elements FAQ
What is the LeetCode number of Top K Frequent Elements?
Top K Frequent Elements is LeetCode problem 347, rated Medium.
What pattern is used to solve Top K Frequent Elements?
Top K Frequent Elements is a Top K Elements problem. It belongs to the Heap (Priority Queue) Patterns pattern, in the Top K Elements (Selection/Frequency) subpattern.
What is the time complexity of Top K Frequent Elements?
The reference solution runs in O(n) time and O(n) space.
Which companies ask Top K Frequent Elements?
Top K Frequent Elements has been reported in interviews at Amazon, Apple, Bloomberg, ByteDance, Capital One, eBay, Facebook, Google, Microsoft, Oracle, Uber, Walmart Labs and others.