Practice/Meta/Leetcode 1838. Frequency of the Most Frequent Element

Leetcode 1838. Frequency of the Most Frequent Element

CodingOptional

Problem

You are given an array of integers nums and an integer k representing your operation budget. In one operation, you can choose any element in the array and increment its value by 1.

Your goal is to maximize the frequency of any element in the array. The frequency of an element is the count of how many times it appears in the array after performing your operations.

Return the maximum frequency you can achieve for any element by performing at most k increment operations.

Requirements

1. You can only increment elements (never decrement)
2. Each increment operation costs 1 from your budget of k
3. You can distribute your operations across any elements in any way
4. Return the maximum count of identical elements you can create

Constraints

• 1 ≤ nums.length ≤ 105
• 1 ≤ nums[i] ≤ 105
• 0 ≤ k ≤ 109
• Time complexity should be O(n log n) or better
• Space complexity should be O(1) excluding the sort

Examples

Example 1:

Input: nums = [1, 2, 4], k = 5 Output: 3 Explanation: We can increment 1 to 4 (cost 3) and 2 to 4 (cost 2). Total cost is 5, and we now have three elements with value 4.

Example 2:

Input: nums = [1, 4, 8, 13], k = 5 Output: 2 Explanation: We can increment 4 to 8 with cost 4, giving us two 8's. We cannot afford to make three or more elements equal.

Example 3:

Input: nums = [3, 3, 3, 3], k = 0 Output: 4 Explanation: All elements are already equal, so no operations needed.