Maximum Frequency of an Element After Performing Operations II

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

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

Solution

Method 1 - Sweep line (difference array)

We have already solved this problem efficiently in [method 1](maximum-frequency-of-an-element-after-performing-operations-i.md/#method-1---two-pass-sliding-windows-with-frequency-map-(existing-and-hypothetical-targets)) in the first part of this problem. But here is a recap below.

Intuition

Each value v in nums can be moved to any target in the inclusive interval [v - k, v + k]. For a fixed candidate target t, any v whose interval covers t can be converted to t with one operation; elements already equal to t need zero operations. So the number of elements that can become t equals the number of intervals covering t. With at most numOperations changes we can convert up to numOperations covered elements that are not already t. This is naturally handled by a sweep-line (difference array) over interval endpoints.

Approach

1. Build a frequency map count mapping each original value to its occurrence count.
2. For each v in nums, emit a difference event: diff[v-k] += 1 and diff[v+k+1] -= 1 (end+1 for inclusive intervals). Also ensure the exact value v is present in the keys so we evaluate existing targets.
3. Sort the distinct keys and sweep them, maintaining a running cover which equals how many intervals currently cover the point.
4. For each key t compute base = count.get(t, 0) (already-equal elements) and others = max(0, cover - base) (covered elements that would need an operation). The achievable frequency at t is base + min(others, numOperations). Track the maximum and return it.

This inspects only O(m) keys (endpoints + original values) and uses ordered-map operations, giving O(n log n) time.

Complexity

• ⏰ Time complexity: O(n log n) – We build and iterate an ordered set/map of endpoints; sorting/ordered-map operations dominate.
• 🧺 Space complexity: O(n) – We store counts and difference events for up to O(n) distinct keys.

Code

C++

class Solution {
public:
    int maxFrequency(std::vector<int>& nums, int k, int numOperations) {
        if (nums.empty()) return 0;
        std::map<long long,int> diff;
        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;
            diff[a] += 1;
            diff[b] -= 1;
            diff[v] += 0; // ensure exact value is evaluated
        }

        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;
    }
};

Go

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)
    seen := make(map[int]bool)

    for _, v := range nums {
        count[v]++
        a := v - k
        b := v + k + 1
        diff[a] += 1
        diff[b] -= 1
        if !seen[a] { keys = append(keys, a); seen[a] = true }
        if !seen[b] { keys = append(keys, b); seen[b] = true }
        if !seen[v] { keys = append(keys, v); seen[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 + min(others, numOperations)
        if achievable > ans { ans = achievable }
    }
    return ans
}

func min(a, b int) int { if a < b { return a }; return b }

Java

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);
        }

        int ans = 0;
        int cover = 0;
        for (Map.Entry<Integer,Integer> e : diff.entrySet()) {
            cover += e.getValue();
            int t = e.getKey();
            int base = count.getOrDefault(t, 0);
            int others = cover - base;
            if (others < 0) others = 0;
            int achievable = base + Math.min(others, numOperations);
            ans = Math.max(ans, achievable);
        }
        return ans;
    }
}

Kotlin

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
    }
}

Python

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

Rust

use std::collections::{HashMap, BTreeMap};

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32, num_operations: 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, num_operations);
            ans = std::cmp::max(ans, achievable);
        }
        ans
    }
}

TypeScript

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;
};