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]`, after which `nums` becomes `[1, 4, 5]`.
  * Adding -1 to `nums[2]`, after which `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^9
  • 0 <= k <= 10^9
  • 0 <= numOperations <= nums.length

Solution

Method 1 – Sorting and Sliding Window with Binary Search

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 and binary search to efficiently check, for each possible target, how many elements can be made equal to it within the allowed operations, considering the cost of increasing and decreasing values.

Approach

  1. Sort nums.
  2. Use prefix sums to quickly compute the sum of any subarray.
  3. For each index r, use binary search to find the leftmost index l such that the total cost to make all elements in nums[l..r] equal to nums[r] is within numOperations * k.
  4. The cost is nums[r] * (r-l+1) - (prefix[r+1] - prefix[l]).
  5. 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
17
18
19
20
21

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end());
        int n = nums.size(), ans = 1;
        vector<long long> pre(n+1);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        for (int r = 0; r < n; ++r) {
            int l = 0, m;
            int lo = 0, hi = r;
            while (lo <= hi) {
                m = (lo + hi) / 2;
                long long cost = 1LL * nums[r] * (r-m+1) - (pre[r+1] - pre[m]);
                if (cost <= 1LL * numOperations * k) hi = m - 1;
                else lo = m + 1;
            }
            ans = max(ans, r - lo + 1);
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

func maxFrequency(nums []int, k int, numOperations int) int {
    sort.Ints(nums)
    n := len(nums)
    pre := make([]int64, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + int64(nums[i])
    }
    ans := 1
    for r := 0; r < n; r++ {
        lo, hi := 0, r
        for lo <= hi {
            m := (lo + hi) / 2
            cost := int64(nums[r]) * int64(r-m+1) - (pre[r+1] - pre[m])
            if cost <= int64(numOperations)*int64(k) {
                hi = m - 1
            } else {
                lo = m + 1
            }
        }
        if r-lo+1 > ans {
            ans = r - lo + 1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Arrays.sort(nums);
        int n = nums.length, ans = 1;
        long[] pre = new long[n+1];
        for (int i = 0; i < n; i++) pre[i+1] = pre[i] + nums[i];
        for (int r = 0; r < n; r++) {
            int lo = 0, hi = r, m;
            while (lo <= hi) {
                m = (lo + hi) / 2;
                long cost = 1L * nums[r] * (r-m+1) - (pre[r+1] - pre[m]);
                if (cost <= 1L * numOperations * k) hi = m - 1;
                else lo = m + 1;
            }
            ans = Math.max(ans, r - lo + 1);
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    fun maxFrequency(nums: IntArray, k: Int, numOperations: Int): Int {
        nums.sort()
        val n = nums.size
        val pre = LongArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] + nums[i]
        var ans = 1
        for (r in 0 until n) {
            var lo = 0
            var hi = r
            while (lo <= hi) {
                val m = (lo + hi) / 2
                val cost = nums[r].toLong() * (r-m+1) - (pre[r+1] - pre[m])
                if (cost <= numOperations.toLong() * k) hi = m - 1 else lo = m + 1
            }
            ans = maxOf(ans, r - lo + 1)
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution:
    def maxFrequency(self, nums: list[int], k: int, numOperations: int) -> int:
        nums.sort()
        n = len(nums)
        pre = [0]
        for v in nums:
            pre.append(pre[-1] + v)
        ans = 1
        for r in range(n):
            lo, hi = 0, r
            while lo <= hi:
                m = (lo + hi) // 2
                cost = nums[r] * (r-m+1) - (pre[r+1] - pre[m])
                if cost <= numOperations * k:
                    hi = m - 1
                else:
                    lo = m + 1
            ans = max(ans, r - lo + 1)
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32, num_operations: i32) -> i32 {
        let mut nums = nums;
        nums.sort();
        let n = nums.len();
        let mut pre = vec![0i64; n+1];
        for i in 0..n {
            pre[i+1] = pre[i] + nums[i] as i64;
        }
        let mut ans = 1;
        for r in 0..n {
            let (mut lo, mut hi) = (0, r);
            while lo <= hi {
                let m = (lo + hi) / 2;
                let cost = nums[r] as i64 * (r as i64 - m as i64 + 1) - (pre[r+1] - pre[m]);
                if cost <= num_operations as i64 * k as i64 {
                    hi = m - 1;
                } else {
                    lo = m + 1;
                }
            }
            ans = ans.max(r as i32 - lo as i32 + 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    maxFrequency(nums: number[], k: number, numOperations: number): number {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        const pre = [0];
        for (let v of nums) pre.push(pre[pre.length-1] + v);
        let ans = 1;
        for (let r = 0; r < n; r++) {
            let lo = 0, hi = r;
            while (lo <= hi) {
                const m = Math.floor((lo + hi) / 2);
                const cost = nums[r] * (r-m+1) - (pre[r+1] - pre[m]);
                if (cost <= numOperations * k) hi = m - 1;
                else lo = m + 1;
            }
            ans = Math.max(ans, r - lo + 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n log n + n log n), where n is the length of the array, due to sorting and binary search for each index.
  • 🧺 Space complexity: O(n), for the prefix sum array.