Top k most frequent values with a deterministic tie order
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given a list of integers and a number `k`, return the `k` values that occur most often in the list. The report names this problem without further detail; the tie rule below is added so that every input has exactly one correct answer.
### Function Signature
```python
def top_k_frequent(nums: list[int], k: int) -> list[int]:
```
### Rules
- Order the distinct values of `nums` by how many times each occurs, highest count first. When two values occur the same number of times, the smaller value comes first.
- Return the first `k` values in that order, as a list in that same order.
- Each value appears at most once in the output.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- `1 <= k <= ` the number of distinct values in `nums`
### Examples
**Example 1**
```text
Input: nums = [4, 1, 4, 2, 2, 4, 3], k = 2
Output: [4, 2]
```
`4` occurs three times and `2` twice; `1` and `3` occur once each.
**Example 2**
```text
Input: nums = [5, 7, 7, 5, 9], k = 1
Output: [5]
```
`5` and `7` both occur twice. The tie is broken by the smaller value, so `5` comes first.
**Example 3**
```text
Input: nums = [-1, 3, -1, 3, 8, 8, 2], k = 3
Output: [-1, 3, 8]
```
`-1`, `3` and `8` all occur twice and are listed in ascending order; `2` occurs once.
Overview: Given a list of integers and a number k, return the k values that occur most often, ordered by frequency with ties broken by the smaller value. It tests counting with hash maps, selecting the top k efficiently and applying a deterministic tie rule.
Given a list of integers `nums` and an integer `k`, return the `k` values that occur most often in `nums`.
Order the distinct values of `nums` by how many times each occurs, highest count first. When two values occur the same number of times, the smaller value comes first. Return the first `k` values in that order, as a list in that same order. Each value appears at most once in the output.
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- `1 <= k <=` the number of distinct values in `nums`
No value or count can exceed 2^31 - 1, so every number fits in a signed 32-bit integer (`int` in Java and C++).
### Example 1
```text
Input: nums = [4, 1, 4, 2, 2, 4, 3], k = 2
Output: [4, 2]
```
`4` occurs three times and `2` twice; `1` and `3` occur once each.
### Example 2
```text
Input: nums = [5, 7, 7, 5, 9], k = 1
Output: [5]
```
`5` and `7` both occur twice. The tie is broken by the smaller value, so `5` comes first.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- 1 <= k <= the number of distinct values in nums
Examples
Input: ([7], 1)
Expected Output: [7]
Explanation: Minimum valid input: one element, so k = 1 returns it.
Input: ([3, 3, 3, 3, 3], 1)
Expected Output: [3]
Explanation: Degenerate: every element is the same value, so there is one distinct value and k = 1.
Hints
- Before you can rank anything, you need to know how many times each distinct value occurs in nums.
- The ranking uses two keys: the count (higher first), and the value itself (smaller first) only when two counts are equal.
- Only the first k values of the full ranking are returned, and they must stay in ranking order rather than being re-sorted by value.