LeetCode Problem 3434

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Dynamic Programming, Greedy, Enumeration, Prefix Sum

Solution

LeetCode 3434 - Maximum Frequency After Subarray Operation

Problem Understanding

We are given an array nums and a target value k.

We must perform exactly one operation:

1. Choose a contiguous subarray nums[i..j].
2. Choose an integer x.
3. Add x to every element inside that subarray.

After performing this operation, some elements may become equal to k, some existing occurrences of k may remain unchanged, and some existing occurrences of k inside the modified subarray may stop being equal to k.

Our goal is to maximize the number of elements equal to k in the final array.

The key observation is that a single operation uses one value of x for the entire chosen subarray. Therefore, every element that becomes k inside the chosen subarray must originally have had the same value.

Suppose we choose a value v. If we set:

$$x = k - v$$

then every occurrence of v inside the selected subarray becomes k.

However, if x ≠ 0, every existing occurrence of k inside that same subarray gets changed to something else and is lost.

The constraints are:

• n ≤ 100000
• nums[i] ≤ 50
• k ≤ 50

The array length is large, but the value range is very small. This strongly suggests that we should exploit the fact that there are only 50 possible values.

Important edge cases include arrays that already contain many occurrences of k, arrays with no occurrences of k, arrays consisting entirely of one value, and cases where converting one value to k would also destroy existing occurrences of k inside the chosen segment.

Approaches

Brute Force

A brute-force solution would enumerate:

• every possible subarray,
• every possible value of x,
• apply the operation,
• count the resulting frequency of k.

There are O(n²) subarrays. Even if we restricted possible values of x, recomputing frequencies would still be expensive.

This quickly becomes infeasible for n = 100000.

The brute-force approach is correct because it checks every possible operation, but its running time is far beyond the allowed limits.

Key Insight

Suppose we decide that value v will be transformed into k.

Then:

$$x = k - v$$

is fixed.

Inside the chosen subarray:

• Every occurrence of v contributes +1 to the frequency of k.
• Every occurrence of k contributes -1 because it gets changed away from k.
• All other values contribute 0.

Therefore, for a fixed value v, each position contributes:

• +1 if nums[i] = v
• -1 if nums[i] = k
• 0 otherwise

The problem becomes finding a subarray with maximum total contribution.

That is exactly the maximum subarray sum problem, which can be solved using Kadane's algorithm.

If:

• base = original frequency of k
• gain(v) = maximum subarray sum for value v

then:

$$\text{answer} = \text{base} + \max_v \text{gain}(v)$$

Since values are only from 1 to 50, we can try every possible value v ≠ k.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³) or worse	O(1)	Enumerates subarrays and operations
Optimal	O(50·n)	O(1)	Kadane's algorithm for each possible value

Algorithm Walkthrough

1. Count existing occurrences of k

Let:

base = number of elements equal to k

These occurrences already contribute to the final answer.

2. Consider each possible value v

Because all numbers are between 1 and 50, iterate through every value:

v = 1..50

excluding k.

For this value, we imagine choosing:

$$x = k - v$$

so that every v becomes k.

3. Build the contribution stream implicitly

For each array position:

• +1 if element equals v
• -1 if element equals k
• 0 otherwise

We do not need to store this array explicitly.

4. Run Kadane's algorithm

Maintain:

current_gain
best_gain

For each element:

current_gain = max(score, current_gain + score)
best_gain = max(best_gain, current_gain)

This finds the subarray that maximizes:

(# of v inside subarray)
-
(# of k inside subarray)

which is exactly the net increase in the frequency of k.

5. Update the global answer

For each value v:

answer = max(answer, base + best_gain)

6. Return the answer

After checking all possible values, return the maximum result found.

Why it works

For a fixed value v, the operation must use x = k - v. Every occurrence of v inside the chosen subarray becomes k, while every occurrence of k inside that subarray is lost. Therefore the net change equals:

$$(\text{count of } v) - (\text{count of } k)$$

inside the chosen subarray.

Kadane's algorithm finds the subarray maximizing exactly this quantity. Since every valid operation corresponds to choosing some value v, checking all possible values guarantees that the best operation is found.

Python Solution

from typing import List

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        base = sum(1 for x in nums if x == k)
        answer = base

        for v in range(1, 51):
            if v == k:
                continue

            current_gain = 0
            best_gain = 0

            for num in nums:
                if num == v:
                    score = 1
                elif num == k:
                    score = -1
                else:
                    score = 0

                current_gain = max(score, current_gain + score)
                best_gain = max(best_gain, current_gain)

            answer = max(answer, base + best_gain)

        return answer

Implementation Explanation

The variable base stores the number of occurrences of k already present in the array.

For every possible value v, we treat occurrences of v as a gain of +1 because they can be converted into k. Existing occurrences of k are treated as -1 because they would be destroyed if they lie inside the chosen subarray. All other values contribute nothing.

Kadane's algorithm is then applied directly while scanning the array. The variable current_gain represents the best gain ending at the current position, and best_gain stores the best gain seen anywhere.

After processing one candidate value v, we add the gain to the original frequency and update the global answer.

Because there are only 50 possible values, repeating this process for every value remains efficient.

Go Solution

func maxFrequency(nums []int, k int) int {
	base := 0
	for _, num := range nums {
		if num == k {
			base++
		}
	}

	answer := base

	for v := 1; v <= 50; v++ {
		if v == k {
			continue
		}

		currentGain := 0
		bestGain := 0

		for _, num := range nums {
			score := 0

			if num == v {
				score = 1
			} else if num == k {
				score = -1
			}

			if currentGain+score > score {
				currentGain = currentGain + score
			} else {
				currentGain = score
			}

			if currentGain > bestGain {
				bestGain = currentGain
			}
		}

		if base+bestGain > answer {
			answer = base + bestGain
		}
	}

	return answer
}

Go-Specific Notes

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

Since all values are small and the maximum answer is at most n, integer overflow is not a concern. Go slices are traversed directly using range, and Kadane's algorithm is implemented using ordinary integer variables without requiring any additional memory.

Worked Examples

Example 1

nums = [1,2,3,4,5,6]
k = 1

Initial frequency:

base = 1

Consider v = 6.

Contribution array:

Value	Score
1	-1
2	0
3	0
4	0
5	0
6	+1

Kadane progression:

Position	Score	Current Gain	Best Gain
0	-1	-1	0
1	0	0	0
2	0	0	0
3	0	0	0
4	0	0	0
5	1	1	1

Result:

base + best_gain
= 1 + 1
= 2

No other value produces a larger gain.

Answer:

2

Example 2

nums = [10,2,3,4,5,5,4,3,2,2]
k = 10

Initial frequency:

base = 1

Consider:

v = 2

Contribution array:

Value	Score
10	-1
2	+1
3	0
4	0
5	0
5	0
4	0
3	0
2	+1
2	+1

Kadane progression:

Position	Score	Current Gain	Best Gain
0	-1	-1	0
1	1	1	1
2	0	1	1
3	0	1	1
4	0	1	1
5	0	1	1
6	0	1	1
7	0	1	1
8	1	2	2
9	1	3	3

Thus:

best_gain = 3
answer = 1 + 3 = 4

Answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(50n)	Run Kadane once for each possible value
Space	O(1)	Only a few variables are maintained

Since the value range is fixed at 50, O(50n) is effectively linear in the size of the array. For n = 100000, this results in about five million simple operations, which is easily fast enough.

Test Cases

s = Solution()

assert s.maxFrequency([1,2,3,4,5,6], 1) == 2  # example 1
assert s.maxFrequency([10,2,3,4,5,5,4,3,2,2], 10) == 4  # example 2

assert s.maxFrequency([1], 1) == 1  # single element already k
assert s.maxFrequency([2], 1) == 1  # single element converted to k

assert s.maxFrequency([1,1,1,1], 1) == 4  # all already k
assert s.maxFrequency([2,2,2,2], 1) == 4  # convert entire array

assert s.maxFrequency([1,2,1,2,1], 1) == 4  # must avoid losing too many k's
assert s.maxFrequency([2,1,2,1,2], 1) == 3  # best subarray is selective

assert s.maxFrequency([3,3,3,1,1], 1) == 5  # convert all 3's

assert s.maxFrequency([1,2,2,2,1], 1) == 5  # middle segment conversion

assert s.maxFrequency([2,3,4,5], 1) == 1  # no existing k

assert s.maxFrequency([50] * 1000, 1) == 1000  # large identical array

Test Summary

Test	Why
[1,2,3,4,5,6], k=1	Official example
[10,2,3,4,5,5,4,3,2,2], k=10	Official example
[1], k=1	Smallest valid input
[2], k=1	Single conversion
[1,1,1,1], k=1	Already optimal
[2,2,2,2], k=1	Convert whole array
[1,2,1,2,1], k=1	Existing k values inside candidate segment
[2,1,2,1,2], k=1	Multiple competing segments
[3,3,3,1,1], k=1	Large positive gain
[1,2,2,2,1], k=1	Interior subarray optimal
[2,3,4,5], k=1	No initial k values
Large repeated array	Stress test for performance

Edge Cases

Array Already Consists Entirely of k

Consider:

nums = [5,5,5,5]
k = 5

Any nonzero operation would destroy some existing occurrences of k. The optimal choice yields no improvement, and the answer remains 4.

The implementation handles this naturally because every candidate value produces a maximum gain of 0, leaving the answer equal to the original frequency.

No Occurrence of k Exists Initially

Consider:

nums = [2,2,2,2]
k = 1

The initial frequency is zero. Choosing v = 2 gives a gain of four, so the entire array can be converted to k.

The algorithm correctly computes base = 0 and finds a maximum subarray gain of 4.

Existing k Values Inside the Chosen Segment

Consider:

nums = [1,2,2,1,2]
k = 1

A common mistake is to count every converted 2 as a gain without accounting for the fact that any 1 inside the selected subarray is destroyed.

The contribution model assigns +1 to 2 and -1 to 1, ensuring that both effects are accounted for simultaneously. Kadane's algorithm then finds the segment with the true net benefit.

Multiple Candidate Values

Consider:

nums = [2,2,3,3,3]
k = 1

A single operation can only use one value of x, so we cannot simultaneously convert both 2 and 3 into 1.

The algorithm explicitly evaluates each candidate value separately and takes the best result, which correctly models the constraint that only one shift value may be used.