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.
This approach involves iterating over all possible subarrays of the given array nums and checking each subarray against the specified pattern. Since we have an array pattern of length m, the length of the subarrays we need to check is m + 1. For each subarray, verify that it matches the pattern by checking the conditions at each step.
The function countSubarrays iterates through each possible starting index of the subarray in nums, checks if the subarray of length m + 1 matches the pattern, and increments the count if it does. The outer loop goes from index 0 to numsSize - patternSize - 1 to fit the required subarray length.
Time Complexity: O(n * m), where n is the length of nums and m is the length of pattern. This is because each subarray check iterates over the pattern.
Space Complexity: O(1), as no additional space beyond counters is used.
By using a sliding window approach, we can optimize the search for matching subarrays. The core idea is to progress through nums with a window of size m+1 and dynamically verify the pattern in real-time for each window shift. This eliminates unnecessary re-evaluation of indices already validated or invalidated as we move forward.
In the C implementation, we maintain a count of consecutive pattern matches using currentMatchLength. If a segment matches the pattern, it is counted and the current match length is adjusted for subsequent checks, thus leveraging a sliding window technique.
C
Java
Python
JavaScript
Time Complexity: O(n), as the single pass through nums using a sliding window provides the match count directly.
Space Complexity: O(1), only a few variables are utilized.
We can enumerate all subarrays of array nums with a length of m + 1, and then check whether they match the pattern array pattern. If they do, we increment the answer by one.
The time complexity is O(n times m), where n and m are the lengths of the arrays nums and pattern respectively. The space complexity is O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m), where n is the length of nums and m is the length of pattern. This is because each subarray check iterates over the pattern. Space Complexity: O(1), as no additional space beyond counters is used. |
| Optimized Sliding Window | Time Complexity: O(n), as the single pass through Space Complexity: O(1), only a few variables are utilized. |
| Enumeration | — |
| 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. |
Number of Subarrays That Match a Pattern | Brute Force | Optimal | KMP | Leetcode 3034 | 3036 • codestorywithMIK • 3,113 views views
Watch 5 more video solutions →Practice Number of Subarrays That Match a Pattern I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor