Top K Frequent Elements

Statement

Given an integer array nums and an integer k, return the k most frequent elements. The answer can be returned in any order.

Examples

nums = [1, 1, 1, 2, 2, 3], k = 2
→ [1, 2]

nums = [1], k = 1
→ [1]

nums = [4, 1, -1, 2, -1, 2, 3], k = 2
→ [-1, 2]   (both appear twice)

Constraints

• 1 ≤ len(nums) ≤ 10⁵
• -10⁴ ≤ nums[i] ≤ 10⁴
• k is in the range [1, number of distinct values].
• Solve in better than O(n log n). Sorting is the obvious answer; the interview is checking whether you can beat it.

What this problem is really testing

Whether you reach for the right complexity. The naive sort is O(n log n); the canonical heap solution is O(n log k); the bucket-sort solution is O(n). Three approaches, each better than the last. The problem is small but the spread of "good enough" to "optimal" is large, and interviewers use it to see how far you push.