# Number of Subarrays That Match a Pattern I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-i)
Canonical: https://scaleengineer.com/dsa/problems/number-of-subarrays-that-match-a-pattern-i
**Patterns:** [String Matching](https://scaleengineer.com/dsa/patterns/string-matching), [Rolling Hash](https://scaleengineer.com/dsa/patterns/rolling-hash), [Hash Function](https://scaleengineer.com/dsa/patterns/hash-function)
**Data structures:** Array
**Companies:** [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [Autodesk](https://scaleengineer.com/companies/autodesk)
---
## 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]` if `pattern[k] == 1`.
* `nums[i + k + 1] == nums[i + k]` if `pattern[k] == 0`.
* `nums[i + k + 1] < nums[i + k]` if `pattern[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 <= 100`
* `1 <= nums[i] <= 109`
* `1 <= m == pattern.length < n`
* `-1 <= pattern[i] <= 1`

# Approaches
## Brute-Force Subarray Check
This approach directly simulates the process described in the problem. We iterate through all possible starting positions for a subarray of size `m+1` in the `nums` array. For each potential subarray, we check if it matches the given `pattern` by comparing adjacent elements according to the pattern's rules.
**Time:** O(n * m). The outer loop runs `n - m` times, and for each iteration, the inner loop runs `m` times. This gives a total complexity proportional to `(n-m)*m`. · **Space:** O(1). We only use a few variables to keep track of the count and loop indices, so the space used is constant.
**Pros:** Easy to understand and implement.; Minimal space usage (O(1)).; Sufficiently fast for the given constraints (n <= 100).
**Cons:** Inefficient for larger inputs, as it involves nested loops leading to a time complexity of O(n*m).
### Explanation
We need to find subarrays of `nums` of length `m+1`. A subarray can start at index `i` and end at index `i+m`. The possible values for `i` range from `0` to `n - (m + 1)`. We use an outer loop to iterate through each possible starting index `i`. Inside this loop, we assume the current subarray is a match and use an inner loop to verify this assumption. The inner loop iterates from `k = 0` to `m-1`, checking the condition for `pattern[k]`. For each `k`, we compare `nums[i + k + 1]` with `nums[i + k]`. If any of these conditions are not met, the current subarray starting at `i` is not a match. We break the inner loop and proceed to the next starting index `i+1`. If the inner loop completes without finding any mismatch, it means the subarray `nums[i...i+m]` is a valid match, and we increment a counter. After the outer loop finishes, the counter will hold the total number of matching subarrays.

```java
class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.length;
        int m = pattern.length;
        int count = 0;
        // Iterate through all possible starting positions of a subarray of size m+1
        for (int i = 0; i <= n - m - 1; i++) {
            boolean isMatch = true;
            // Check if the subarray nums[i...i+m] matches the pattern
            for (int k = 0; k < m; k++) {
                if (pattern[k] == 1) {
                    if (nums[i + k + 1] <= nums[i + k]) {
                        isMatch = false;
                        break;
                    }
                } else if (pattern[k] == 0) {
                    if (nums[i + k + 1] != nums[i + k]) {
                        isMatch = false;
                        break;
                    }
                } else { // pattern[k] == -1
                    if (nums[i + k + 1] >= nums[i + k]) {
                        isMatch = false;
                        break;
                    }
                }
            }
            if (isMatch) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate with an index `i` from `0` to `n - m - 1`. This `i` represents the start of a potential matching subarray in `nums`.
- For each `i`, assume a match is found by setting a boolean flag, e.g., `isMatch = true`.
- Start an inner loop with index `k` from `0` to `m - 1`. This `k` corresponds to the index in the `pattern` array.
- Inside the inner loop, check the relationship between `nums[i + k + 1]` and `nums[i + k]` against `pattern[k]`.
- If the condition for `pattern[k]` is not satisfied, set `isMatch` to `false` and break the inner loop.
- After the inner loop, if `isMatch` is still `true`, increment `count`.
- Return `count` after the outer loop finishes.

## Transformation to String Matching with KMP
This approach improves upon the brute-force method by transforming the problem into a classic string (or array) matching problem. We first convert the `nums` array into a "relationship" array that mirrors the structure of the `pattern` array. Then, we use the highly efficient Knuth-Morris-Pratt (KMP) algorithm to find occurrences of the `pattern` in this new array.
**Time:** O(n + m). The transformation takes O(n) time. The KMP algorithm involves O(m) for pre-computation (LPS array) and O(n) for the search. Since `m < n`, the total time complexity is O(n). · **Space:** O(n + m). We need O(n-1) space for the `numsPattern` array and O(m) space for the `lps` array. Since `m < n`, this simplifies to O(n).
**Pros:** Asymptotically more efficient with a linear time complexity.; A standard and powerful technique for pattern matching that is useful in many other problems.
**Cons:** More complex to implement, requiring knowledge of the KMP algorithm and its LPS array computation.; Uses extra space to store the transformed array and the LPS array.
### Explanation
This method involves two main steps:

**1. Transformation:** We create a new integer array, `numsPattern`, of size `n-1`. We populate this array by comparing adjacent elements in `nums`. For each `i` from `0` to `n-2`:
- `numsPattern[i] = 1` if `nums[i+1] > nums[i]`.
- `numsPattern[i] = 0` if `nums[i+1] == nums[i]`.
- `numsPattern[i] = -1` if `nums[i+1] < nums[i]`.
After this transformation, the problem is equivalent to finding the number of occurrences of the `pattern` array as a contiguous subarray within the `numsPattern` array.

**2. KMP Algorithm:** The KMP algorithm is an efficient way to solve this subarray search problem. It avoids redundant comparisons by using a pre-computed Longest Proper Prefix Suffix (LPS) array for the `pattern`. The search for the pattern within the transformed text is then done in linear time.

```java
class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.length;
        int m = pattern.length;
        
        // Step 1: Transform nums into a pattern array
        int[] numsPattern = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                numsPattern[i] = 1;
            } else if (nums[i + 1] < nums[i]) {
                numsPattern[i] = -1;
            } else {
                numsPattern[i] = 0;
            }
        }
        
        // Step 2: Use KMP to find occurrences of pattern in numsPattern
        return kmpSearch(numsPattern, pattern);
    }

    private int[] computeLPS(int[] pattern) {
        int m = pattern.length;
        int[] lps = new int[m];
        int length = 0; // length of the previous longest prefix suffix
        int i = 1;
        while (i < m) {
            if (pattern[i] == pattern[length]) {
                length++;
                lps[i] = length;
                i++;
            } else {
                if (length != 0) {
                    length = lps[length - 1];
                } else {
                    lps[i] = 0;
                    i++;
                }
            }
        }
        return lps;
    }

    private int kmpSearch(int[] text, int[] pattern) {
        int n = text.length;
        int m = pattern.length;
        if (m == 0) return n + 1; // Or based on problem spec for empty pattern
        if (n < m) return 0;
        
        int[] lps = computeLPS(pattern);
        int i = 0; // index for text
        int j = 0; // index for pattern
        int count = 0;
        
        while (i < n) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            }
            if (j == m) {
                count++;
                j = lps[j - 1];
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a new array `numsPattern` of size `n-1`.
- Iterate from `i = 0` to `n-2` and populate `numsPattern[i]` with `1`, `0`, or `-1` based on the comparison of `nums[i+1]` and `nums[i]`.
- Implement the KMP algorithm to find occurrences of `pattern` in `numsPattern`.
- **KMP Pre-computation:**
    - Create an LPS (Longest Proper Prefix Suffix) array `lps` of size `m`.
    - Compute the `lps` array for the `pattern`. This takes O(m) time.
- **KMP Search:**
    - Initialize `count = 0`, text pointer `i = 0`, pattern pointer `j = 0`.
    - While `i < n-1`:
        - If `numsPattern[i] == pattern[j]`, increment both `i` and `j`.
        - If `j` reaches `m`, a match is found. Increment `count`, and update `j` using `lps[j-1]` to continue searching for more matches.
        - If `numsPattern[i] != pattern[j]`, a mismatch occurs. Update `j` to `lps[j-1]` if `j > 0`, otherwise increment `i`.
- Return the final `count`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CountMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.Length, m = pattern.Length;
        int ans = 0;
        for (int i = 0; i < n - m; ++i) {
            int ok = 1;
            for (int k = 0; k < m && ok == 1; ++k) {
                if (f(nums[i + k], nums[i + k + 1]) != pattern[k]) {
                    ok = 0;
                }
            }
            ans += ok;
        }
        return ans;
    }
    private int f(int a, int b) {
        return a == b ? 0 : (a < b ? 1 : -1);
    }
}
```

### Java

```java
class Solution {
public
  int countMatchingSubarrays(int[] nums, int[] pattern) {
    int n = nums.length;
    int m = pattern.length;
    int count = 0;
    for (int i = 0; i <= n - m - 1; i++) {
      boolean flag = true;
      for (int j = 0; j < m; j++) {
        if ((pattern[j] == 1 && nums[i + j + 1] <= nums[i + j]) ||
            (pattern[j] == 0 && nums[i + j + 1] != nums[i + j]) ||
            (pattern[j] == -1 && nums[i + j + 1] >= nums[i + j])) {
          flag = false;
          break;
        }
      }
      if (flag) {
        count++;
      }
    }
    return count;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int countMatchingSubarrays(vector<int> &nums, vector<int> &pattern) {
    int n = nums.size();
    int m = pattern.size();
    int c = 0;
    for (int i = 0; i <= n - m - 1; i++) {
      bool flag = true;
      for (int j = 0; j < m; j++) {
        if ((pattern[j] == 1 && nums[i + j + 1] <= nums[i + j]) ||
            (pattern[j] == 0 && nums[i + j + 1] != nums[i + j]) ||
            (pattern[j] == -1 && nums[i + j + 1] >= nums[i + j])) {
          flag = false;
          break;
        }
      }
      if (flag) {
        c++;
      }
    }
    return c;
  }
};

```

### Python

```python
class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int: n = len(nums) m = len(pattern) count = 0 for i in range(n - m): flag = True for j in range(m): if ((pattern[j] == 1 and nums[i + j + 1] <= nums[i + j]) or (pattern[j] == 0 and nums[i + j + 1] != nums[i + j]) or (pattern[j] == - 1 and nums[i + j + 1] >= nums[i + j])): flag = False break if flag: count += 1 return count

```