NeetCode #821LC-3434MediumGreedy
← Back to All Problems#821 · #3434 · Maximum Frequency After Subarray Operation(子数组操作后的最大频率)
📌 Problem Statement & Constraints
You are given an integer array
nums and an integer k. Choose one contiguous subarray and add k to every element in it. Return the maximum possible frequency of any single value in the array afterwards. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 50, 1 <= k <= 50.💡 Core Algorithmic Approaches
- Fix a target value
x. Elements already equal toxcount for free; elements equal tox - kbecomexwhen the chosen subarray covers them. - Inside the chosen subarray, an
xbecomesx + kand is lost, while anx - kbecomesxand is gained, so the net gain of a subarray iscount(x - k) - count(x)inside it. - Assign
+1tox - k,-1tox, and0to everything else, then take the maximum subarray sum (Kadane) to get the best gain. - The answer for target
xistotal(x) + best_gain; maximise over allxin1..50.
💻 Benchmark Python3 Implementation
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
from collections import Counter
total = Counter(nums)
ans = max(total.values())
for target in range(1, 51):
source = target - k # only values that become target
if source < 1:
continue
cur = 0
best = 0
for v in nums:
if v == source:
cur += 1
elif v == target:
cur -= 1
if cur < 0:
cur = 0
best = max(best, cur)
ans = max(ans, total[target] + best)
return ans⚡ Complexity Deep Dive
⏱️ Time Complexity
O(50 * n): for each of the 50 candidate targets a single Kadane pass.
💾 Space Complexity
O(1) beyond the frequency counter.
⚠️ Interview Pitfalls & Follow-ups
- Treating
kas freely chosen:kis fixed by the input, so the only source value istarget - k. - Forgetting that existing
xinside the subarray are lost: the-1weight models exactly that, and omitting it overcounts. - Skipping the no-operation baseline:
max(total.values())is the answer when the operation is not worth using. - Allowing a negative subarray sum: Kadane resets to 0, which corresponds to choosing the empty subarray (i.e. no operation).
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.