Number of Subarrays That Match a Pattern II — Solution
Number of Subarrays That Match a Pattern II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Subarrays That Match a Pattern II is a hard coding problem on arrays, rolling hash and string matching, asked in Amazon interviews.
- Difficulty: Hard
- Topics: Arrays, Rolling Hash, String Matching
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums of length n and an array pattern of length m whose entries are each -1, 0 or 1.
A subarray nums[i..i+m] (of size m + 1) matches the pattern when, for every k from 0 to m - 1:
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 number of subarrays of nums that match pattern. This is the large version: n can reach a million, so checking every start against the whole pattern is too slow.
Example 1
Input: nums = [1,2,3,4,5,6], pattern = [1,1]
Output: 4
Explanation: Every window of three consecutive values is strictly increasing.
Example 2
Input: nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output: 2
Explanation: [1,4,4,1] and [3,5,5,3] match.
Example 3
Input: nums = [3,1,3,1,3,1,3], pattern = [-1,1,-1]
Output: 2
Explanation: The matches start at indices 0 and 2 and overlap — both count.
Constraints
2 <= n == nums.length <= 10^61 <= nums[i] <= 10^91 <= m == pattern.length < n-1 <= pattern[i] <= 1
Hints for Number of Subarrays That Match a Pattern II
Hint 1
Turn
numsinto a sequence ofn - 1signs:1,0or-1for each neighbouring pair.Hint 2
A subarray matches exactly when
patternappears in that sign sequence starting at the subarray's first index.Hint 3
Count the (possibly overlapping) occurrences of
patternin the sign sequence with a linear string-matching algorithm such as KMP or the Z-function.
How to solve Number of Subarrays That Match a Pattern II
Comparing neighbours turns the array into a 'text' of signs over the alphabet {-1, 0, 1}. The question becomes: how many times does pattern occur in that text? That is classic string matching, solvable in linear time with KMP.
Approach
- Build the KMP failure table of
pattern:fail[i]is the length of the longest proper border ofpattern[0..i]. - Scan
i = 0 .. n - 2, computing the signsofnums[i+1]versusnums[i]on the fly. - Keep
j, the length of the pattern prefix matched so far: whilej > 0ands != pattern[j], fall back tofail[j - 1]; ifs == pattern[j], advancej. - When
j == m, count a match and continue fromfail[m - 1]so overlapping matches are found.
Why it works
Subarray nums[i..i+m] matches iff signs i .. i+m-1 equal pattern, so the matches are in one-to-one correspondence with occurrences of pattern in the sign text. KMP finds every occurrence, overlapping ones included, and its fallback pointer only moves forward overall, so the scan is linear.
Complexity
- Time —
O(n + m) - Space —
O(m)
Pitfalls
- After a full match fall back to
fail[m - 1]rather than resetting to 0, or overlapping matches like Example 3 are missed. - The text has
n - 1symbols, notn. - Use comparisons for the sign rather than a subtraction that could overflow in other variants of the problem.
Reference solution
Python
from typing import List
def countMatchingSubarrays(nums: List[int], pattern: List[int]) -> int:
m = len(pattern)
fail = [0] * m
j = 0
for i in range(1, m):
while j and pattern[i] != pattern[j]:
j = fail[j - 1]
if pattern[i] == pattern[j]:
j += 1
fail[i] = j
res = j = 0
for i in range(len(nums) - 1):
a, b = nums[i], nums[i + 1]
s = (b > a) - (b < a)
while j and s != pattern[j]:
j = fail[j - 1]
if s == pattern[j]:
j += 1
if j == m:
res += 1
j = fail[j - 1]
return resJava
public static int countMatchingSubarrays(int[] nums, int[] pattern) {
int m = pattern.length;
int[] fail = new int[m];
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) j = fail[j - 1];
if (pattern[i] == pattern[j]) j++;
fail[i] = j;
}
int res = 0;
j = 0;
for (int t = 0; t + 1 < nums.length; t++) {
int s = Integer.compare(nums[t + 1], nums[t]);
while (j > 0 && s != pattern[j]) j = fail[j - 1];
if (s == pattern[j]) j++;
if (j == m) { res++; j = fail[j - 1]; }
}
return res;
}C++
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
int m = pattern.size();
vector<int> fail(m, 0);
int j = 0;
for (int i = 1; i < m; i++) {
while (j > 0 && pattern[i] != pattern[j]) j = fail[j - 1];
if (pattern[i] == pattern[j]) j++;
fail[i] = j;
}
int res = 0;
j = 0;
for (int t = 0; t + 1 < (int) nums.size(); t++) {
int s = (nums[t + 1] > nums[t]) - (nums[t + 1] < nums[t]);
while (j > 0 && s != pattern[j]) j = fail[j - 1];
if (s == pattern[j]) j++;
if (j == m) { res++; j = fail[j - 1]; }
}
return res;
}JavaScript
var countMatchingSubarrays = function(nums, pattern) {
var m = pattern.length;
var fail = new Array(m).fill(0);
var j = 0;
for (var i = 1; i < m; i++) {
while (j > 0 && pattern[i] !== pattern[j]) j = fail[j - 1];
if (pattern[i] === pattern[j]) j++;
fail[i] = j;
}
var res = 0;
j = 0;
for (var t = 0; t + 1 < nums.length; t++) {
var a = nums[t], b = nums[t + 1];
var s = b > a ? 1 : (b === a ? 0 : -1);
while (j > 0 && s !== pattern[j]) j = fail[j - 1];
if (s === pattern[j]) j++;
if (j === m) { res++; j = fail[j - 1]; }
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays