Top K Frequent Elements

The "what's trending today" question. Given a stream of events and a number k, return the k most frequent event IDs. At scale this is heap territory, but for moderate k there's a clever bucket-sort approach that runs in linear time and is worth knowing — it shows up surprisingly often in mid-to-senior interviews.

Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order. The answer is guaranteed to be unique.

Examples

Example 1:

• Input: nums = [1, 1, 1, 2, 2, 3], k = 2
• Output: [1, 2] (1 appears 3 times, 2 appears 2 times)

Example 2:

• Input: nums = [1], k = 1
• Output: [1]

Example 3:

• Input: nums = [4, 1, -1, 2, -1, 2, 3], k = 2
• Output: [-1, 2] (each appears 2 times, others appear once)

Constraints

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4
• 1 <= k <= number of unique elements in nums

Follow-up

Can you solve it in O(n) time? Naive sort-by-frequency is O(n log n). A min-heap of size k is O(n log k), better but not linear. Bucket sort by frequency (since the maximum frequency is n) lands at O(n) time — that's the answer worth practicing.