Maximum Count of Target After One Operation

Problem Description

You are given an integer array nums of length n and an integer k.[1][2]

You may perform the following operation on nums exactly once:

1. Select a subarray nums[i..j] where 0 <= i <= j <= n - 1.
2. Select an integer x, and add x to every element in nums[i..j].

Your goal is to determine the maximum possible frequency (count) of the value k in the array after performing this single operation. Since you can choose x = 0, you can effectively decide to leave the array unchanged if no modification improves the count of k.[3]

Note: This is a reconstructed statement of an interview problem often titled “Maximum Count of Target After One Operation”, which corresponds to the LeetCode problem known as “Maximum Frequency After Subarray Operation” and has been reported in FAANG (including Amazon) interviews.[2][1]

Input/Output Format

• Input:

  • nums: an array of integers of length n.
  • k: an integer representing the target value whose frequency you want to maximize.

• Output:

  • Return a single integer:
    • The maximum possible number of occurrences of k in nums after performing the operation once (choosing any subarray and any integer x, possibly x = 0).[1][2]

• Typical function signature examples:

  • C++: int maxFrequencyAfterOperation(vector<int>& nums, int k);
  • Java: int maxFrequencyAfterOperation(int[] nums, int k);
  • Python: def maxFrequencyAfterOperation(nums: List[int], k: int) -> int:

Examples

Example 1

Input

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

Output

text 2

Explanation

• The initial array is [1, 2, 3, 4, 5, 6].
  Currently, the value 1 appears once (at index 0).[2][1]
• Choose the subarray nums[2..5] = [3, 4, 5, 6].
• Choose x = -5 and add it to each element in this subarray:
  • 3 + (-5) = -2
  • 4 + (-5) = -1
  • 5 + (-5) = 0
  • 6 + (-5) = 1
• The array becomes [1, 2, -2, -1, 0, 1].
• Now the value 1 appears twice (at indices 0 and 5).
• No other choice of subarray and x can increase the frequency of 1 beyond 2, so the answer is 2.[1][2]

Example 2

Input

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

Output

text 4

Explanation

• Initially, 10 appears once (at index 0).[2][1]
• Choose the subarray nums[1..9] = [2, 3, 4, 5, 5, 4, 3, 2, 2].
• Choose x = 8 and add it to each element in this subarray:
  • 2 + 8 = 10
  • 3 + 8 = 11
  • 4 + 8 = 12
  • 5 + 8 = 13
  • 5 + 8 = 13
  • 4 + 8 = 12
  • 3 + 8 = 11
  • 2 + 8 = 10
  • 2 + 8 = 10
• The array becomes [10, 10, 11, 12, 13, 13, 12, 11, 10, 10].
• Now 10 appears four times (indices 0, 1, 8, and 9).
• This is the maximum possible frequency of 10 after one operation, so the answer is 4.[1][2]

Constraints

• 1 <= n == nums.length <= 100000 (i.e., n up to 10^5).[2]
• 1 <= nums[i] <= 50 for all 0 <= i < n.[2]
• 1 <= k <= 50.[2]

Performance expectations (to pass typical constraints):

• Time complexity: Approximately $$O(n \cdot V)$$, where $$V$$ is the number of distinct values in nums (at most 50), which is effectively linear in n.[3]
• Auxiliary space: $$O(1)$$ or $$O(V)$$ beyond the input array.[3]

Solution Hint

Think of the operation as picking a subarray and “turning” all occurrences of some value t inside that subarray into k, while any existing k in that subarray will be shifted away from k and thus lost. For each possible candidate value t, use a greedy Kadane-style / sliding-window pass over nums to find the subarray where converting t to k yields the maximum net gain (#t gained − #k lost), then add this best gain to the original count of k and take the maximum over all t.[4][3]