Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

For a fixed target, only values within k of it can become equal to it. Existing occurrences cost no operation; every other eligible value costs one. Therefore its best frequency is its current count plus as many eligible nonmatches as the operation budget allows.

Approach

Sort nums and build a frequency map. Enumerate every integer target from the smallest input value through the largest. Binary-search the first value at least target - k and the first value greater than target + k. Their index difference is the eligible count.

Subtract the target's existing frequency to find how many new matches could be created, cap that number by numOperations, and add the existing frequency back. Return the largest result. Targets outside the input range cannot improve the answer because moving them toward the nearest endpoint only enlarges their eligible set. Although exactly the specified number of operations is required, any unused operations can add zero to other distinct indices without changing the result.

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        nums.sort()
        fm = defaultdict(int)

        for x in nums:
            fm[x] += 1

        def get_freq(target):
            l = bisect_left(nums, target - k)
            r = bisect_right(nums, target + k)
            ops = r - l - fm[target]
            return fm[target] + min(ops, numOperations)

        res = 0

        for n in range(nums[0], nums[-1] + 1):
            res = max(res, get_freq(n))

        return res

Complexity analysis

Let n = nums.length and R = max(nums) - min(nums) + 1. Time is O((n + R) log(n + 1)) with expected hash-map access, including the singleton case. Python's defaultdict inserts every enumerated target, even when its frequency is zero, so its map grows to R entries and auxiliary space is O(n + R), including sorting workspace. JavaScript's non-inserting lookups retain only original distinct values, giving O(n) auxiliary space including sorting.