IntermediateHashingHeaps
Top K Frequent Elements
Problem
Given an integer array nums and an integer k, return the k most frequent elements. The answer is guaranteed to be unique (no ties at the k-th position), and it may be returned in any order. Aim for a solution better than O(n log n).
Constraints
- 1 ≤ n ≤ 10^5
- -10^4 ≤ nums[i] ≤ 10^4
- 1 ≤ k ≤ number of distinct elements
Examples
in: nums = [1,1,1,2,2,3], k = 2
out: [1,2]
in: nums = [1], k = 1
out: [1]
What this tests
- Two-phase thinking: count, then select
- Size-k min-heap on (frequency, value) pairs
- Bucket sort keyed by frequency for a true O(n)
- Recognising when quickselect applies to a derived array
- Reasoning about the number of distinct elements
dvsn
Pattern RecognitionComplexity AnalysisOptimizationCommunication
Progressive hints
Choose how much help you want. Each hint reveals a little more; the pattern is not named until hint 2.
Hint 1Direction
Hint 2Pattern
Hint 3Data structure
Hint 4Algorithm
Hint 5Pseudocode
Solution
Solve in your language
The editor, starter code and solution adapt to the language you pick — C++, JavaScript, TypeScript or Python.
Solve in
Candidate thinking
How a strong candidate reasons through this problem, step by step.
Try the problem yourself first (or run the mock interview), then compare your process against a strong candidate's.
Follow-up engine
Requirements change; so does the right algorithm.
F1
Return the top
k in decreasing order of frequency.F2
Elements arrive as a stream and you must answer top-k at any time.
F3
Top
k most frequent *words*, with ties broken alphabetically.F4
The data does not fit in memory (billions of elements). How do you approximate?