Find top-K frequent values with tiebreaks
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
##### Question
Given an integer array `nums` and an integer `k`, return the `k` values with the highest frequency. The array can contain up to 10^6 elements.
When multiple values share the same frequency, break ties deterministically:
1. First by **smaller numeric value** (for string inputs, break ties lexicographically instead).
2. Then by **earlier first-occurrence index** in the array.
Your solution should address all of the following:
1. Return the correct `k` values under the tie-breaking rules above. If `k` exceeds the number of distinct values, return all of the distinct values.
2. Provide an algorithm faster than `O(n log n)` — for example `O(n)` or `O(n log k)` — and justify why it stays correct under the tie rules.
3. Discuss and compare the trade-offs among the main approaches: bucket counting by frequency, a size-`k` heap, and a selection/quickselect-based partition. State the time and space complexity of each.
4. **Follow-up:** For an array of length `n`, derive the maximum possible number of *distinct* frequency values achievable across its unique elements, and justify your formula.
5. **Follow-up:** How would you validate and guard against invalid inputs (e.g. non-integer elements, negative or non-integer `k`, an extremely large `n`) while keeping the service robust?
Quick Answer: Given an integer array and k, return the k highest-frequency values, breaking ties by smaller numeric value then earlier first-occurrence index (lexicographically for strings), and returning all uniques when k is too large. The solution covers an O(n) bucket-counting algorithm plus O(n log k) heap and expected-linear quickselect alternatives with their trade-offs, derives floor((sqrt(8n+1)-1)/2) as the maximum number of distinct frequency values, and outlines input validation for robustness at scale.
Given an integer array `nums` and an integer `k`, return the `k` values with the highest frequency.
When multiple values share the same frequency, break ties deterministically:
1. First by **smaller numeric value**.
2. Then by **earlier first-occurrence index** in the array.
Rules:
- Return the result as a list ordered from highest rank to lowest under the rules above (frequency descending, then smaller value, then earlier first occurrence).
- If `k` is greater than or equal to the number of distinct values, return all of the distinct values (still in ranked order).
- If `k <= 0`, return an empty list.
Aim for an algorithm faster than `O(n log n)` overall (counting is `O(n)`; only the relevant tie tiers need ordering).
Constraints
- 0 <= len(nums) <= 10^6
- Elements are integers (may be negative).
- k may be 0, negative, or larger than the number of distinct values.
- If k <= 0, return [].
- If k >= number of distinct values, return all distinct values in ranked order.
Examples
Input: ([1, 1, 1, 2, 2, 3], 2)
Expected Output: [1, 2]
Explanation: Frequencies: 1->3, 2->2, 3->1. Top 2 by frequency are 1 then 2.
Input: ([4, 4, 5, 5, 6], 2)
Expected Output: [4, 5]
Explanation: 4 and 5 both have frequency 2; tie broken by smaller value (4 before 5). 6 has frequency 1.
Hints
- Count each value's frequency in one O(n) pass, and record its first-occurrence index in the same pass.
- Define a single total order over the distinct values: frequency descending, then smaller numeric value, then earlier first-occurrence index. Sort or select by that key.
- Two distinct integers can never be equal, so the first-occurrence tiebreak only ever resolves ties between a value's own equal keys — it is a stable secondary key, harmless to keep.
- For an O(n)-style speedup over O(n log n), bucket values by frequency (buckets[f] = values seen f times) and walk buckets from high frequency to low, ordering only the tier you are currently emitting from.
- Handle k <= 0 (return []) and k >= distinct count (return all distinct, still ranked) as explicit branches.