2025-10-22 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's October LeetCoding Challenge with cpp.

October LeetCoding Challenge 22

Description

Maximum Frequency of an Element After Performing Operations II

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

Solution

class Solution {
public:
  int maxFrequency(vector<int>& nums, int k, int numOperations) {
    int len = nums.size();
    if(len == 1) return 1;
    sort(nums.begin(), nums.end());
    int left = 0;
    int right = 0;
    for(int i = 0; i < len; ++i) {
      int target = min<long long>(nums[i] + 2LL * k, INT_MAX);
      while(left < len && nums[left] <= target) {
        left += 1;
      }
      right = max(right, left - i);
    }
    right = min(right, numOperations);
    left = 0;
    int index = 0;
    int freq = 0;
    for(int i = 0; i < len; ++i) {
      int n = nums[i];
      freq = (i && nums[i] == nums[i - 1]) ? freq + 1 : 1;
      int mmin = n - k;
      int mmax = n + k;
      while((index < len && nums[index] < mmin) || (left < len && nums[left] <= mmax)) {
        if((index < len && nums[index] < mmin)) {
          index += 1;
        } else {
          left += 1;
        }
      }
      right = max(right, min(freq + numOperations, left - index));
    }
    return right;
  }
};

// Accepted
// 633/633 cases passed (35 ms)
// Your runtime beats 96.21 % of cpp submissions
// Your memory usage beats 99.05 % of cpp submissions (83.2 MB)
Algorithm