Number of Subarrays That Match a Pattern II solution and explanation
5 more videos on this problem
3036. Number of Subarrays That Match a Pattern II | KMP | String MatchingAryan Mittal · 18:36 · 4K views
Number of Subarrays That Match a Pattern | Brute Force | Optimal | KMP | Leetcode 3034 | 3036codestorywithMIK · 37:38 · 3K views
3036. Number of Subarrays That Match a Pattern II | Leetcode Weekly 384codingMohan · 16:51 · 640 views
3036. Number of Subarrays That Match a Pattern II (Leetcode Hard)Programming Live with Larry · 15:14 · 355 views
LeetCode 3036 - Number of Subarrays that Match a Pattern II - PythonAlpha-Code · 19:02 · 81 views
3034. Number of Subarrays That Match a Pattern I , 3036. Number of Subarrays That Match a Pattern IIShivam Mishra LeetCode · 14:28 · 69 views
The problem
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]ifpattern[k] == 1.nums[i + k + 1] == nums[i + k]ifpattern[k] == 0.nums[i + k + 1] < nums[i + k]ifpattern[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] <= 1
Approach overview
Problem 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 1: Sliding Window Approach
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.
def count_matching_subarrays(nums, pattern):
n = len(nums)
m = len(pattern)
count = 0
for start in range(n - m):
match = True
for k in range(m):
if pattern[k] == 1 and not (nums[start + k + 1] > nums[start + k]):
match = False
break
elif pattern[k] == 0 and not (nums[start + k + 1] == nums[start + k]):
match = False
break
elif pattern[k] == -1 and not (nums[start + k + 1] < nums[start + k]):
match = False
break
if match:
count += 1
return count
# Example usage
print(count_matching_subarrays([1, 2, 3, 4, 5, 6], [1, 1])) # Output: 4
print(count_matching_subarrays([1, 4, 4, 1, 3, 5, 5, 3], [1, 0, -1])) # Output: 2public class Solution {
public int countMatchingSubarrays(int[] nums, int[] pattern) {
int n = nums.length;
int m = pattern.length;
int count = 0;
for (int start = 0; start <= n - m - 1; start++) {
boolean match = true;
for (int k = 0; k < m; k++) {
if ((pattern[k] == 1 && nums[start + k + 1] <= nums[start + k]) ||
(pattern[k] == 0 && nums[start + k + 1] != nums[start + k]) ||
(pattern[k] == -1 && nums[start + k + 1] >= nums[start + k])) {
match = false;
break;
}
}
if (match) count++;
}
return count;
}
// Example usage
// int result1 = new Solution().countMatchingSubarrays(new int[]{1,2,3,4,5,6}, new int[]{1,1}); // Output: 4
// int result2 = new Solution().countMatchingSubarrays(new int[]{1,4,4,1,3,5,5,3}, new int[]{1,0,-1}); // Output: 2
}#include <vector>
using namespace std;
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
int n = nums.size();
int m = pattern.size();
int count = 0;
for (int start = 0; start <= n - m - 1; ++start) {
bool match = true;
for (int k = 0; k < m; ++k) {
if ((pattern[k] == 1 && nums[start + k + 1] <= nums[start + k]) ||
(pattern[k] == 0 && nums[start + k + 1] != nums[start + k]) ||
(pattern[k] == -1 && nums[start + k + 1] >= nums[start + k])) {
match = false;
break;
}
}
if (match) {
++count;
}
}
return count;
}
// Example usage
// int result1 = countMatchingSubarrays(vector<int>{1, 2, 3, 4, 5, 6}, vector<int>{1, 1}); // Output: 4
// int result2 = countMatchingSubarrays(vector<int>{1, 4, 4, 1, 3, 5, 5, 3}, vector<int>{1, 0, -1}); // Output: 2function countMatchingSubarrays(nums, pattern) {
const n = nums.length;
const m = pattern.length;
let count = 0;
for (let start = 0; start <= n - m - 1; start++) {
let match = true;
for (let k = 0; k < m; k++) {
if ((pattern[k] === 1 && nums[start + k + 1] <= nums[start + k]) ||
(pattern[k] === 0 && nums[start + k + 1] !== nums[start + k]) ||
(pattern[k] === -1 && nums[start + k + 1] >= nums[start + k])) {
match = false;
break;
}
}
if (match) count++;
}
return count;
}
// Example usage
// console.log(countMatchingSubarrays([1,2,3,4,5,6], [1,1])); // Output: 4
// console.log(countMatchingSubarrays([1,4,4,1,3,5,5,3], [1,0,-1])); // Output: 2This 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.
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.
Approach 2: Two-Pointer Optimization
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 would be a slightly more optimized version that attempts to skip unnecessary checks.
def count_matching_subarrays_tp(nums, pattern):
n = len(nums)
m = len(pattern)
count = 0
i = 0
while i <= n - m - 1:
j = i
match = True
for k in range(m):
if pattern[k] == 1 and not (nums[j + 1] > nums[j]):
match = False
break
elif pattern[k] == 0 and not (nums[j + 1] == nums[j]):
match = False
break
elif pattern[k] == -1 and not (nums[j + 1] < nums[j]):
match = False
break
j += 1
if match:
count += 1
i += 1 # could implement a more clever skip on failure
return count
# Example usage
print(count_matching_subarrays_tp([1, 2, 3, 4, 5, 6], [1, 1])) # Output: 4
print(count_matching_subarrays_tp([1, 4, 4, 1, 3, 5, 5, 3], [1, 0, -1])) # Output: 2This 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.
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).
Approach 3: Default Approach
class Solution {
countMatchingSubarrays(nums: number[], pattern: number[]): number {
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i + 1] > nums[i]) nums[i] = 1;
else if (nums[i + 1] < nums[i]) nums[i] = -1;
else nums[i] = 0;
}
nums[nums.length - 1] = 2;
const n = nums.length;
const m = pattern.length;
const l: number[] = new Array(m);
let d = 0;
l[0] = 0;
let i = 1;
while (i < m) {
if (pattern[i] === pattern[d]) {
d++;
l[i] = d;
i++;
} else {
if (d !== 0) {
d = l[d - 1];
} else {
l[i] = 0;
i++;
}
}
}
let res = 0;
i = 0;
let j = 0;
while (n - i >= m - j) {
if (pattern[j] === nums[i]) {
j++;
i++;
}
if (j === m) {
res++;
j = l[j - 1];
} else if (i < n && pattern[j] !== nums[i]) {
if (j !== 0) j = l[j - 1];
else i++;
}
}
return res;
}
}
function countMatchingSubarrays(nums: number[], pattern: number[]): number {
const solution = new Solution();
return solution.countMatchingSubarrays(nums, pattern);
}func countMatchingSubarrays(nums []int, pattern []int) int {
N := len(pattern)
ps := make([]int, N+1)
ps[0], ps[1] = -1, 0
for i, p := 2, 0; i <= N; i++ {
x := pattern[i-1]
for p >= 0 && pattern[p] != x {
p = ps[p]
}
p++
ps[i] = p
}
res := 0
M := len(nums)
for i, p := 1, 0; i < M; i++ {
t := nums[i] - nums[i-1]
switch {
case t > 0:
t = 1
case t < 0:
t = -1
}
for p >= 0 && pattern[p] != t {
p = ps[p]
}
if p++; p == N {
res++
p = ps[p]
}
}
return res
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sliding Window Approach | The time complexity of this approach is |
| Two-Pointer Optimization | The time complexity remains |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Number of Subarrays That Match a Pattern II easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing a transformation from numeric comparisons to pattern matching. Efficient solutions rely on rolling hash or linear scanning techniques rather than brute force enumeration of subarrays.
Number of Subarrays That Match a Pattern II Python/Java solution
Python, Java, C++, and JavaScript implementations typically convert the array into a comparison sequence and then apply sliding window hashing. Python versions often use simple integer hashing, while Java and C++ implementations may use modular rolling hash for collision safety.
How to solve Number of Subarrays That Match a Pattern II in O(n)?
First build a derived array that records whether each adjacent pair increases, decreases, or stays equal. Then search for the pattern inside this derived array using a rolling hash or linear sliding window comparison. Because the sequence is scanned once and hash updates are constant time, the total runtime is O(n).
What is the best approach for Number of Subarrays That Match a Pattern II?
The most reliable approach converts the array into a comparison sequence and applies sliding window pattern matching with a rolling hash. This reduces the task to substring search and runs in O(n) time. It scales well for large inputs and avoids recomputing comparisons for every subarray.
Is Number of Subarrays That Match a Pattern II asked at Google/Amazon/Meta?
Problems combining pattern matching and array transformations commonly appear in interviews at companies like Google, Amazon, and Meta. Variants test whether candidates recognize reductions to string matching techniques such as Rabin–Karp or KMP while maintaining linear complexity.
What data structure is used in Number of Subarrays That Match a Pattern II?
The solution primarily uses arrays along with a sliding window. Many implementations also rely on rolling hash values or hash-based comparisons to detect matches efficiently. These techniques come from string matching and hash function design.
What is the time complexity of Number of Subarrays That Match a Pattern II?
The optimal solution runs in O(n) time where n is the length of the input array. After converting the array into a comparison sequence of length n-1, a sliding window or rolling hash scans it once. Space complexity ranges from O(1) to O(n) depending on whether auxiliary arrays or hashing structures are used.