Problem Description

You have an integer array nums and two integer parameters: k and numOperations.

You need to perform exactly numOperations operations on the array. In each operation:

• Choose an index i that hasn't been selected in any previous operation (each index can only be modified once)
• Add any integer value between -k and k (inclusive) to nums[i]

After performing all operations, you want to maximize the frequency of any element in the modified array. The frequency of an element is the number of times it appears in the array.

Your task is to return the maximum possible frequency that any single element can achieve after performing all the operations optimally.

For example, if you have nums = [1, 2, 3], k = 1, and numOperations = 2, you could:

• Add 1 to nums[0] to make it 2
• Add -1 to nums[2] to make it 2
• This would give you [2, 2, 2] with a maximum frequency of 3

The key insight is that by adding values in the range [-k, k], you can potentially transform different elements to become equal, thereby increasing the frequency of a particular value. You need to strategically choose which elements to modify and what values to add to achieve the highest possible frequency for any element.

Intuition

The key observation is that for any target value x, we can transform elements to become x if they fall within the range [x - k, x + k]. This is because we can add any value from [-k, k] to an element.

Think about it this way: if we want to maximize the frequency of some value x, we have two types of elements to consider:

1. Elements that are already equal to x (they contribute to the frequency without using any operations)
2. Elements that can be transformed to x by adding a value in [-k, k] (these require operations)

For each potential target value x, the maximum frequency we can achieve is the sum of:

• Elements already equal to x (free contributions)
• Up to numOperations elements from the range [x - k, x + k] that we can transform to x

This leads us to think about counting, for each possible target value, how many elements fall within its "reachable range" [x - k, x + k].

The challenge is efficiently computing this for all possible target values. We can use a sweep line technique with difference arrays. For each element nums[i], it can be transformed to any value in the range [nums[i] - k, nums[i] + k]. So nums[i] contributes to the potential frequency of all values in this range.

By marking range boundaries using a difference array (d[x - k] += 1 and d[x + k + 1] -= 1), we can efficiently compute how many elements can reach each target value. As we sweep through sorted positions, we maintain a running sum s that tells us how many elements can be transformed to the current position.

The final answer for each position x is min(s, cnt[x] + numOperations) because:

• s is the total number of elements that can reach x
• But we can only modify numOperations elements
• Elements already at x (counted in cnt[x]) don't need operations

Learn more about Binary Search, Prefix Sum, Sorting and Sliding Window patterns.

Solution Approach

The solution uses a sweep line algorithm with a difference array to efficiently count how many elements can reach each potential target value.

Step 1: Initialize Data Structures

• cnt: A dictionary to store the frequency of each original element in nums
• d: A difference array to mark range boundaries for sweep line processing

Step 2: Process Each Element For each element x in nums:

• cnt[x] += 1: Count the original frequency of x
• d[x] += 0: Ensure x exists as a key in the difference array (for elements already at this value)
• d[x - k] += 1: Mark the start of the range where x can contribute (elements can be transformed from x to any value in [x - k, x + k])
• d[x + k + 1] -= 1: Mark the end of the range (exclusive) using difference array technique

Step 3: Sweep Line Processing Sort the difference array by keys and process each position:

• s += t: Maintain a running sum that represents how many elements can be transformed to the current position x
• For each position x, calculate the maximum achievable frequency:
  • Total elements that can reach x: s
  • Elements already at x that don't need operations: cnt[x]
  • Maximum frequency: min(s, cnt[x] + numOperations)

The min operation is crucial because:

• If s <= cnt[x] + numOperations: All s elements can contribute to the frequency
• If s > cnt[x] + numOperations: We're limited by the number of operations, so we take cnt[x] (free) plus numOperations (maximum we can transform)

Step 4: Return Maximum Track and return the maximum frequency found across all positions.

Time Complexity: O(n log n) due to sorting the difference array Space Complexity: O(n) for storing the dictionaries

The elegance of this solution lies in using the difference array to avoid explicitly checking ranges for each potential target, reducing what could be an O(n²) operation to O(n log n).

Example Walkthrough

Let's walk through a concrete example with nums = [1, 4, 5], k = 2, and numOperations = 2.

Step 1: Initialize Data Structures

• cnt = {} (frequency counter)
• d = {} (difference array for sweep line)

Step 2: Process Each Element

For element 1:

• cnt[1] = 1 (one occurrence of 1)
• d[1] = 0 (ensure key exists)
• d[1-2] = d[-1] = 1 (start of range where 1 can contribute)
• d[1+2+1] = d[4] = -1 (end of range, exclusive)
• Element 1 can be transformed to any value in [-1, 3]

For element 4:

• cnt[4] = 1 (one occurrence of 4)
• d[4] = 0 (ensure key exists, now d[4] = -1 + 0 = -1)
• d[4-2] = d[2] = 1 (start of range)
• d[4+2+1] = d[7] = -1 (end of range)
• Element 4 can be transformed to any value in [2, 6]

For element 5:

• cnt[5] = 1 (one occurrence of 5)
• d[5] = 0 (ensure key exists)
• d[5-2] = d[3] = 1 (start of range)
• d[5+2+1] = d[8] = -1 (end of range)
• Element 5 can be transformed to any value in [3, 7]

Current state:

• cnt = {1: 1, 4: 1, 5: 1}
• d = {-1: 1, 1: 0, 2: 1, 3: 1, 4: -1, 5: 0, 7: -1, 8: -1}

Step 3: Sweep Line Processing

Sort keys of d: [-1, 1, 2, 3, 4, 5, 7, 8]

Process each position with running sum s:

Step 4: Return Maximum

The maximum frequency achieved is 2, which occurs at positions 2, 3, 4, and 5.

For example, at position 3:

• All three elements (1, 4, 5) can reach value 3
• Element 1 can add +2 to become 3
• Element 4 can add -1 to become 3
• Element 5 can add -2 to become 3
• But we can only perform 2 operations, so maximum frequency is 2

We could transform the array to [1, 3, 3] by modifying elements at indices 1 and 2, achieving a frequency of 2 for the value 3.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n) where n is the length of the input array nums.

• Iterating through nums to populate cnt and d dictionaries takes O(n) time
• Each element in nums creates at most 3 entries in dictionary d (at positions x, x-k, and x+k+1), so d has at most O(n) entries
• Sorting the items in dictionary d takes O(n log n) time since there are O(n) unique keys
• The final iteration through sorted items takes O(n) time
• Overall time complexity is dominated by the sorting step: O(n log n)

Space Complexity: O(n) where n is the length of the input array nums.

• Dictionary cnt stores at most n unique elements from nums, requiring O(n) space
• Dictionary d stores at most 3n entries (3 entries per element in nums), which is O(n) space
• The sorted items list created from d.items() requires O(n) space
• Additional variables (ans, s, x, t) use O(1) space
• Overall space complexity is O(n)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Misunderstanding Range Boundaries

The Problem: A common mistake is incorrectly setting up the difference array boundaries. Developers often confuse:

• Whether to use num - k or num + k as the start of the range
• Whether the end boundary should be num + k or num + k + 1

Why This Happens: The confusion arises from mixing up two different perspectives:

1. "What values can I change num into?" (Answer: [num - k, num + k])
2. "What values can be changed to reach position x?" (Answer: values in [x - k, x + k])

Incorrect Implementation:

# WRONG: Confusing the direction of transformation
range_contributions[num + k] += 1  # Wrong start
range_contributions[num - k + 1] -= 1  # Wrong end

Correct Solution:

# RIGHT: For each num, mark where it can contribute as a target
range_contributions[num - k] += 1      # Start of range
range_contributions[num + k + 1] -= 1  # End of range (exclusive)

Pitfall 2: Forgetting to Initialize Position Keys

The Problem: Failing to ensure that each original number's position exists in the difference array, leading to missed counting opportunities.

Why This Happens: The difference array only creates entries where boundaries exist. If a number doesn't serve as a boundary for any range, it won't appear in the sorted iteration.

Incorrect Implementation:

# WRONG: Not initializing positions
for num in nums:
    frequency_count[num] += 1
    # Missing: range_contributions[num] += 0
    range_contributions[num - k] += 1
    range_contributions[num + k + 1] -= 1

Correct Solution:

# RIGHT: Ensure every original number position is considered
for num in nums:
    frequency_count[num] += 1
    range_contributions[num] += 0  # Important: Initialize position
    range_contributions[num - k] += 1
    range_contributions[num + k + 1] -= 1

Pitfall 3: Incorrect Maximum Frequency Calculation

The Problem: Misunderstanding how to combine the original frequency with the number of operations available.

Common Mistakes:

# WRONG 1: Always adding numOperations
max_frequency = frequency_count[position] + numOperations

# WRONG 2: Not considering original frequency
max_frequency = min(current_sum, numOperations)

# WRONG 3: Taking maximum instead of minimum
max_frequency = max(current_sum, frequency_count[position] + numOperations)

Correct Solution:

# RIGHT: Take minimum of available transformations and operation budget
max_frequency = max(
    max_frequency,
    min(current_sum, frequency_count[position] + numOperations)
)

The logic is:

• current_sum: Total elements that could potentially reach this position
• frequency_count[position] + numOperations: Maximum we can actually achieve (original + transformed)
• We take the minimum because we're constrained by either the available elements or our operation budget

Pitfall 4: Off-by-One Error in Difference Array

The Problem: Using inclusive end boundary instead of exclusive, causing incorrect counting.

Incorrect Implementation:

# WRONG: Using inclusive boundary
range_contributions[num + k] -= 1  # Should be num + k + 1

This would exclude position num + k from the range, even though we can transform num to num + k.

Correct Solution:

# RIGHT: Use exclusive end boundary
range_contributions[num + k + 1] -= 1

This ensures the range [num - k, num + k] is fully included in the sweep line calculation.