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

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

1. How many length‑(m+1) subarrays are there in nums of length n?
2. 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.
3. 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

Java Code