Longest Target Run After Replacements
Learn this problem
GoogleNEW GRADONSITE INTERVIEWProblem statement
You are given an integer array nums, an integer target, and an integer maxChanges.
You may choose at most maxChanges elements whose value is not target and change each chosen element to target.
Return the maximum possible length of a contiguous subarray that can contain only target after performing at most maxChanges changes. If no non-empty target-only subarray can be formed, return 0.
Original Interview Report
Onsite 1 was an array problem that became harder step by step. Given an original array:
- Given a number
n, return the longest consecutive length wherenappears. - Given a target array such as
[n, m, k], return each target number's longest consecutive occurrence count in the original array. - Given a number
nand an integerk, you may change at mostknumbers inton. Return the longest consecutive length ofnafter the changes.
The third part felt like a sliding-window problem, but the idea was not immediately obvious at first; it was derived from the lower-level reasoning.
Function
longestTargetRunAfterReplacements(nums: int[], target: int, maxChanges: int) → intExamples
Example 1
nums = [1,2,1,1,3,1,2]target = 1maxChanges = 1return = 4Change the 2 at index 1 to 1. Then indices 0 through 3 form a contiguous block of four 1s.
Example 2
nums = [2,2,1,2,3,2,2]target = 2maxChanges = 2return = 7The array contains exactly two values that are not 2. Change both of them to 2, and the whole array becomes one contiguous target run.
Example 3
nums = [4,4,5,4,6,4,4,4]target = 4maxChanges = 1return = 5Change the 6 at index 4 to 4. Then indices 3 through 7 form a contiguous block of five 4s.
Constraints
1 <= nums.length <= 200,000-10^9 <= nums[i], target <= 10^90 <= maxChanges <= nums.length