Find k most frequent elements, discuss O(n)

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]

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Top K Frequent Elements

Given an integer array nums of length n and an integer k (where 1 <= k <= the number of distinct values in nums), return the k values that occur most frequently. The k most-frequent values are uniquely determined; for this console, return them ordered by frequency descending, breaking ties by value ascending, so the result is deterministic.

Work through the problem in increasing order of efficiency and pick one to implement:

1. Baseline — Count frequencies with a hash map, then sort the distinct values by frequency and take the first k. Time O(n + d log d), space O(d), where d is the number of distinct values.
2. Heap-based — Keep a size-k min-heap keyed on frequency so you never fully order the long tail of infrequent values. Time O(n + d log k); strictly better than the baseline when k is much smaller than d.
3. Linear time — Use bucket sort by frequency: frequencies live in [1, n], so drop each value into a bucket indexed by its count and scan buckets from highest frequency down until you have k values. Time O(n), space O(n), with no global sort. (Quickselect on the frequency counts is the expected-O(n) alternative with O(1) extra selection space.)

Examples

nums = [1, 1, 1, 2, 2, 3], k = 2  ->  [1, 2]
nums = [1], k = 1                 ->  [1]

Constraints

• 1 <= nums.length <= 10^5
• -10^9 <= nums[i] <= 10^9
• 1 <= k <= number of distinct values in nums
• The k most-frequent values are uniquely determined for the given inputs

Hints

1. Every approach shares the same first step: count how often each value appears with a hash map in O(n) time.
2. You never need to fully sort all distinct values when you only want the top k — a size-k min-heap selects them in O(n + d log k).
3. No value can appear more than n times, so frequencies fall in [1, n]. Bucket the values by their count and scan from the highest bucket down for true O(n) time with no sort.

Solution

The interviewer is looking for the candidate to (1) recognize hash-map frequency counting as the shared O(n) preprocessing step, (2) progress from a full sort to a size-k heap (O(n + d log k)) by realizing only the top k matter, and (3) reach genuine linear time via bucket sort (frequencies are bounded by n) or expected-linear Quickselect, articulating that no global sort is needed. Strong answers state complexities precisely in terms of n, d, and k and explain the trade-offs rather than just coding one solution.

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

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....

Recommended Approach

When repeatedly combining the two smallest available values, use a min-heap. Pop the two smallest, add their sum to the total cost, and push the combined value back until one value remains. This is the same greedy structure as Huffman merging.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Time: O(n log n). Space: O(n).

Edge Cases and Tests

No values, one value, duplicate values, very large sums, and proving the greedy choice by exchange argument.

[1, 2] for nums=[1,1,1,2,2,3], k=2 (any ordering of the two most frequent values accepted); [1] for nums=[1], k=1.