Number of Subarrays That Match a Pattern I — Solution
Number of Subarrays That Match a Pattern I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Number of Subarrays That Match a Pattern I is a medium coding problem on arrays, rolling hash and string matching, asked in Amazon interviews.
- Difficulty: Medium
- 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.
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: [1,2,3], [2,3,4], [3,4,5] and [4,5,6].
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] go up, stay level, then go down.
Example 3
Input: nums = [7,7,7,7], pattern = [0,0,0]
Output: 1
Explanation: The only subarray of size 4 is the whole array, and it never changes.
Constraints
2 <= n == nums.length <= 1001 <= nums[i] <= 10^91 <= m == pattern.length < n-1 <= pattern[i] <= 1
Hints for Number of Subarrays That Match a Pattern I
Hint 1
A pattern entry only describes how one element compares with the next one.
Hint 2
For every start
i, walkkfrom0tom - 1and compare the sign ofnums[i + k + 1] - nums[i + k]withpattern[k].Hint 3
Stop a start early at its first mismatch and count the starts that survive all
mcomparisons.
How to solve Number of Subarrays That Match a Pattern I
With n <= 100 each of the n - m candidate subarrays can be checked against the pattern directly — one comparison of neighbours per pattern entry.
Approach
- For every start
iwithi + m < n: - for
k = 0 .. m - 1, computes = 1ifnums[i+k+1] > nums[i+k],0if equal,-1if smaller; ifs != pattern[k], the start fails. - Count the starts that never fail.
Why it works
The definition of a match is exactly these m neighbour comparisons, and every subarray of size m + 1 is identified by its start i, so each candidate is tested once against the full definition.
Complexity
- Time —
O(n * m) - Space —
O(1)
Pitfalls
- The subarray has
m + 1elements, so the last start isn - m - 1. - Compare values rather than subtracting into a sign in languages where a difference could overflow — here values are at most
10^9, so a difference fits in 32 bits, but a comparison is clearer.
Reference solution
Python
from typing import List
def countMatchingSubarrays(nums: List[int], pattern: List[int]) -> int:
n, m = len(nums), len(pattern)
res = 0
for i in range(n - m):
ok = True
for k in range(m):
a, b = nums[i + k], nums[i + k + 1]
s = 1 if b > a else (0 if b == a else -1)
if s != pattern[k]:
ok = False
break
if ok:
res += 1
return resJava
public static int countMatchingSubarrays(int[] nums, int[] pattern) {
int n = nums.length, m = pattern.length, res = 0;
for (int i = 0; i + m < n; i++) {
boolean ok = true;
for (int k = 0; k < m; k++) {
int s = Integer.compare(nums[i + k + 1], nums[i + k]);
if (s != pattern[k]) { ok = false; break; }
}
if (ok) res++;
}
return res;
}C++
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
int n = nums.size(), m = pattern.size(), res = 0;
for (int i = 0; i + m < n; i++) {
bool ok = true;
for (int k = 0; k < m; k++) {
int a = nums[i + k], b = nums[i + k + 1];
int s = (b > a) - (b < a);
if (s != pattern[k]) { ok = false; break; }
}
if (ok) res++;
}
return res;
}JavaScript
var countMatchingSubarrays = function(nums, pattern) {
var n = nums.length, m = pattern.length, res = 0;
for (var i = 0; i + m < n; i++) {
var ok = true;
for (var k = 0; k < m; k++) {
var a = nums[i + k], b = nums[i + k + 1];
var s = b > a ? 1 : (b === a ? 0 : -1);
if (s !== pattern[k]) { ok = false; break; }
}
if (ok) res++;
}
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