Skip to content

3640. Maximum Frequency Of An Element After Performing Operations II

Array Binary Search Sliding Window Sorting Prefix Sum

Problem - Maximum Frequency Of An Element After Performing Operations II

Hard

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

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        count = defaultdict(int)
        table = defaultdict(int)

        for num in nums:
            count[num] += 1
            table[num] += 0
            table[num - k] += 1
            table[num + k + 1] -= 1

        result = sum_val = 0
        for val, occ in sorted(table.items()):
            sum_val += occ
            result = max(result, min(sum_val, count[val] + numOperations))

        return result

Submission Stats:

  • Runtime: 1488 ms (35.48%)
  • Memory: 79 MB (6.45%)