2025-10-21 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

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

October LeetCoding Challenge 21

Description

Maximum Frequency of an Element After Performing Operations I

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 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]. nums becomes [1, 4, 5].
  • Adding -1 to nums[2]. 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] <= 105
  • 0 <= k <= 105
  • 0 <= numOperations <= nums.length

Solution

class Solution {
public:
  int maxFrequency(vector<int>& nums, int k, int numOperations) {
    int maxVal = *max_element(nums.begin(), nums.end()) + k + 2;
    vector<int> count(maxVal);

    for(auto n : nums) {
      count[n] += 1;
    }

    for(int i = 1; i < maxVal; ++i) {
      count[i] += count[i - 1];
    }

    int answer = 0;
    for(int i = 0; i < maxVal; ++i) {
      int left = max(0, i - k);
      int right = min(maxVal - 1, i + k);
      int total = count[right] - (left ? count[left - 1] : 0);
      int freq = count[i] - (i ? count[i - 1] : 0);
      answer = max(answer, freq + min(numOperations, total - freq));
    }
    return answer;
  }
};

// Accepted
// 635/635 cases passed (4 ms)
// Your runtime beats 99.27 % of cpp submissions
// Your memory usage beats 81.46 % of cpp submissions (96.2 MB)
Algorithm