LeetCode 3346 - Maximum Frequency of an Element After Performing Operations I

LeetCode Problem 3346

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sliding Window, Sorting, Prefix Sum

Solution

Problem Understanding

The problem gives us an integer array nums, along with two integers, k and numOperations.

We are allowed to perform exactly numOperations operations. In each operation, we must choose a unique index that has not been used before, and modify that element by adding any integer value in the range [-k, k].

This means each selected element can be changed independently to any value within:

$$[\text{nums}[i] - k,\ \text{nums}[i] + k]$$

Our goal is to maximize the frequency of some value after all operations are completed. In other words, we want as many elements as possible to become equal.

An important detail is that each index can be selected at most once. Since each operation targets a distinct index, an element can only be modified one time.

The constraints are large:

• nums.length can be up to 10^5
• Values can also be up to 10^5

These limits immediately rule out any quadratic solution. We need something close to O(n log n).

The key observation is that an element can become a target value x if:

$$|nums[i] - x| \le k$$

This transforms the problem into an interval overlap problem. Each element contributes an interval of reachable values, and we want to find a value that can be reached by the largest number of elements, while respecting the limit of numOperations.

There are several important edge cases:

• k = 0, meaning no value can actually change
• numOperations = 0, meaning we cannot modify anything
• Multiple values already equal
• All values very far apart
• Large groups where only some elements need modification
• Cases where the best target value does not initially exist in the array

The problem guarantees valid input sizes and non-negative operation counts, so we do not need to handle malformed data.

Approaches

Brute Force Approach

A brute force strategy would try every possible target value and determine how many elements could become that value.

For a target value x, we would count:

• Elements already equal to x
• Elements where |nums[i] - x| <= k, since they can be converted into x

However, only numOperations elements can actually be modified, so if many elements are convertible, we can only use at most numOperations of them unless they are already equal to x.

If we tried every possible target value across the entire value range, the complexity would become extremely large. The value range itself can reach about 2 * 10^5, and for each target we might scan the whole array.

That leads to roughly:

$$O(V \cdot n)$$

which is too slow for n = 10^5.

Key Insight

Instead of testing every target independently, we sort the array and use a sliding window.

Suppose we want all numbers inside a window to become equal to some value x.

A number nums[i] can become x if:

$$x \in [nums[i] - k,\ nums[i] + k]$$

For multiple elements to all become the same value, their reachable intervals must overlap.

For a sorted window from left to right, the intersection exists if:

$$nums[right] - nums[left] \le 2k$$

Why?

Because:

• The leftmost value can increase by at most k
• The rightmost value can decrease by at most k

So they can meet only if their distance is at most 2k.

Now suppose a valid window has size windowSize.

Some elements may already equal the target value, while the rest require operations.

If a target value appears freq times naturally inside the window, then we need:

$$windowSize - freq$$

operations to convert the remaining elements.

Since we only have numOperations operations, the achievable frequency becomes:

$$freq + \min(numOperations,\ windowSize - freq)$$

The optimal solution uses sorting, binary search boundaries, and frequency counting.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(V * n)	O(1)	Try every target value and scan all elements
Optimal	O(n log n)	O(n)	Sorting plus sliding window and frequency counting

Algorithm Walkthrough

1. Sort the array.

Sorting allows us to efficiently examine contiguous ranges of values. Since reachable intervals depend on numeric distance, sorting makes sliding window techniques possible. 2. Build a frequency map.

We count how many times each value already appears in the array. This helps determine how many elements already equal a candidate target. 3. Use a sliding window.

Maintain two pointers, left and right.

The window represents elements that could potentially all become the same value. 4. Expand the right pointer.

For each new element at right, check whether the window remains valid.

The condition is:

$$nums[right] - nums[left] \le 2k$$

If this condition fails, move left forward until the window becomes valid again. 5. Compute the window size.

The number of elements currently inside the window is:

$$right - left + 1$$ 6. Choose a target value.

The best target inside the current window is usually one of the existing values.

Let the target be nums[right].

Suppose this target already appears freq[target] times in the array. 7. Compute required operations.

Some elements already equal the target, while others need modification.

The number needing modification is:

$$windowSize - freq[target]$$ 8. Respect the operation limit.

We can modify at most numOperations elements.

Therefore the achievable frequency is:

$$freq[target] + \min(numOperations,\ windowSize - freq[target])$$ 9. Update the answer.

Track the maximum achievable frequency across all windows.

Why it works

The sliding window guarantees that every pair of values inside the window differs by at most 2k, which means all elements in the window can be converted to some common value.

Sorting ensures that if the extreme values satisfy the condition, all middle values also satisfy it.

By counting how many elements already equal the chosen target, we minimize the number of required operations. Since every modification costs exactly one operation and each index can only be modified once, limiting conversions to numOperations produces the optimal achievable frequency.

Python Solution

from typing import List
from collections import Counter

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

        left = 0
        answer = 0

        for right in range(len(nums)):
            while nums[right] - nums[left] > 2 * k:
                left += 1

            window_size = right - left + 1
            target = nums[right]

            existing = frequency[target]

            achievable = min(
                window_size,
                existing + numOperations
            )

            answer = max(answer, achievable)

        return answer

The implementation begins by sorting the array. This enables the sliding window condition based on numeric distance.

A Counter stores the total occurrences of every value. This is important because some elements already equal the chosen target value and therefore do not require operations.

The sliding window maintains a valid range where all values differ by at most 2 * k. Whenever the condition breaks, the left pointer moves forward until the window becomes valid again.

For each valid window, the algorithm treats nums[right] as the target value. The total achievable frequency is limited by two things:

• The total number of elements inside the window
• The number of elements we can convert using available operations

Since existing elements already equal the target, we can add at most numOperations more converted elements.

The maximum across all windows is returned.

Go Solution

package main

import (
	"sort"
)

func maxFrequency(nums []int, k int, numOperations int) int {
	sort.Ints(nums)

	frequency := make(map[int]int)
	for _, num := range nums {
		frequency[num]++
	}

	left := 0
	answer := 0

	for right := 0; right < len(nums); right++ {
		for nums[right]-nums[left] > 2*k {
			left++
		}

		windowSize := right - left + 1
		target := nums[right]

		existing := frequency[target]

		achievable := existing + numOperations
		if achievable > windowSize {
			achievable = windowSize
		}

		if achievable > answer {
			answer = achievable
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

A map[int]int is used instead of Python's Counter. The array is sorted using sort.Ints.

Go slices naturally handle dynamic indexing, so no special handling is required for empty arrays because the constraints guarantee at least one element.

All arithmetic safely fits within Go's int range because the values are bounded by 10^5.

Worked Examples

Example 1

Input:

nums = [1,4,5]
k = 1
numOperations = 2

After sorting:

[1,4,5]

Frequency map:

1 -> 1
4 -> 1
5 -> 1

Step	left	right	Window	Valid?	Window Size	Target	Achievable
1	0	0	[1]	Yes	1	1	1
2	0	1	[1,4]	No, diff=3 > 2	shrink	-	-
3	1	1	[4]	Yes	1	4	1
4	1	2	[4,5]	Yes	2	5	2

For the final window:

• 5 already exists once
• 4 can become 5
• only one operation required

Answer:

2

Example 2

Input:

nums = [5,11,20,20]
k = 5
numOperations = 1

After sorting:

[5,11,20,20]

Frequency map:

5 -> 1
11 -> 1
20 -> 2

Step	left	right	Window	Valid?	Window Size	Target	Achievable
1	0	0	[5]	Yes	1	5	1
2	0	1	[5,11]	Yes	2	11	2
3	0	2	[5,11,20]	No	shrink	-	-
4	1	2	[11,20]	Yes	2	20	2
5	1	3	[11,20,20]	Yes	3	20	3

For the final window:

• two elements already equal 20
• one additional element can become 20
• only one operation needed

Answer:

3

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(n)	Frequency map stores counts of values

The sliding window itself runs in linear time because each pointer moves at most n times.

Sorting requires O(n log n), which dominates the total complexity.

The frequency map may store up to n distinct values, leading to O(n) auxiliary space.

Test Cases

from typing import List

class Solution:
    def maxFrequency(self, nums: List[int], k: int, numOperations: int) -> int:
        from collections import Counter

        nums.sort()
        frequency = Counter(nums)

        left = 0
        answer = 0

        for right in range(len(nums)):
            while nums[right] - nums[left] > 2 * k:
                left += 1

            window_size = right - left + 1
            target = nums[right]

            existing = frequency[target]

            achievable = min(
                window_size,
                existing + numOperations
            )

            answer = max(answer, achievable)

        return answer

sol = Solution()

assert sol.maxFrequency([1,4,5], 1, 2) == 2
# basic example from statement

assert sol.maxFrequency([5,11,20,20], 5, 1) == 3
# convert one extra value into existing duplicates

assert sol.maxFrequency([1,1,1], 0, 0) == 3
# already all equal

assert sol.maxFrequency([1,10,20], 0, 2) == 1
# no changes allowed because k=0

assert sol.maxFrequency([1,2,3,4], 10, 4) == 4
# all values can become equal

assert sol.maxFrequency([1], 100, 1) == 1
# single element array

assert sol.maxFrequency([1,2,2,3], 1, 1) == 3
# extend an existing group

assert sol.maxFrequency([1,100,200], 10, 2) == 1
# values too far apart

assert sol.maxFrequency([3,3,6,6,9], 3, 2) == 4
# multiple overlapping ranges

assert sol.maxFrequency([1,5,5,5,9], 4, 1) == 4
# only one extra conversion possible

Test	Why
[1,4,5], k=1, ops=2	Basic example from statement
[5,11,20,20], k=5, ops=1	Existing duplicates plus one conversion
[1,1,1], k=0, ops=0	Already uniform array
[1,10,20], k=0, ops=2	No value changes possible
[1,2,3,4], k=10, ops=4	Every value convertible
[1], k=100, ops=1	Minimum array size
[1,2,2,3], k=1, ops=1	Expand existing frequency
[1,100,200], k=10, ops=2	No overlapping intervals
[3,3,6,6,9], k=3, ops=2	Multiple possible target groups
[1,5,5,5,9], k=4, ops=1	Operation limit becomes bottleneck

Edge Cases

One important edge case occurs when k = 0. In this scenario, elements cannot actually change value because the allowed modification range is only [0, 0]. A buggy implementation might still assume nearby values can merge together. The sliding window condition naturally prevents this because the allowed difference becomes zero, so only identical values remain in the same window.

Another critical edge case is when numOperations = 0. Even if many values could theoretically become equal, no modifications are allowed. The formula:

$$existing + numOperations$$

correctly reduces to just the count of already existing target values.

A third tricky case happens when values are extremely far apart. For example:

[1, 100, 200]

with small k.

A naive solution might incorrectly group distant values together. The sliding window validity condition:

$$nums[right] - nums[left] \le 2k$$

guarantees that only mutually reachable values remain in the same candidate group.

Another subtle case involves large existing duplicate groups. Suppose the target value already appears many times. Those elements require no operations, so the algorithm correctly counts them separately using the frequency map. This prevents wasting operations on values already equal to the target.