3034. Number of Subarrays That Match a Pattern I - Detailed Explanation

Free Coding Questions Catalog

Boost your coding skills with our essential coding questions catalog. Take a step towards a better tech career now!

Problem Statement

You are given a 0‑indexed integer array nums of length n, and a 0‑indexed integer array pattern of length m containing only -1, 0, or 1.
A subarray nums[i..i+m] (of length m+1) matches the pattern if for every k in [0..m-1]:

pattern[k] == 1 implies nums[i+k+1] > nums[i+k]
pattern[k] == 0 implies nums[i+k+1] == nums[i+k]
pattern[k] == -1 implies nums[i+k+1] < nums[i+k]
Return the total number of subarrays in nums that match pattern.

Examples

Example 1

Input   nums = [1,2,3,4,5,6], pattern = [1,1]
Output  4
Explanation  We need strictly increasing runs of length 3. The matching subarrays are:
 [1,2,3], [2,3,4], [3,4,5], [4,5,6].

Example 2

Input   nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output  2
Explanation  We need subarrays of length 4 where: up, equal, down.
 The matching ones are [1,4,4,1] and [3,5,5,3].

Constraints

2 ≤ n = nums.length ≤ 100
1 ≤ nums[i] ≤ 10^9
1 ≤ m = pattern.length < n
pattern[k] ∈ {-1, 0, 1}

Hints

How many length‑(m+1) subarrays are there in nums of length n?
If you preprocess a “sign” array of size n−1 where sign[i] = compare(nums[i], nums[i+1]) (−1,0,1), matching pattern becomes a substring search.
Can you slide a window of size m over that sign array and compare in O(m) per position? Can you do even better with string‑matching (KMP)?

Approach 1 Enumeration (O(n·m))

Check each candidate start i from 0 to n−m−1, loop k from 0 to m−1, and verify compare(nums[i+k],nums[i+k+1]) == pattern[k].

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity

Time O(n·m)
Space O(1)

Approach 2 Sliding Window on Sign Array (O(n·m) but simpler constants)

Build sign[i] = compare(nums[i], nums[i+1]) for i∈[0..n-2]. Then each subarray of length m+1 corresponds to a window of length m in sign. Compare those windows directly.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity

Time O(n·m)
Space O(n)

Approach 3 KMP on Sign Array (O(n+m))

Treat sign and pattern as “texts” and “pattern” in string matching. Use the Knuth–Morris–Pratt algorithm to count occurrences of pattern in sign.

Python Code

Python3

. . . .

Java Code

Java

. . . .

Complexity

Time O(n + m)
Space O(n + m)

Step‑by‑Step Walkthrough (Example 2)

nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]

Sign array: compare adjacent:
[1, 0, -1, 1, 1, 0, -1]
Windows of length 3:
- [1,0,-1] at i=0 → match → count=1
- [0,-1,1] → no
- [-1,1,1] → no
- [1,1,0] → no
- [1,0,-1] at i=4 → match → count=2
Return 2.

Common Mistakes

Off‑by‑one in loop bounds (i ≤ n−m−1, not n−m).
Forgetting to compare pattern.length+1 subarray has pattern.length comparisons.
Skipping duplicate code when building sign array vs direct cmp.
In KMP, incorrectly updating j on mismatch.