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] <= 1Problem Overview: You get an integer array nums and a pattern array containing values -1, 0, and 1. The pattern describes how consecutive elements should compare (decreasing, equal, increasing). The task is to count how many subarrays of nums produce the same comparison pattern.
Approach 1: Sliding Window + Rolling Hash (O(n) time, O(n) space)
Convert the array into a comparison sequence where each adjacent pair becomes -1, 0, or 1. The problem then becomes classic pattern matching: find how many times the pattern appears inside this derived sequence. Apply a rolling hash (similar to Rabin–Karp) while sliding a window of length m across the comparison array. Each step updates the hash in constant time and compares it with the pattern hash. This avoids recomputing comparisons for every window and keeps the scan linear.
The key insight: subarray validity depends only on adjacent comparisons, not the actual numbers. By transforming the input into a comparison string, the task reduces to efficient substring matching using a rolling hash or other string matching technique.
Approach 2: Two-Pointer Optimization (O(n) time, O(1) space)
Instead of hashing, scan the comparison array using two pointers. Start a window where the pattern could match and compare each step with the expected pattern value. If a mismatch occurs, shift the starting pointer forward and restart matching. When all m comparisons match, increment the result and move forward to search for overlapping matches. Since each element participates in only a small number of checks, the overall complexity stays linear.
This approach relies purely on pointer movement and direct comparisons, making it memory efficient. It works well when the pattern length is relatively small compared to the input size.
Recommended for interviews: The sliding window with rolling hash is the most scalable and closest to standard pattern matching problems. Interviewers expect candidates to recognize the transformation from numeric comparisons to a sequence and apply techniques from array processing and substring search. The two-pointer approach demonstrates strong intuition and space optimization, but the hashing solution more clearly shows algorithmic pattern recognition.
This approach uses a sliding window that iterates over the nums array, checking each subarray of length m+1 to see if it matches the given pattern. By moving a window of this fixed length through nums, we can efficiently count the matching subarrays. This is a straightforward way to ensure that we are considering each subarray only once and directly comparing adjacent elements as specified by pattern.
This solution iterates through the array nums, using a sliding window of size m+1. For each potential starting index, it checks the conditions dictated by pattern on the subarray nums[i..i+m]. If all conditions are satisfied, we increment our counter for matching subarrays.
Python
C++
Java
JavaScript
The time complexity of this approach is O(n*m), as we're iterating over the nums array with a window of size m, and for each window position, we're checking conditions which take O(m) time. The space complexity is O(1) as we're using only a constant amount of extra space.
This approach attempts to further optimize the sliding window by using two pointers, i and j, to skip unnecessary comparisons and focus only on valid starting points. This optimization works by finding the first valid point where a match might start, thereby potentially reducing average case runtime compared to the naive sliding window.
This attempt uses a while loop allowing for more advanced control over pointer movement, which can enable you to skip some repetitive computations on certain conditions. However, this is more complex and may not show significant gains compared to the sliding window in worst-case scenarios.
Python
The time complexity remains O(n*m) in the worst case, but the two-pointer technique can sometimes offer O(n) on average if the skipping logic is soundly applied. Space complexity remains O(1).
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Sliding Window Approach | The time complexity of this approach is |
| Two-Pointer Optimization | The time complexity remains |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sliding Window + Rolling Hash | O(n) | O(n) | Best general solution for large arrays and long patterns |
| Two-Pointer Optimization | O(n) | O(1) | When pattern length is small and memory usage should stay minimal |
3036. Number of Subarrays That Match a Pattern II | KMP | String Matching • Aryan Mittal • 4,609 views views
Watch 5 more video solutions →Practice Number of Subarrays That Match a Pattern II with our built-in code editor and test cases.
Practice on FleetCode