Problem Statement in English

You’re given a 0-indexed array nums consisting of positive integers, a positive integer k and numOperations which is the maximum number of operations you can perform.

You are allowed to add or subtract any number in the range [-k, k] to each element of the array nums. You can perform this operation only once for each element.

Return the maximum possible frequency of an element in the array after performing the operations.

This element is not necessarily an element from nums.

Approach

The approach solves both 3346. Maximum Frequency Of An Element After Performing Operations 1 and 3347. Maximum Frequency Of An Element After Performing Operations 2.

I was lucky enough to come up with this approach almost immediately after reading the problem, although I did botch the implementation the first time around.

The thing we need to do here is kind of figure out a common number that we can convert as many numbers in the array to as possible. I think the diagram I came up with in my head really helped.

If you think about each number in the array being able to be subtracted by k and added by k at the most, it suddenly looks like a range on a number line.

And when you do this with all the numbers in the array, you get a series of overlapping ranges on a number line.

Now the problem boils down to finding the point on the number line where the maximum number of these ranges overlap.

And that’s exactly what the sweep line algorithm is good for.

However, there are a couple things here. What do we do about the numOperations constraint? And how do we implement the sweep line algorithm?

We clearly need to track the number of operations we are performing at each point on the number line. To be precise:

  • When we hit the start of a range (i.e., num - k), we are starting to include that number in our possible conversions, so we increase our current frequency by 1 and increase our operations count by 1.

  • When we hit the actual number before we subtracted or added k, at that spot we don’t need any operation to convert it to itself, so we decrease our operations count by 1, while keeping the number of overlapping elements in that range the same.

  • When we go 1 past the actual number (i.e., num + 1), we are now using an operation to convert that number to something else, so we increase our operations count by 1, while keeping the number of overlapping elements in that range the same.

  • Finally, when we go past the end of the range (i.e., num + k + 1), we are no longer including that number in our possible conversions, so we decrease our current frequency by 1 and decrease our operations count by 1.

This completely captures the operations we are performing at each point on the number line.

Now, we can use this to help us with situations where we’ve exceeded our numOperations limit. If we have x operations at a point and x > numOperations, we can simply reduce our current frequency by x - numOperations to account for the excess operations. Read that again if you didn’t get it the first time.

The next thing to keep in mind is that we should ensure that we’ve applied all necessary operations for a point before actually assessing if it’s the best overlap we’ve come across.

Solution in Python


class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        tracker, res, ops, curr = [], 1, 0, 0

        for n in nums:
            # pos, op, value
            tracker.append((n - k, 1, 1))
            tracker.append((n, -1, 0))
            tracker.append((n + 1, 1, 0))
            tracker.append((n + k + 1, -1, -1))

        tracker.sort()

        for r in range(len(tracker)):
            pos, op, v  = tracker[r]

            curr += v
            ops += op
            adjusted = curr

            if ops > numOperations:
                adjusted -= (ops - numOperations)
            
            if not(r + 1 < len(tracker) and tracker[r + 1][0] == pos):
                res = max(res, adjusted)

        return res

Complexity

  • Time: $O(n \log n)$
    Since we sort the tracker list.

  • Space: $O(n)$
    Since we use a tracker list of size proportional to the input array.

Mistakes I Made

I botched implementations multiple times, but I stayed with this problem for 3 days, and eventually got it right.

And we are done.