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
Similar Problems

Solution

Method 1 - Two-pass sliding windows with frequency map (existing and hypothetical targets)

Intuition

Each input value v defines an inclusive interval of targets it can be moved to: [v - k, v + k]. If a target t lies inside that interval then the element v can be changed (with one operation) to become t. So for any candidate target t the number of elements that can be turned into t equals the number of intervals that cover t. Elements already equal to t count for free. With at most numOperations changes we can convert up to numOperations additional covered elements. This is a classic sweep-line / difference-array application: add +1 at interval start and -1 after interval end, sweep the keys in order and track how many intervals cover each candidate point t.

Note: Method 1 does not sort the input array nums. The O(n log n) cost comes from ordering interval endpoints or using ordered-map (TreeMap / std::map / BTreeMap) operations, not from sorting nums itself.

Approach

  1. Build a frequency map count of original values in nums (how many are already equal to a target).
  2. Build a difference map diff (ordered map): for every v in nums do diff[v-k] += 1 and diff[v+k+1] -= 1. Also insert v into the set of keys so we evaluate the exact points that appear in nums.
  3. Sweep the ordered keys of diff accumulating a running cover value. At each key t the cover value equals how many numbers have t in their [v-k, v+k] interval.
  4. The achievable frequency at t is count.get(t, 0) + min(cover - count.get(t, 0), numOperations). Update the global maximum.
  5. Return the global maximum.

This method examines only O(m) distinct keys where m is the number of unique endpoints / values, so overall complexity is O(n log n) dominated by ordered-map operations.

This approach is in a way very close to sweep line approach on the difference array.

Complexity

  • ⏰ Time complexity: O(n log n) – Building and iterating the ordered maps uses logarithmic-time map operations per input element.
  • 🧺 Space complexity: O(n) – We store counts and difference events for up to O(n) distinct points.

Code

 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
27
28
29
30

class Solution {
public:
    int maxFrequency(std::vector<int>& nums, int k, int numOperations) {
        if (nums.empty()) return 0;
        std::map<long long, int> diff; // ordered keys
        std::unordered_map<int,int> count;
        for (int v : nums) {
            count[v]++;
            long long a = (long long)v - k;
            long long b = (long long)v + k + 1; // end + 1 for inclusive interval
            diff[a] += 1;
            diff[b] -= 1;
            // ensure exact value is present as a key so we evaluate it
            diff[v] += 0;
        }

        int ans = 0;
        long long cover = 0;
        for (auto &p : diff) {
            cover += p.second;
            int t = (int)p.first;
            int base = count.count(t) ? count[t] : 0;
            long long others = cover - base;
            if (others < 0) others = 0;
            int achievable = base + (int)std::min<long long>(others, numOperations);
            ans = std::max(ans, achievable);
        }
        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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

package main

import (
    "sort"
)

// maxFrequency returns the maximum achievable frequency using the sweep-line difference map.
func maxFrequency(nums []int, k int, numOperations int) int {
    if len(nums) == 0 { return 0 }
    count := make(map[int]int)
    diff := make(map[int]int)
    keys := make([]int, 0)
    present := make(map[int]bool)

    for _, v := range nums {
        count[v]++
        a := v - k
        b := v + k + 1
        diff[a] += 1
        diff[b] -= 1
        if !present[a] { keys = append(keys, a); present[a] = true }
        if !present[b] { keys = append(keys, b); present[b] = true }
        if !present[v] { keys = append(keys, v); present[v] = true }
    }

    sort.Ints(keys)
    ans := 0
    cover := 0
    for _, t := range keys {
        cover += diff[t]
        base := count[t]
        others := cover - base
        if others < 0 { others = 0 }
        achievable := base
        if int(others) > numOperations {
            achievable += numOperations
        } else {
            achievable += others
        }
        if achievable > ans { ans = achievable }
    }
    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
27
28
29

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        if (nums.length == 0) return 0;
        Map<Integer, Integer> count = new HashMap<>();
        TreeMap<Integer, Integer> diff = new TreeMap<>();

        for (int v : nums) {
            count.put(v, count.getOrDefault(v, 0) + 1);
            int a = v - k;
            int b = v + k + 1;
            diff.put(a, diff.getOrDefault(a, 0) + 1);
            diff.put(b, diff.getOrDefault(b, 0) - 1);
            diff.putIfAbsent(v, 0); // ensure we evaluate exact values
        }

        int ans = 0;
        int cover = 0;
        for (Map.Entry<Integer, Integer> e : diff.entrySet()) {
            int point = e.getKey();
            cover += e.getValue();
            int base = count.getOrDefault(point, 0);
            int others = cover - base;
            if (others < 0) others = 0;
            int achievable = base + Math.min(others, numOperations);
            ans = Math.max(ans, achievable);
        }
        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
27
28

class Solution {
    fun maxFrequency(nums: IntArray, k: Int, numOperations: Int): Int {
        if (nums.isEmpty()) return 0
        val count = mutableMapOf<Int, Int>()
        val diff = java.util.TreeMap<Int, Int>()

        for (v in nums) {
            count[v] = count.getOrDefault(v, 0) + 1
            val a = v - k
            val b = v + k + 1
            diff[a] = diff.getOrDefault(a, 0) + 1
            diff[b] = diff.getOrDefault(b, 0) - 1
            diff.putIfAbsent(v, 0)
        }

        var ans = 0
        var cover = 0
        for ((point, delta) in diff) {
            cover += delta
            val base = count.getOrDefault(point, 0)
            var others = cover - base
            if (others < 0) others = 0
            val achievable = base + kotlin.math.min(others, numOperations)
            ans = kotlin.math.max(ans, achievable)
        }
        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
27

class Solution:
    def maxFrequency(self, nums: list[int], k: int, numOperations: int) -> int:
        if not nums:
            return 0
        from collections import Counter
        count = Counter(nums)
        diff = {}
        keys = set()
        for v in nums:
            a = v - k
            b = v + k + 1
            diff[a] = diff.get(a, 0) + 1
            diff[b] = diff.get(b, 0) - 1
            keys.add(a); keys.add(b); keys.add(v)

        keys = sorted(keys)
        cover = 0
        ans = 0
        for t in keys:
            cover += diff.get(t, 0)
            base = count.get(t, 0)
            others = cover - base
            if others < 0:
                others = 0
            achievable = base + min(others, numOperations)
            ans = max(ans, achievable)
        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
27
28
29
30
31

use std::collections::HashMap;
use std::collections::BTreeMap;

impl Solution {
    pub fn maxFrequency(nums: Vec<i32>, k: i32, numOperations: i32) -> i32 {
        if nums.is_empty() { return 0 }
        let mut count: HashMap<i32, i32> = HashMap::new();
        let mut diff: BTreeMap<i64, i32> = BTreeMap::new();
        for &v in &nums {
            *count.entry(v).or_insert(0) += 1;
            let a = v as i64 - k as i64;
            let b = v as i64 + k as i64 + 1;
            *diff.entry(a).or_insert(0) += 1;
            *diff.entry(b).or_insert(0) -= 1;
            diff.entry(v as i64).or_insert(0);
        }

        let mut ans = 0;
        let mut cover: i32 = 0;
        for (point, delta) in diff {
            cover += delta;
            let t = point as i32;
            let base = *count.get(&t).unwrap_or(&0);
            let mut others = cover - base;
            if others < 0 { others = 0 }
            let achievable = base + std::cmp::min(others, numOperations);
            ans = std::cmp::max(ans, achievable);
        }
        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

function maxFrequency(nums: number[], k: number, numOperations: number): number {
    if (nums.length === 0) return 0;
    const count = new Map<number, number>();
    const diff = new Map<number, number>();
    const keys = new Set<number>();
    for (const v of nums) {
        count.set(v, (count.get(v) ?? 0) + 1);
        const a = v - k;
        const b = v + k + 1;
        diff.set(a, (diff.get(a) ?? 0) + 1);
        diff.set(b, (diff.get(b) ?? 0) - 1);
        keys.add(a); keys.add(b); keys.add(v);
    }
    const sortedKeys = Array.from(keys).sort((x,y) => x - y);
    let cover = 0;
    let ans = 0;
    for (const t of sortedKeys) {
        cover += diff.get(t) ?? 0;
        const base = count.get(t) ?? 0;
        let others = cover - base;
        if (others < 0) others = 0;
        const achievable = base + Math.min(others, numOperations);
        ans = Math.max(ans, achievable);
    }
    return ans;
};