Sliding Window: Target Containment and Most-Repeated Window
Learn this problem
RobloxFULLTIMEONSITE INTERVIEWProblem statement
You are given an integer array nums, a window size k, and an integer target.
Part 1. Return every length-k contiguous window that contains target at least once.
Part 2. Return the first length-k contiguous window containing the greatest number of occurrences of target. “First” means the smallest start index.
The executable function below implements Part 2 and returns the window itself, not its start index. If k is larger than the array length, return an empty array. If the target never appears, every valid window has count zero, so return the first window.
Function
mostRepeatedWindow(nums: int[], k: int, target: int) → int[]Examples
Example 1
nums = [3, 1, 3, 2, 3, 3, 4, 3]k = 4target = 3return = [3, 2, 3, 3]The windows starting at 2 and 4 each contain three copies of 3. The earlier window, starting at 2, is returned.
Example 2
nums = [3, 1, 1, 3, 1, 1]k = 3target = 3return = [3, 1, 1]Every length-3 window contains one copy of 3, so the first window wins.
Example 3
nums = [1, 2, 4, 5]k = 2target = 3return = [1, 2]The target is absent, so all valid windows tie at zero and the first window is returned.
Example 4
nums = [1, 3]k = 5target = 3return = []No length-5 window exists.
Constraints
1 <= nums.length <= 1000001 <= k- Values in
numsandtargetare 32-bit signed integers. - If
k > nums.length, return an empty array. - On a tie, return the earliest window.