Maximize Element Frequency with Limited Increments

Problem Statement

You are given an array of integers nums and an integer k. In a single operation, you can choose any index i and increment nums[i] by 1. You can perform at most k operations in total.

Return the maximum possible frequency of any element in nums after applying at most k operations.

Function Signature

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

Examples

Example 1:

Input: nums = [1, 2, 4], k = 5
Output: 3
Explanation: Increment 1 three times to get 4, and increment 2 two times to get 4.
The array becomes [4, 4, 4] with 3 + 2 = 5 operations. The frequency of 4 is 3.

Example 2:

Input: nums = [1, 4, 8, 13], k = 5
Output: 2
Explanation: There are multiple optimal choices:
- Increment 1 three times to reach 4 (using 3 ops), resulting in two 4s.
- Increment 4 four times to reach 8 (using 4 ops), resulting in two 8s.
The maximum frequency attainable is 2.

Example 3:

Input: nums = [3, 9, 6], k = 2
Output: 1
Explanation: No single element can be made equal to another within 2 operations. The maximum frequency is 1.

Constraints

• 1 <= len(nums) <= 10^5
• 1 <= nums[i] <= 10^5
• 1 <= k <= 10^9

Edge Cases to Consider

• Array has a single element (len(nums) == 1).
• k is smaller than any difference between distinct elements.
• k is large enough to make all elements equal to the maximum element.