Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


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 <= 10^5
  • 1 <= nums[i] <= 10^5
  • 0 <= k <= 10^5
  • 0 <= numOperations <= nums.length

Solution

Method 1 – Sorting and Sliding Window

Intuition

To maximize the frequency of any element after performing up to numOperations operations (each changing a different index by at most k), we want to make as many elements as possible equal to some value. By sorting the array, we can use a sliding window to efficiently check, for each possible target, how many elements can be made equal to it within the allowed operations.

Approach

  1. Sort nums.
  2. Use a sliding window with two pointers (l, r).
  3. For each r, maintain the total cost to make all elements in the window equal to nums[r] (i.e., sum of nums[r] - nums[i] for all i in [l, r]).
  4. For each window, check if the number of operations needed is within numOperations * k.
  5. If not, move l forward and update the cost.
  6. The answer is the maximum window size found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end());
        long long sum = 0;
        int l = 0, ans = 1, n = nums.size();
        for (int r = 0; r < n; ++r) {
            sum += nums[r];
            while ((long long)nums[r] * (r - l + 1) - sum > (long long)numOperations * k) {
                sum -= nums[l++];
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

func maxFrequency(nums []int, k int, numOperations int) int {
    sort.Ints(nums)
    sum, l, ans := 0, 0, 1
    for r, v := range nums {
        sum += v
        for int64(nums[r]*(r-l+1)-sum) > int64(numOperations)*int64(k) {
            sum -= nums[l]
            l++
        }
        if r-l+1 > ans {
            ans = r - l + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);
        long sum = 0;
        int l = 0, ans = 1, n = nums.length;
        for (int r = 0; r < n; r++) {
            sum += nums[r];
            while ((long)nums[r] * (r - l + 1) - sum > (long)numOperations * k) {
                sum -= nums[l++];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun maxFrequency(nums: IntArray, k: Int, numOperations: Int): Int {
        nums.sort()
        var sum = 0L
        var l = 0
        var ans = 1
        for (r in nums.indices) {
            sum += nums[r]
            while (nums[r].toLong() * (r - l + 1) - sum > numOperations.toLong() * k) {
                sum -= nums[l++]
            }
            ans = maxOf(ans, r - l + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def maxFrequency(self, nums: list[int], k: int, numOperations: int) -> int:
        nums.sort()
        l = 0
        s = 0
        ans = 1
        for r, v in enumerate(nums):
            s += v
            while nums[r] * (r - l + 1) - s > numOperations * k:
                s -= nums[l]
                l += 1
            ans = max(ans, r - l + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32, num_operations: i32) -> i32 {
        let mut nums = nums;
        nums.sort();
        let mut sum = 0i64;
        let mut l = 0;
        let mut ans = 1;
        for r in 0..nums.len() {
            sum += nums[r] as i64;
            while (nums[r] as i64) * (r as i64 - l as i64 + 1) - sum > (num_operations as i64) * (k as i64) {
                sum -= nums[l] as i64;
                l += 1;
            }
            ans = ans.max(r as i32 - l as i32 + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
    maxFrequency(nums: number[], k: number, numOperations: number): number {
        nums.sort((a, b) => a - b);
        let sum = 0, l = 0, ans = 1;
        for (let r = 0; r < nums.length; r++) {
            sum += nums[r];
            while (nums[r] * (r - l + 1) - sum > numOperations * k) {
                sum -= nums[l++];
            }
            ans = Math.max(ans, r - l + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), where n is the length of the array, due to sorting and the sliding window.
  • 🧺 Space complexity: O(1) (or O(n) if sorting in-place is not allowed), as only a few variables are used.