Maximize Element Frequency with Limited Increments

Implement max_frequency_after_increments(nums: list[int], k: int) -> int.

In one operation, choose an element of nums and increase it by 1. You may perform at most k operations in total. Return the largest possible frequency of any value after the operations.

Input Domain

• 1 <= len(nums) <= 100,000.
• 1 <= nums[i] <= 100,000.
• 0 <= k <= 10^14.
• Values and intermediate operation counts fit in signed 64-bit integers.

Output Rules

• Return only the maximum attainable frequency.
• Elements may be increased but never decreased.
• If several target values attain the same maximum, the returned scalar is unchanged, so no tie-break is needed.

Constraints

• Target time complexity is O(n log n) or better.
• Additional space may be O(n).

Examples

Example 1

Input: nums = [1,3,5,7,8,9,10,15], k = 6

Output: 4

Raising 7, 8, and 9 to 10 costs 3 + 2 + 1 = 6, producing four copies of 10.

Example 2

Input: nums = [1,3,5,10,10,10,10,15], k = 0

Output: 4

No increments are available, and 10 already appears four times.

Hint: Equalize toward an existing value

After ordering the values, consider a contiguous group raised to match its largest member and maintain the cost of that choice.