Number of subarrays that match a pattern ii

Array Rolling Hash String Matching Hash Function

33.4% acceptance

Feb 25, 2026

169

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_matching_subarrays(nums: Vec<i32>, pattern: Vec<i32>) -> i32 {
    let n = nums.len();
    let m = pattern.len();
    // Convert nums to comparison sequence
    let s: Vec<i32> = (1..n).map(|i| nums[i].cmp(&nums[i-1]) as i32).collect();
    // KMP on s with pattern
    let mut fail = vec![0usize; m];
    let mut k = 0usize;
    for i in 1..m {
      while k > 0 && pattern[k] != pattern[i] { k = fail[k-1]; }
      if pattern[k] == pattern[i] { k += 1; }
      fail[i] = k;
    }
    let mut count = 0;
    k = 0;
    for i in 0..s.len() {
      while k > 0 && pattern[k] != s[i] { k = fail[k-1]; }
      if pattern[k] == s[i] { k += 1; }
      if k == m { count += 1; k = fail[k-1]; }
    }
    count
  }
}