Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

An optimal target either already occurs in the array or must be created entirely through operations. Existing targets gain free occurrences. For a new target, a group can all reach one value exactly when its minimum and maximum differ by at most 2 * k, because their reachable intervals then intersect.

Approach

Sort the array. First consider each existing value x as the target. Move two pointers to maintain the values in [x - k, x + k], updating their frequency map. Add the existing count of x to the smaller of the operation budget and the number of eligible nonmatches.

Next slide a window whose maximum minus minimum is at most 2 * k. Such a window shares a reachable integer target; count at most numOperations of its elements, since this pass assumes every chosen element may need an operation. This is feasible even if that target happens to exist already, because adding zero is allowed.

Take the best result from both passes. Every absent-target solution is covered by the second pass, and the first captures the extra advantage of existing occurrences.

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        nums.sort()
        n = len(nums)
        res = 0

        # target in the array
        m = defaultdict(int)
        l = 0
        r = 0
        for x in nums:
            while r < n and nums[r] <= x + k:
                m[nums[r]] += 1
                r += 1
            while l < n and nums[l] < x - k:
                m[nums[l]] -= 1
                l += 1
            mx_ops = r - l - m[x]
            res = max(res, min(mx_ops, numOperations) + m[x])

        # target not in arr
        l = 0
        for r in range(n):
            while l < n and nums[l] + (k * 2) < nums[r]:
                l += 1
            mx_ops = r - l + 1
            res = max(res, min(mx_ops, numOperations))

        return res

Complexity analysis

Let n = nums.length. Time: O(n log n). Auxiliary space: O(n) for sorting and the frequency map.