3434. Maximum Frequency After Subarray Operation
Medium30.9% acceptance24,712 / 80,014 submissions
Asked by 3 companies
Topics
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
Hints
Hint 1
Fix the element you want to convert to
k.Hint 2
Use prefix sums to optimize counting occurrences of an element.