Find k most frequent elements, discuss O(n)

Question

Given an integer array nums of length n and an integer k (where 1 ≤ k ≤ the number of distinct values in nums), return any ordering of the k values that occur most frequently.

Work through the problem in increasing order of efficiency:

1. Baseline. Describe a straightforward approach (e.g. count frequencies, then sort the distinct values by frequency). Analyze its time and space complexity.
2. Heap-based. Improve the selection step to O(n log k) time using a typical data structure (a size-k heap) instead of fully sorting all distinct values. Explain why this is better when k is much smaller than the number of distinct values.
3. Linear time. Achieve expected O(n) time and O(n) extra space without any global sort. Explain the data structures you would use (bucket sort by frequency, or Quickselect on the frequency counts) and implement that approach.

Discuss the time/space trade-offs of each approach and when each is preferable.

Example

nums = [1, 1, 1, 2, 2, 3], k = 2 -> [1, 2] (any order accepted)
nums = [1], k = 1 -> [1]