⚡Flashcard Drill➔
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

  1. Fix a target value x. Elements already equal to x count for free; elements equal to x - k become x when the chosen subarray covers them.
  2. Inside the chosen subarray, an x becomes x + k and is lost, while an x - k becomes x and is gained, so the net gain of a subarray is count(x - k) - count(x) inside it.
  3. Assign +1 to x - k, -1 to x, and 0 to everything else, then take the maximum subarray sum (Kadane) to get the best gain.
  4. The answer for target x is total(x) + best_gain; maximise over all x in 1..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 k as freely chosen: k is fixed by the input, so the only source value is target - k.
  • Forgetting that existing x inside the subarray are lost: the -1 weight 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.
🎯 Drill This Card Now➔

🧩 Related Greedy Problems