Top K Frequent Values
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Top K Frequent Values
Implement `top_k_frequent(values: list[int], k: int) -> list[int]`.
Return the `k` distinct integers that occur most frequently in `values`.
### Input Domain
- `1 <= len(values) <= 200,000`.
- Every value fits in a signed 32-bit integer.
- `1 <= k <=` the number of distinct values.
### Output Rules
- Sort the result by descending frequency.
- When two values have the same frequency, place the smaller integer first.
- Return exactly `k` values and no duplicates.
- The input list must not be modified.
### Constraints
- Target time is `O(n log k)` or `O(n)` after frequency counting.
- Additional space may be proportional to the number of distinct values.
### Examples
#### Example 1
Input: `values = [1,1,1,2,2,3], k = 2`
Output: `[1,2]`
#### Example 2
Input: `values = [4,4,5,5,6,6], k = 2`
Output: `[4,5]`
```hint Make ties part of ranking
Treat each candidate as a pair of frequency and value so the same comparison controls selection and final ordering.
```
Quick Answer: Return the top k most frequent integers with a deterministic smaller-value tie-break and efficient frequency selection.
Implement `top_k_frequent(values: list[int], k: int) -> list[int]`.
Return the `k` distinct integers that occur most frequently in `values`. Order the result by descending frequency. When two values have the same frequency, place the smaller integer first. Return exactly `k` values with no duplicates, and do not modify the input list.
Constraints
- 1 <= len(values) <= 200,000.
- Every value fits in a signed 32-bit integer.
- 1 <= k <= the number of distinct values.
- Return exactly k distinct values in descending frequency order, breaking ties by smaller integer first.
- The input list must not be modified.
- Target time is O(n log k) or O(n) after frequency counting.
- Additional space may be proportional to the number of distinct values.
Examples
Input: ([1, 1, 1, 2, 2, 3], 2)
Expected Output: [1, 2]
Explanation: The frequencies are 3, 2, and 1, so 1 and 2 are the first two values in the required ranking.
Input: ([4, 4, 5, 5, 6, 6], 2)
Expected Output: [4, 5]
Explanation: All three values occur twice, so the smaller values 4 and 5 win the tie.
Hints
- Treat each candidate as a pair of frequency and value so the same comparison controls selection and final ordering.