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.

Top K Most Frequent Values with Smaller-Value Tie-Break

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 (the number of times the value occurs), highest frequency first. When two values have the same frequency, the smaller value ranks first. Return the first k values of this ranking as a list, in ranking order.

Implement k_most_frequent(nums, k).

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

Every value and every frequency fits in a signed 32-bit integer. The Java and C++ signatures take and return 64-bit integers (long / long long).

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.

Hints

1. Start by finding out how many times each distinct value occurs in nums.
2. The ranking is one total order: a higher count always comes first, and between equal counts the smaller value comes first. The answer is the first k values of that order.
3. Check what happens when several values share the frequency at the k-th position: only the smaller ones make the cut.

Approach

Count the occurrences of every distinct value in one pass with a hash map. Then sort the distinct values by the key (frequency descending, value ascending) and return the first k of them. Correctness: that comparator is exactly the ranking the statement defines, and because two distinct values never compare equal under it, it is a strict total order, so the sorted list is the unique ranking. Its length-k prefix is therefore the answer, including when several values tie at the cutoff frequency: the smaller tied values sort first and are the ones kept. Edge cases: a single element, or a single distinct value, returns that value; k = d returns the whole ranking; negative values, zero and the +/-10^9 extremes must be compared numerically. JavaScript needs an explicit numeric comparator because its default sort is lexicographic, and Java and C++ compare values directly instead of subtracting them.

• Time complexity: O(n + d log d)
• Space complexity: O(d)