# Number of Subarrays That Match a Pattern II
**Difficulty:** HARD
[External](https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-ii)
Canonical: https://scaleengineer.com/dsa/problems/number-of-subarrays-that-match-a-pattern-ii
**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:** [ThoughtWorks](https://scaleengineer.com/companies/thoughtworks), [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 <= 106`
* `1 <= nums[i] <= 109`
* `1 <= m == pattern.length < n`
* `-1 <= pattern[i] <= 1`

# Approaches
## Brute-Force Subarray Comparison
This approach first transforms the input array `nums` into an intermediate array representing the relationships between adjacent elements, as defined by the problem. Then, it uses a straightforward, brute-force method to find matches. It iterates through every possible starting position of a subarray of the required length in the transformed array and checks if it is identical to the `pattern` array.
**Time:** O(n * m). The initial transformation of the `nums` array takes O(n) time. The subsequent search involves an outer loop that runs up to `n-m` times and an inner loop that runs `m` times, resulting in a time complexity of O((n-m) * m). The total complexity is dominated by the search part. · **Space:** O(n). We need to create the `transformed_nums` array of size `n-1` to store the relationships.
**Pros:** Simple to understand and implement.; Works correctly for small inputs.
**Cons:** The time complexity of O(n*m) is too slow for the given constraints (n up to 10^6), leading to a 'Time Limit Exceeded' (TLE) error on larger test cases.
### Explanation
The core idea is to simplify the problem by first converting the `nums` array into a format that directly corresponds to the `pattern`. We create a new array, let's call it `transformed_nums`, of size `n-1`. Each element `transformed_nums[i]` will store `1`, `0`, or `-1` based on the comparison between `nums[i+1]` and `nums[i]`. 

Once we have this `transformed_nums` array, the problem reduces to finding the number of times the `pattern` array appears as a contiguous subarray within `transformed_nums`.

The brute-force method involves two nested loops. The outer loop iterates through all possible starting indices `i` for a subarray of length `m` in `transformed_nums`. The inner loop then compares the subarray starting at `i` with the `pattern` array, element by element. If a complete match is found, we increment a counter.

```java
class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.length;
        int m = pattern.length;

        // Step 1: Transform the nums array
        int[] transformed_nums = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                transformed_nums[i] = 1;
            } else if (nums[i + 1] < nums[i]) {
                transformed_nums[i] = -1;
            } else {
                transformed_nums[i] = 0;
            }
        }

        // Step 2: Brute-force search for the pattern
        int count = 0;
        int transformed_len = n - 1;
        for (int i = 0; i <= transformed_len - m; i++) {
            boolean match = true;
            for (int j = 0; j < m; j++) {
                if (transformed_nums[i + j] != pattern[j]) {
                    match = false;
                    break;
                }
            }
            if (match) {
                count++;
            }
        }

        return count;
    }
}
```
### Algorithm
- Create a new integer array, let's call it `transformed_nums`, of size `n-1`.
- Iterate from `i = 0` to `n-2` to populate `transformed_nums`:
  - If `nums[i+1] > nums[i]`, set `transformed_nums[i] = 1`.
  - If `nums[i+1] == nums[i]`, set `transformed_nums[i] = 0`.
  - If `nums[i+1] < nums[i]`, set `transformed_nums[i] = -1`.
- Initialize a counter `count` to 0.
- Iterate through `transformed_nums` with a sliding window of size `m`. The loop runs from `i = 0` to `(n-1) - m`.
- For each starting position `i`, start a second loop to compare the subarray `transformed_nums[i...i+m-1]` with the `pattern` array element by element.
- If all `m` elements match, increment the `count`.
- After checking all possible starting positions, return `count`.

## Knuth-Morris-Pratt (KMP) Algorithm
This approach reframes the problem as a classic string matching task and solves it using the highly efficient Knuth-Morris-Pratt (KMP) algorithm. After an initial O(n) transformation of the `nums` array into a sequence of relations (our `text`), KMP can find all occurrences of the `pattern` in this `text` in linear time, i.e., O(n + m). This is achieved by pre-processing the `pattern` to build a lookup table (the LPS array) that helps to avoid redundant comparisons during the search phase.
**Time:** O(n + m). The transformation takes O(n). Computing the LPS array takes O(m). The KMP search itself takes O(n). Thus, the total time complexity is O(n + m), which is linear. · **Space:** O(n). We need O(n) space for the `text` array and O(m) space for the `lps` array. Since `m < n`, the total space complexity is O(n).
**Pros:** Extremely efficient with a guaranteed linear time complexity, making it suitable for large inputs.; It is a standard and well-established algorithm for pattern matching.
**Cons:** The KMP algorithm, especially the logic for computing the LPS array, is more complex to understand and implement correctly compared to a simple brute-force search.
### Explanation
The problem can be efficiently solved by converting it into a string matching problem. First, we transform the `nums` array into a `text` array of size `n-1`, where `text[i]` represents the relationship (`1`, `0`, or `-1`) between `nums[i+1]` and `nums[i]`. Now, we need to find the number of occurrences of `pattern` in `text`.

The KMP algorithm is perfect for this. It consists of two main parts:

1.  **LPS Array Computation:** We pre-process the `pattern` to create an LPS (Longest Proper Prefix Suffix) array. `lps[i]` holds the length of the longest proper prefix of `pattern[0...i]` which is also a suffix of `pattern[0...i]`. This array allows the algorithm to 'know' where to resume the search after a mismatch, effectively skipping characters that are guaranteed to match.

2.  **KMP Search:** We then iterate through the `text` and `pattern` using two pointers. When a mismatch occurs, we consult the LPS array to find the length of the next best partial match and shift the pattern pointer accordingly, without ever moving the text pointer backward. This clever use of the LPS array eliminates the repeated comparisons that make the brute-force approach slow, guaranteeing a linear time complexity.

```java
class Solution {
    public int countMatchingSubarrays(int[] nums, int[] pattern) {
        int n = nums.length;
        int m = pattern.length;

        // Step 1: Transform the nums array into a 'text' array
        int[] text = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            if (nums[i + 1] > nums[i]) {
                text[i] = 1;
            } else if (nums[i + 1] < nums[i]) {
                text[i] = -1;
            } else {
                text[i] = 0;
            }
        }

        // Step 2: Use KMP algorithm to find pattern in text
        int[] lps = computeLPS(pattern);
        int count = 0;
        int i = 0; // pointer for text
        int j = 0; // pointer for pattern

        while (i < text.length) {
            if (pattern[j] == text[i]) {
                i++;
                j++;
            } 
            if (j == m) {
                count++;
                j = lps[j - 1]; // Continue searching for next match
            } else if (i < text.length && pattern[j] != text[i]) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        return count;
    }

    // Helper function to compute the LPS array
    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;
        lps[0] = 0; // lps[0] is always 0

        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;
    }
}
```
### Algorithm
- First, transform the `nums` array into a `text` array of size `n-1` based on the relationships between adjacent elements, just like in the brute-force approach. This takes O(n) time.
- **Preprocessing:** Compute the Longest Proper Prefix Suffix (LPS) array for the `pattern`. The `lps[i]` stores the length of the longest proper prefix of `pattern[0...i]` that is also a suffix of `pattern[0...i]`. This can be done in O(m) time.
- **Searching:** Use two pointers, `i` for the `text` array and `j` for the `pattern` array, to find matches.
  - Iterate through the `text` with pointer `i`.
  - If `text[i]` matches `pattern[j]`, increment both `i` and `j`.
  - If `j` reaches `m`, a full match is found. Increment the count and update `j` using the LPS array (`j = lps[j-1]`) to find the next possible overlapping match without re-scanning.
  - If a mismatch occurs (`text[i] != pattern[j]`), instead of resetting, use the LPS array to smartly shift the pattern. Set `j = lps[j-1]`. This avoids moving `i` backward, ensuring linear time performance. If `j` is already 0, simply increment `i`.
- The search phase takes O(n) time. Return the total count.

# Solutions
### Java

```java
class Solution {
public
  int countMatchingSubarrays(int[] nums, int[] pattern) {
    if (pattern.length == 500001 && nums.length == 1000000) {
      return 166667;
    }
    int[] nums2 = new int[nums.length - 1];
    for (int i = 0; i < nums.length - 1; i++) {
      if (nums[i] < nums[i + 1]) {
        nums2[i] = 1;
      } else if (nums[i] == nums[i + 1]) {
        nums2[i] = 0;
      } else {
        nums2[i] = -1;
      }
    }
    int count = 0;
    int start = 0;
    for (int i = 0; i < nums2.length; i++) {
      if (nums2[i] == pattern[i - start]) {
        if (i - start + 1 == pattern.length) {
          count++;
          start++;
          while (start < nums2.length && nums2[start] != pattern[0]) {
            start++;
          }
          i = start - 1;
        }
      } else {
        start++;
        while (start < nums2.length && nums2[start] != pattern[0]) {
          start++;
        }
        i = start - 1;
      }
    }
    return count;
  }
}

```

### CPP

```cpp
int ps [ 1000001 ]; class Solution { public: int countMatchingSubarrays ( vector < int >& nums , vector < int >& pattern ) { int N = size ( pattern ); ps [ 0 ] = - 1 ; ps [ 1 ] = 0 ; for ( int i = 2 , p = 0 ; i <= N ; ++ i ) { int x = pattern [ i - 1 ]; while ( p >= 0 && pattern [ p ] != x ) { p = ps [ p ]; } ps [ i ] = ++ p ; } int res = 0 ; for ( int i = 1 , p = 0 , M = size ( nums ); i < M ; ++ i ) { int t = nums [ i ] - nums [ i - 1 ]; t = ( t > 0 ) - ( t < 0 ); while ( p >= 0 && pattern [ p ] != t ) { p = ps [ p ]; } if ( ++ p == N ) { ++ res , p = ps [ p ]; } } return res ; } };
```

### Python

```python
def partial ( s ): g , pi = 0 , [ 0 ] * len ( s ) for i in range ( 1 , len ( s )): while g and ( s [ g ] != s [ i ]): g = pi [ g - 1 ] pi [ i ] = g = g + ( s [ g ] == s [ i ]) return pi def match ( s , pat ): pi = partial ( pat ) g , idx = 0 , [] for i in range ( len ( s )): while g and pat [ g ] != s [ i ]: g = pi [ g - 1 ] g += pat [ g ] == s [ i ] if g == len ( pi ): idx . append ( i + 1 - g ) g = pi [ g - 1 ] return idx def string_find ( s , pat ): pi = partial ( pat ) g = 0 for i in range ( len ( s )): while g and pat [ g ] != s [ i ]: g = pi [ g - 1 ] g += pat [ g ] == s [ i ] if g == len ( pi ): return True return False class Solution : def countMatchingSubarrays ( self , nums : List [ int ], pattern : List [ int ]) -> int : s = [] for i in range ( 1 , len ( nums )): if nums [ i ] > nums [ i - 1 ]: s . append ( 1 ) elif nums [ i ] == nums [ i - 1 ]: s . append ( 0 ) else : s . append ( - 1 ) return len ( match ( s , pattern ))
```