3640. Maximum Frequency of an Element After Performing Operations II

Hard
Array
Binary Search
Sliding Window
Sorting
Prefix Sum

Description

You are given an integer array nums and two integers k and numOperations.

You must perform an operation numOperations times on nums, where in each operation you:

  • Select an index i that was not selected in any previous operations.
  • Add an integer in the range [-k, k] to nums[i].

Return the maximum possible frequency of any element in nums after performing the operations.

 

Example 1:

Input: nums = [1,4,5], k = 1, numOperations = 2

Output: 2

Explanation:

We can achieve a maximum frequency of two by:

  • Adding 0 to nums[1], after which nums becomes [1, 4, 5].
  • Adding -1 to nums[2], after which nums becomes [1, 4, 4].

Example 2:

Input: nums = [5,11,20,20], k = 5, numOperations = 1

Output: 2

Explanation:

We can achieve a maximum frequency of two by:

  • Adding 0 to nums[1].

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 0 <= k <= 109
  • 0 <= numOperations <= nums.length

Hints

Hint 1
The optimal values to check are <code>nums[i] - k</code>, <code>nums[i]</code>, and <code>nums[i] + k</code>.

Statistics

Acceptance
53.9%
Submissions
122,333
Accepted
65,956