Watch 6 video solutions for Number of Subarrays That Match a Pattern II, a hard level problem involving Array, Rolling Hash, String Matching. This walkthrough by Aryan Mittal has 4,609 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |