You are given a 0-indexed integer array nums of size n, and a 0-indexed integer array pattern of size m consisting of integers -1, 0, and 1.
A subarray nums[i..j] of size m + 1 is said to match the pattern if the following conditions hold for each element pattern[k]:
nums[i + k + 1] > nums[i + k] if pattern[k] == 1.nums[i + k + 1] == nums[i + k] if pattern[k] == 0.nums[i + k + 1] < nums[i + k] if pattern[k] == -1.Return the count of subarrays in nums that match the pattern.
Example 1:
Input: nums = [1,2,3,4,5,6], pattern = [1,1] Output: 4 Explanation: The pattern [1,1] indicates that we are looking for strictly increasing subarrays of size 3. In the array nums, the subarrays [1,2,3], [2,3,4], [3,4,5], and [4,5,6] match this pattern. Hence, there are 4 subarrays in nums that match the pattern.
Example 2:
Input: nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1] Output: 2 Explanation: Here, the pattern [1,0,-1] indicates that we are looking for a sequence where the first number is smaller than the second, the second is equal to the third, and the third is greater than the fourth. In the array nums, the subarrays [1,4,4,1], and [3,5,5,3] match this pattern. Hence, there are 2 subarrays in nums that match the pattern.
Constraints:
2 <= n == nums.length <= 1061 <= nums[i] <= 1091 <= m == pattern.length < n-1 <= pattern[i] <= 1In #3036 Number of Subarrays That Match a Pattern II, the goal is to count subarrays whose relative comparisons follow a given pattern. Instead of matching raw values, we first convert the array into a comparison sequence. For each adjacent pair in nums, we record whether the relationship is -1 (decreasing), 0 (equal), or 1 (increasing). This transforms the problem into a classic pattern matching task.
Once the comparison array is built, the challenge becomes finding how many subarrays match the given pattern. Efficient techniques such as rolling hash (Rabin–Karp) or KMP string matching can be applied to search the pattern within the transformed sequence. These approaches avoid checking each subarray individually and instead perform linear-time matching.
The optimal strategy scans the array once to build the comparison sequence and then performs pattern matching in linear time. This results in a total time complexity of O(n + m) with O(m) additional space for preprocessing structures.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Comparison Array + KMP / Rolling Hash | O(n + m) | O(m) |
Ashish Pratap Singh
Use these hints if you're stuck. Try solving on your own first.
Create a second array <code>nums2</code> such that <code>nums2[i] = 1</code> if <code>nums[i + 1] > nums[i]</code>, <code>nums2[i] = 0</code> if <code>nums[i + 1] == nums[i]</code>, and <code>nums2[i] = -1</code> if <code>nums[i + 1] < nums[i]</code>.
The problem becomes: “Count the number of subarrays in <code>nums2</code> that are equal to <code>pattern</code>.
Use Knuth-Morris-Pratt or Z-Function algorithms.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Problems involving pattern matching, rolling hash, and sequence transformations are common in FAANG-style interviews. While the exact question may vary, the underlying concepts such as KMP, hashing, and array preprocessing are frequently tested.
The problem focuses on relative relationships between consecutive elements rather than exact values. By transforming these relationships into a sequence, the task becomes identical to finding pattern occurrences in an array or string. Pattern matching algorithms efficiently detect all matches in linear time.
The optimal approach converts the array into a comparison sequence representing increases, decreases, or equal values. The pattern is then matched against this sequence using efficient algorithms such as KMP or rolling hash. This reduces the problem to linear-time pattern matching.
Techniques like rolling hash (Rabin–Karp) or the KMP string matching algorithm work best. They allow fast detection of pattern matches without recomputing comparisons for every subarray. This makes the solution scalable for large inputs.