Return the k most frequent values in an array with a deterministic tie rule

Given an integer array nums and an integer k, return the k values that occur most often in nums.

Rank the distinct values of nums by frequency (number of occurrences), highest first, and break ties between values with equal frequency by putting the smaller value first. Return the first k values of this ranking, in ranking order.

Function Signature

def k_most_frequent(nums: list[int], k: int) -> list[int]:

Rules

• Each distinct value appears at most once in the output.
• The output order is the ranking order: frequency descending, then value ascending.
• The same rule decides which values are included when several values tie at the cutoff: a smaller value always ranks ahead of a larger value with the same frequency.

Constraints

• 1 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• 1 <= k <= d, where d is the number of distinct values in nums

Examples

Example 1

Input: nums = [4, 1, 4, 2, 1, 4, 3], k = 2
Output: [4, 1]

4 occurs three times, 1 twice, and 2 and 3 once each.

Example 2

Input: nums = [3, 3, 2, 2, 1, 1, 0], k = 2
Output: [1, 2]

1, 2 and 3 each occur twice. The tie is broken by the smaller value, so 1 and 2 are returned and 3 is not.

Example 3

Input: nums = [-5, 7, -5, 7, 9], k = 3
Output: [-5, 7, 9]

-5 and 7 each occur twice, and -5 is smaller. 9 occurs once.