3640. Maximum Frequency Of An Element After Performing Operations Ii¶

Difficulty: Hard

LeetCode Problem View on GitHub

3640. Maximum Frequency of an Element After Performing Operations II

Hard

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

Solution¶

class Solution {

    static class Pair {
        int first, second;
        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
        @Override
        public String toString() {
            return "(" + first + " " + second + ")";
        }
    }

    static class custom_sort implements Comparator<Pair> {
        @Override
        public int compare(Pair first, Pair second) {
            return Integer.compare(first.first, second.first);
        }
    }

    public int maxFrequency(int[] nums, int k, int numOperations) {
        int n = nums.length;
        HashMap<Integer, Integer> freq = new HashMap<>();
        ArrayList<Pair> res = new ArrayList<>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
            res.add(new Pair(num - k, 1)); res.add(new Pair(num + 1 + k , -1));
        }
        TreeSet<Integer> set = new TreeSet<>();
        for (Pair x : res) 
            set.add(x.first);
        for (int num : freq.keySet()) 
            set.add(num);
        Collections.sort(res, new custom_sort());
        int idx = 0, temp = 0, maxi = 0;
        for (int ele : set) {
            while (idx < res.size() && res.get(idx).first <= ele) {
                temp += res.get(idx).second;
                idx++;
            }
            int cnt = freq.getOrDefault(ele, 0);
            int curr = cnt + Math.min(numOperations, temp - cnt);
            maxi = Math.max(maxi, curr);
        }
        return maxi;
    }
}

Complexity Analysis¶

Time Complexity: O(?)
Space Complexity: O(?)

Approach¶

Detailed explanation of the approach will be added here