Arrays & Hashing · 006Medium
Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned in any order.
Constraints
- 1 <= nums.length <= 10^5
- k is in the range [1, number of distinct elements]
- The answer is guaranteed to be unique.
Examples
topKFrequent([1, 1, 1, 2, 2, 3], 2) -> [1, 2] topKFrequent([1], 1) -> [1] // single element topKFrequent([1, 2], 2) -> [1, 2] // every value ties at count 1; any order topKFrequent([4, 4, 4, 4], 1) -> [4] // all identical topKFrequent([-1, -1, 2, 2, 2, 3], 2) -> [2, -1] // negatives are valid keys; any order topKFrequent([1, 1, 2, 2, 3], 3) -> [1, 2, 3] // k === number of distinct values
Edge cases
- k equals the number of distinct elements — return them all.
- All elements identical.
- Negative values are valid keys.
Show the target complexity (spoiler)
- Naive
- O(n log n) time — count, then sort every distinct value by frequency.
- Target
- O(n) time — bucket sort by frequency (a frequency can never exceed n), or a size-k heap for O(n log k).
Solve it
By hand, in your editor. The runner checks answers and timing.
git clone https://github.com/sarmadkung/optimal-round cd optimal-round # open problems/01-arrays-hashing/006-top-k-frequent-elements.js ./practice c 006