Watch 6 video solutions for Number of Subarrays That Match a Pattern I, a medium level problem involving Array, Rolling Hash, String Matching. This walkthrough by codestorywithMIK has 3,113 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 <= 1001 <= nums[i] <= 1091 <= m == pattern.length < n-1 <= pattern[i] <= 1Problem Overview: You are given an integer array nums and a pattern array containing values -1, 0, and 1. Each pattern value describes the relationship between two consecutive numbers: decreasing, equal, or increasing. The task is to count how many subarrays of length pattern.length + 1 produce the same sequence of comparisons.
Approach 1: Brute Force Comparison (Time: O(n * m), Space: O(1))
The direct method checks every possible subarray of length m + 1 where m is the pattern length. For each candidate start index, iterate through the next m pairs and compute the relationship between adjacent elements: 1 if increasing, 0 if equal, and -1 if decreasing. Compare this generated relation with the corresponding pattern value. If all comparisons match, increment the result. This approach uses basic array traversal and is easy to implement, but it repeatedly recomputes comparisons for overlapping windows.
Approach 2: Optimized Sliding Window (Time: O(n), Space: O(n))
A more efficient approach converts the original array into a difference pattern first. Build a new array where each element represents the relation between nums[i] and nums[i+1]. This produces a sequence of -1, 0, and 1 values. The problem then becomes a classic string matching task: count how many times the pattern appears inside this difference array.
Using a sliding window of size m, compare the window against the pattern while moving one step at a time. Because the comparison array already encodes relationships, each shift only requires checking the window values rather than recalculating numeric comparisons. Some implementations further optimize this using rolling hash to treat the relation sequence like a hashed string and detect matches in constant time per step.
This reduces repeated work and processes the array in a single pass after preprocessing. The time complexity becomes O(n) since each comparison relation is computed once and each window is checked once.
Recommended for interviews: Start with the brute force approach to demonstrate that you understand how the pattern maps to pairwise comparisons. Then move to the optimized sliding window or string‑matching interpretation. Interviewers typically expect the linear-time idea because it avoids recomputing comparisons for overlapping subarrays and shows familiarity with pattern matching techniques.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n * m) | O(1) | Useful for understanding the comparison logic or when the pattern length is very small. |
| Sliding Window on Difference Array | O(n) | O(n) | General optimal solution for large arrays. Converts numeric comparisons into a pattern matching problem. |