3434. Maximum Frequency After Subarray Operation
SourceWeekly Contest 434 Q3DifficultyMediumRating2093
Description
You are given an array nums of length n. You are also given an integer k.
You perform the following operation on nums once:
- Select a subarray
nums[i..j]where0 <= i <= j <= n - 1. - Select an integer
xand addxto all the elements innums[i..j].
Find the maximum frequency of the value k after the operation.
Example 1:
Input: nums = [1,2,3,4,5,6], k = 1
Output: 2
Explanation:
After adding -5 to nums[2..5], 1 has a frequency of 2 in [1, 2, -2, -1, 0, 1].
Example 2:
Input: nums = [10,2,3,4,5,5,4,3,2,2], k = 10
Output: 4
Explanation:
After adding 8 to nums[1..9], 10 has a frequency of 4 in [10, 10, 11, 12, 13, 13, 12, 11, 10, 10].
Constraints:
1 <= n == nums.length <= 1051 <= nums[i] <= 501 <= k <= 50
Solutions
Solution 1
Thinking
One operation rewrites a subarray to \(k\); we want the maximum frequency of \(k\) afterwards. \(n\le 10^5\) but values are at most \(50\).
The new frequency is the original count of \(k\) plus how many non-\(k\) cells in the subarray become \(k\). That is a Kadane problem on a \(+1/-1\) encoding.
For each original value \(x\neq k\), run maximum subarray on \(+1\) for \(x\) and \(-1\) for \(k\), then add the global count of \(k\). The tiny alphabet makes \(O(50n)\) acceptable.
1 | |
1 | |
1 | |
1 | |