3347. Maximum Frequency of an Element After Performing Operations II

Description

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.

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

Solutions

Solution 1: Difference Array

According to the problem description, for each element \(x\) in the array \(\textit{nums}\), we can change it to any integer within the range \([x-k, x+k]\). We want to perform operations on some elements in \(\textit{nums}\) to maximize the frequency of a certain integer in the array.

The problem can be transformed into merging all elements in the interval \([x-k, x+k]\) corresponding to each element \(x\), and finding the integer that contains the most original elements in the merged intervals. This can be implemented using a difference array.

We use a dictionary \(d\) to record the difference array. For each element \(x\), we perform the following operations on the difference array:

Add \(1\) at position \(x-k\), indicating that a new interval starts from this position.
Subtract \(1\) at position \(x+k+1\), indicating that an interval ends from this position.
Add \(0\) at position \(x\), ensuring that position \(x\) exists in the difference array for subsequent calculations.

At the same time, we need to record the number of occurrences of each element in the original array, using a dictionary \(cnt\) to implement this.

Next, we perform prefix sum calculation on the difference array to get how many intervals cover each position. For each position \(x\), we calculate the number of intervals covering it as \(s\). Then we discuss by cases:

If \(x\) appears in the original array, operations on \(x\) itself are meaningless. Therefore, there are \(s - cnt[x]\) other elements that can be changed to \(x\) through operations, but at most \(\textit{numOperations}\) operations can be performed. So the maximum frequency at this position is \(\textit{cnt}[x] + \min(s - \textit{cnt}[x], \textit{numOperations})\).
If \(x\) does not appear in the original array, then at most \(\textit{numOperations}\) operations can be performed to change other elements to \(x\). Therefore, the maximum frequency at this position is \(\min(s, \textit{numOperations})\).

Combining the above two cases, we can uniformly express it as \(\min(s, \textit{cnt}[x] + \textit{numOperations})\).

Finally, we traverse all positions, calculate the maximum frequency at each position, and take the maximum value among them as the answer.

The time complexity is \(O(n \times \log n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the array \(\textit{nums}\).

Python3JavaC++GoTypeScriptRustC#

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        cnt = defaultdict(int)
        d = defaultdict(int)
        for x in nums:
            cnt[x] += 1
            d[x] += 0
            d[x - k] += 1
            d[x + k + 1] -= 1
        ans = s = 0
        for x, t in sorted(d.items()):
            s += t
            ans = max(ans, min(s, cnt[x] + numOperations))
        return ans

class Solution {
    public int maxFrequency(int[] nums, int k, int numOperations) {
        Map<Integer, Integer> cnt = new HashMap<>();
        TreeMap<Integer, Integer> d = new TreeMap<>();
        for (int x : nums) {
            cnt.merge(x, 1, Integer::sum);
            d.putIfAbsent(x, 0);
            d.merge(x - k, 1, Integer::sum);
            d.merge(x + k + 1, -1, Integer::sum);
        }
        int ans = 0, s = 0;
        for (var e : d.entrySet()) {
            int x = e.getKey(), t = e.getValue();
            s += t;
            ans = Math.max(ans, Math.min(s, cnt.getOrDefault(x, 0) + numOperations));
        }
        return ans;
    }
}

class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        unordered_map<int, int> cnt;
        map<int, int> d;

        for (int x : nums) {
            cnt[x]++;
            d[x];
            d[x - k]++;
            d[x + k + 1]--;
        }

        int ans = 0, s = 0;
        for (const auto& [x, t] : d) {
            s += t;
            ans = max(ans, min(s, cnt[x] + numOperations));
        }

        return ans;
    }
};

func maxFrequency(nums []int, k int, numOperations int) (ans int) {
    cnt := make(map[int]int)
    d := make(map[int]int)
    for _, x := range nums {
        cnt[x]++
        d[x] = d[x]
        d[x-k]++
        d[x+k+1]--
    }

    s := 0
    keys := make([]int, 0, len(d))
    for key := range d {
        keys = append(keys, key)
    }
    sort.Ints(keys)
    for _, x := range keys {
        s += d[x]
        ans = max(ans, min(s, cnt[x]+numOperations))
    }

    return
}

function maxFrequency(nums: number[], k: number, numOperations: number): number {
    const cnt: Record<number, number> = {};
    const d: Record<number, number> = {};
    for (const x of nums) {
        cnt[x] = (cnt[x] || 0) + 1;
        d[x] = d[x] || 0;
        d[x - k] = (d[x - k] || 0) + 1;
        d[x + k + 1] = (d[x + k + 1] || 0) - 1;
    }
    let [ans, s] = [0, 0];
    const keys = Object.keys(d)
        .map(Number)
        .sort((a, b) => a - b);
    for (const x of keys) {
        s += d[x];
        ans = Math.max(ans, Math.min(s, (cnt[x] || 0) + numOperations));
    }

    return ans;
}

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

impl Solution {
    pub fn max_frequency(nums: Vec<i32>, k: i32, num_operations: i32) -> i32 {
        let mut cnt = HashMap::new();
        let mut d = BTreeMap::new();

        for &x in &nums {
            *cnt.entry(x).or_insert(0) += 1;
            d.entry(x).or_insert(0);
            *d.entry(x - k).or_insert(0) += 1;
            *d.entry(x + k + 1).or_insert(0) -= 1;
        }

        let mut ans = 0;
        let mut s = 0;
        for (&x, &t) in d.iter() {
            s += t;
            let cur = s.min(cnt.get(&x).copied().unwrap_or(0) + num_operations);
            ans = ans.max(cur);
        }

        ans
    }
}

public class Solution {
    public int MaxFrequency(int[] nums, int k, int numOperations) {
        var cnt = new Dictionary<int, int>();
        var d = new SortedDictionary<int, int>();

        foreach (var x in nums) {
            if (!cnt.ContainsKey(x)) {
                cnt[x] = 0;
            }
            cnt[x]++;

            if (!d.ContainsKey(x)) {
                d[x] = 0;
            }
            if (!d.ContainsKey(x - k)) {
                d[x - k] = 0;
            }
            if (!d.ContainsKey(x + k + 1)) {
                d[x + k + 1] = 0;
            }

            d[x - k] += 1;
            d[x + k + 1] -= 1;
        }

        int ans = 0, s = 0;
        foreach (var kvp in d) {
            int x = kvp.Key, t = kvp.Value;
            s += t;
            int cur = Math.Min(s, (cnt.ContainsKey(x) ? cnt[x] : 0) + numOperations);
            ans = Math.Max(ans, cur);
        }

        return ans;
    }
}

3347. Maximum Frequency of an Element After Performing Operations II

Description

Solutions

Solution 1: Difference Array

Comments