LeetCode Problem 3347

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sliding Window, Sorting, Prefix Sum

Solution

LeetCode 3347 - Maximum Frequency of an Element After Performing Operations II

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 an index that has not been used before.
• We may add any integer value in the range [-k, k] to that element.

This means every selected element can be adjusted independently, but only once, and only within a bounded interval.

The goal is to maximize the frequency of some value after all operations are complete. In other words, after modifying up to numOperations distinct elements, we want as many array elements as possible to become equal.

The key observation is that an element nums[i] can become any value in the interval:

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

So instead of thinking about specific operations, we can think about intervals of reachable values.

For a target value x:

• Any element whose interval contains x can be converted into x.
• Existing elements already equal to x require no operation.
• Elements not already equal to x require one operation each.

We want to find the maximum possible number of elements that can simultaneously become the same target value while respecting the operation limit.

The constraints are large:

• nums.length can reach 10^5
• Values can be as large as 10^9

This immediately rules out brute force solutions that try every target value against every element.

Important edge cases include:

• k = 0, where elements cannot change at all
• numOperations = 0, where we can only use existing frequencies
• Large gaps between numbers, where intervals do not overlap
• Arrays where all elements are already equal
• Situations where many elements can reach a target, but the operation budget is too small

These cases are important because they expose incorrect assumptions about convertibility or operation usage.

Approaches

Brute Force Approach

A straightforward idea is to try every possible target value and determine how many elements can become that target.

For every candidate target x:

1. Iterate through all elements.
2. Check whether |nums[i] - x| <= k.
3. Count:

• How many elements are already equal to x
• How many additional elements can be converted into x

4. The achievable frequency becomes:

$$\text{existing} + \min(\text{convertible},\ \text{numOperations})$$

This approach is correct because it directly evaluates every possible target.

However, it is far too slow. There are potentially enormous candidate values, especially because values range up to 10^9. Even restricting targets to existing numbers still leads to an O(n^2) solution.

With n = 10^5, quadratic complexity is infeasible.

Key Insight

Each element defines a reachable interval:

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

If many intervals overlap at some value x, then many elements can be converted into x.

This transforms the problem into an interval overlap problem.

After sorting the array, we can use a sliding window:

• If nums[right] - nums[left] <= 2k, then all elements in that window can potentially become a common value.
• The window size gives the number of potentially compatible elements.
• But only numOperations elements may actually be modified.

Suppose:

• windowSize is the number of elements in the current valid window
• countTarget is the number of elements already equal to the target value

Then the achievable frequency is:

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

We process equal values together and maintain the largest valid window using two pointers.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Try every target against every element
Optimal	O(n log n)	O(1) excluding sort	Sorting plus sliding window

Algorithm Walkthrough

Step 1: Sort the Array

We sort nums so that elements close in value become adjacent.

This is important because if two numbers differ by more than 2k, they can never become the same value.

Sorting allows us to efficiently maintain contiguous valid ranges.

Step 2: Use a Sliding Window

We maintain two pointers:

• left
• right

The window represents elements that can potentially become a common value.

The validity condition is:

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

If the difference exceeds 2k, then no single target can satisfy both endpoints, so we shrink the window from the left.

Step 3: Process Equal Values Together

For each distinct value x:

• Let countX be the number of occurrences of x
• Expand the window so all numbers within 2k distance are included

The window size tells us how many elements could potentially become x.

Step 4: Compute Achievable Frequency

Inside the window:

• countX elements already equal x
• The remaining elements require operations

The number we can convert is limited by numOperations.

So:

$$\text{frequency} = countX + \min(numOperations,\ windowSize - countX)$$

We maximize this over all targets.

Step 5: Return the Maximum

After scanning all distinct values, the maximum computed frequency is the answer.

Why it works

The sliding window guarantees that every element inside the window can reach a common target because the maximum pairwise difference is at most 2k.

For a target value x, every element already equal to x contributes for free. Every other compatible element costs exactly one operation.

Since operations are independent and limited to distinct indices, selecting the best possible compatible elements greedily is always optimal.

Therefore, the formula correctly computes the best achievable frequency for every target.

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()
        freq = Counter(nums)

        n = len(nums)
        left = 0
        answer = 0

        for value in sorted(freq.keys()):
            while nums[left] < value - k:
                left += 1

            right_limit = value + k

            lo, hi = 0, n
            while lo < hi:
                mid = (lo + hi) // 2
                if nums[mid] <= right_limit:
                    lo = mid + 1
                else:
                    hi = mid

            right = lo

            window_size = right - left
            existing = freq[value]

            answer = max(
                answer,
                existing + min(numOperations, window_size - existing)
            )

        return answer

The implementation begins by sorting the array, which enables efficient range processing.

A Counter stores the frequency of every distinct value. This is important because elements already equal to the target do not require operations.

For each distinct target value:

• The left boundary moves until all elements are at least value - k
• Binary search finds the first index greater than value + k

This gives the entire compatible interval.

The window size represents all elements capable of becoming the target value. Some are already equal to the target, while others require operations.

The formula:

existing + min(numOperations, window_size - existing)

correctly limits the number of conversions by the available operation budget.

The algorithm tracks the maximum achievable frequency across all targets.

Go Solution

package main

import (
	"sort"
)

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

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

	n := len(nums)
	left := 0
	answer := 0

	keys := make([]int, 0, len(freq))
	for key := range freq {
		keys = append(keys, key)
	}
	sort.Ints(keys)

	for _, value := range keys {
		for nums[left] < value-k {
			left++
		}

		right := sort.Search(n, func(i int) bool {
			return nums[i] > value+k
		})

		windowSize := right - left
		existing := freq[value]

		candidate := existing
		convertible := windowSize - existing

		if convertible > numOperations {
			candidate += numOperations
		} else {
			candidate += convertible
		}

		if candidate > answer {
			answer = candidate
		}
	}

	return answer
}

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

A map stores frequencies of distinct values. Since Go does not provide a built in Counter, a standard map is used instead.

Binary search uses sort.Search, which returns the first index satisfying the condition. This efficiently computes the right boundary of the compatible range.

All arithmetic safely fits inside Go's int type because constraints are within 32 bit limits, though Go integers are typically 64 bit on modern platforms.

Worked Examples

Example 1

Input:

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

After sorting:

[1,4,5]

Target = 1

Reachable range:

[0,2]

Compatible elements:

Element	Can become 1?
1	Yes
4	No
5	No

Window size = 1

Existing count = 1

Frequency:

1 + min(2, 0) = 1

Target = 4

Reachable range:

[3,5]

Compatible elements:

Element	Can become 4?
1	No
4	Yes
5	Yes

Window size = 2

Existing count = 1

Frequency:

1 + min(2, 1) = 2

Best answer becomes 2.

Target = 5

Reachable range:

[4,6]

Compatible elements:

Element	Can become 5?
1	No
4	Yes
5	Yes

Window size = 2

Existing count = 1

Frequency:

1 + min(2, 1) = 2

Final answer:

2

Example 2

Input:

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

Sorted array:

[5,11,20,20]

Target = 5

Reachable range:

[0,10]

Compatible elements:

Element	Can become 5?
5	Yes
11	No
20	No
20	No

Frequency = 1

Target = 11

Reachable range:

[6,16]

Compatible elements:

Element	Can become 11?
5	No
11	Yes
20	No
20	No

Frequency = 1

Target = 20

Reachable range:

[15,25]

Compatible elements:

Element	Can become 20?
5	No
11	No
20	Yes
20	Yes

Existing count = 2

Frequency:

2 + min(1, 0) = 2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates, binary searches are logarithmic
Space	O(n)	Frequency map stores distinct values

The sorting step requires O(n log n) time. Each distinct value performs one binary search, which costs O(log n). Since there are at most n distinct values, the total complexity remains O(n log n).

The frequency map may contain up to n distinct keys, requiring linear auxiliary space.

Test Cases

from typing import List

s = Solution()

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

assert s.maxFrequency([5,11,20,20], 5, 1) == 2
# existing duplicates already optimal

assert s.maxFrequency([1,2,3], 0, 3) == 1
# k = 0 means no changes possible

assert s.maxFrequency([7,7,7,7], 10, 0) == 4
# already all equal

assert s.maxFrequency([1,10,20], 100, 2) == 3
# large k allows all elements to match

assert s.maxFrequency([1,2,100], 1, 2) == 2
# disconnected groups

assert s.maxFrequency([1], 5, 1) == 1
# single element array

assert s.maxFrequency([1,1,2,2,3,3], 1, 2) == 4
# multiple overlapping intervals

assert s.maxFrequency([1,5,9,13], 4, 1) == 2
# operation limit smaller than compatible set

assert s.maxFrequency([1,2,2,2,10], 3, 1) == 4
# one additional conversion possible

Test	Why
[1,4,5], k=1, ops=2	Basic functionality
[5,11,20,20], k=5, ops=1	Existing duplicates
k=0 case	No modifications allowed
All equal array	Maximum already achieved
Very large k	Entire array compatible
Disconnected intervals	Prevent invalid merges
Single element	Minimum input size
Overlapping intervals	Sliding window correctness
Limited operations	Budget constraint validation
Existing majority group	Incremental improvement

Edge Cases

Case 1: k = 0

When k is zero, elements cannot change at all because the only allowed addition is 0.

A buggy implementation might still try to merge nearby values. However, the interval for each element collapses to a single point.

The implementation handles this naturally because the compatibility condition becomes exact equality.

Case 2: numOperations = 0

If no operations are allowed, the answer must simply be the maximum existing frequency.

An incorrect solution may still attempt conversions.

The formula:

existing + min(0, convertible)

ensures no extra elements are added.

Case 3: Large Gaps Between Values

Consider:

[1, 100, 200]

with small k.

The intervals do not overlap, so no conversions are possible.

A naive sliding window may incorrectly include incompatible elements.

The implementation prevents this by enforcing:

nums[right] - nums[left] <= 2k

which guarantees all elements in the window share at least one common reachable target.

Case 4: Many Compatible Elements but Small Operation Budget

Suppose many elements can reach the target, but only a few operations are allowed.

A buggy implementation might count all compatible elements.

The formula:

existing + min(numOperations, convertible)

correctly caps the number of modified elements by the available operation count.