mafeshsho8lmafeshsho8l
Get Started
All coding questions

Top K Frequent Elements

medium
Blind 75NeetCode 150arrayshashingheap

Problem

Given a list of integers and a number k, return the k values that occur most frequently. The answer may be returned in any order, and the k most frequent values are guaranteed to be unambiguous.

Examples

Input: nums = [1, 1, 1, 2, 2, 3], k = 2
Output: [1, 2]
1 appears three times and 2 appears twice.
Input: nums = [1], k = 1
Output: [1]
Only one distinct value exists.

Constraints

  • • 1 <= nums.length <= 10^5
  • • 1 <= k <= number of distinct values
Hints(tap to reveal)
  • 1. First count frequencies.
  • 2. Bucket sort by frequency avoids a full sort and runs in linear time.
Optimal approach(spoiler)
  1. Count the frequency of each value with a hash map.
  2. Create buckets indexed by frequency, where each bucket holds the values with that count.
  3. Walk the buckets from highest frequency down.
  4. Collect values until you have k of them.
  5. O(n) time and O(n) space.

Ready to solve it?

Write your solution in the editor and get an instant AI grade on correctness, edge cases, and complexity.

Practice in the editor