Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Number of Subarrays That Match a Pattern II

Problem (restated)

pattern[j] is -1, 0, or 1 meaning the next value should fall, stay, or rise. Count subarrays of nums whose consecutive differences match the whole pattern. n can be 1e6, so linear time.

Intuition

Turn nums into a sign stream of length n-1. Count how often pattern occurs in that stream. That is KMP with a count (on match, j = lps[j-1] and increment, do not stop).

Approaches

KMP on sign stream

Unverified

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

Idea. text[i] = sign(nums[i+1]-nums[i]). Build LPS of pattern. Scan text; every time j == m, ans++ and j = lps[j-1].

Walkthrough. nums=[1,2,3,1,2,3], pattern=[1,1] (two rises). Two windows: [1,2,3] twice. Overlapping matches are allowed.

Trade-offs. Naive windows TLE at 1e6. Same KMP as LC 28, counting instead of returning the first index.

Solution

export function countMatchingSubarrays(nums: number[], pattern: number[]): number {
  const text: number[] = [];
  for (let i = 1; i < nums.length; i++) {
    const d = nums[i]! - nums[i - 1]!;
    text.push(d > 0 ? 1 : d < 0 ? -1 : 0);
  }
  const m = pattern.length;
  if (m === 0) return text.length + 1;
  const lps = new Array<number>(m).fill(0);
  let length = 0;
  for (let i = 1; i < m; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  let j = 0, ans = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1]!;
    if (text[i] === pattern[j]) j++;
    if (j === m) {
      ans++;
      j = lps[j - 1]!;
    }
  }
  return ans;
}

export function countMatchingSubarrays(nums: number[], pattern: number[]): number {
  const text: number[] = [];
  for (let i = 1; i < nums.length; i++) {
    const d = nums[i]! - nums[i - 1]!;
    text.push(d > 0 ? 1 : d < 0 ? -1 : 0);
  }
  const m = pattern.length;
  if (m === 0) return text.length + 1;
  const lps = new Array<number>(m).fill(0);
  let length = 0;
  for (let i = 1; i < m; i++) {
    while (length > 0 && pattern[i] !== pattern[length]) length = lps[length - 1]!;
    if (pattern[i] === pattern[length]) length++;
    lps[i] = length;
  }
  let j = 0, ans = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = lps[j - 1]!;
    if (text[i] === pattern[j]) j++;
    if (j === m) {
      ans++;
      j = lps[j - 1]!;
    }
  }
  return ans;
}

Template connection

KMP exact match on a derived alphabet {-1,0,1}. Count-all variant of LC 28.

Reflection

The text is the sign of each consecutive difference. KMP searches the pattern’s signs in that text. An equal difference is sign 0.
When j reaches the pattern length, increment the count and set j = lps[j - 1]. That keeps overlapping matches.
A pattern of one difference counts how often that sign appears. A text shorter than the pattern is 0.