Number of Subarrays That Match a Pattern II

Hard
1766.

Number of Subarrays That Match a Pattern II

Number of Subarrays That Match a Pattern II is a hard coding problem on arrays, rolling hash and string matching, asked in Amazon interviews.

You are given an integer array nums of length n and an array pattern of length m whose entries are each -1, 0 or 1.

A subarray nums[i..i+m] (of size m + 1) matches the pattern when, for every k from 0 to m - 1:

  • 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 number of subarrays of nums that match pattern. This is the large version: n can reach a million, so checking every start against the whole pattern is too slow.

Example 1

Input
nums = [1,2,3,4,5,6], pattern = [1,1]
Output
4
Explanation
Every window of three consecutive values is strictly increasing.

Example 2

Input
nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output
2
Explanation
[1,4,4,1] and [3,5,5,3] match.

Example 3

Input
nums = [3,1,3,1,3,1,3], pattern = [-1,1,-1]
Output
2
Explanation
The matches start at indices 0 and 2 and overlap — both count.

Constraints

  • 2 <= n == nums.length <= 10^6
  • 1 <= nums[i] <= 10^9
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} pattern
 * @return {number}
 */
var countMatchingSubarrays = function(nums, pattern) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Subarrays That Match a Pattern II — Solution

Number of Subarrays That Match a Pattern II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Subarrays That Match a Pattern II is a hard coding problem on arrays, rolling hash and string matching, asked in Amazon interviews.

  • Difficulty: Hard
  • Topics: Arrays, Rolling Hash, String Matching
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums of length n and an array pattern of length m whose entries are each -1, 0 or 1.

A subarray nums[i..i+m] (of size m + 1) matches the pattern when, for every k from 0 to m - 1:

  • 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 number of subarrays of nums that match pattern. This is the large version: n can reach a million, so checking every start against the whole pattern is too slow.

Example 1

Input: nums = [1,2,3,4,5,6], pattern = [1,1]
Output: 4
Explanation: Every window of three consecutive values is strictly increasing.

Example 2

Input: nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output: 2
Explanation: [1,4,4,1] and [3,5,5,3] match.

Example 3

Input: nums = [3,1,3,1,3,1,3], pattern = [-1,1,-1]
Output: 2
Explanation: The matches start at indices 0 and 2 and overlap — both count.

Constraints

  • 2 <= n == nums.length <= 10^6
  • 1 <= nums[i] <= 10^9
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1

Hints for Number of Subarrays That Match a Pattern II

  1. Hint 1

    Turn nums into a sequence of n - 1 signs: 1, 0 or -1 for each neighbouring pair.

  2. Hint 2

    A subarray matches exactly when pattern appears in that sign sequence starting at the subarray's first index.

  3. Hint 3

    Count the (possibly overlapping) occurrences of pattern in the sign sequence with a linear string-matching algorithm such as KMP or the Z-function.

How to solve Number of Subarrays That Match a Pattern II

Comparing neighbours turns the array into a 'text' of signs over the alphabet {-1, 0, 1}. The question becomes: how many times does pattern occur in that text? That is classic string matching, solvable in linear time with KMP.

Approach

  1. Build the KMP failure table of pattern: fail[i] is the length of the longest proper border of pattern[0..i].
  2. Scan i = 0 .. n - 2, computing the sign s of nums[i+1] versus nums[i] on the fly.
  3. Keep j, the length of the pattern prefix matched so far: while j > 0 and s != pattern[j], fall back to fail[j - 1]; if s == pattern[j], advance j.
  4. When j == m, count a match and continue from fail[m - 1] so overlapping matches are found.

Why it works

Subarray nums[i..i+m] matches iff signs i .. i+m-1 equal pattern, so the matches are in one-to-one correspondence with occurrences of pattern in the sign text. KMP finds every occurrence, overlapping ones included, and its fallback pointer only moves forward overall, so the scan is linear.

Complexity

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

Pitfalls

  • After a full match fall back to fail[m - 1] rather than resetting to 0, or overlapping matches like Example 3 are missed.
  • The text has n - 1 symbols, not n.
  • Use comparisons for the sign rather than a subtraction that could overflow in other variants of the problem.

Reference solution

Python

from typing import List

def countMatchingSubarrays(nums: List[int], pattern: List[int]) -> int:
    m = len(pattern)
    fail = [0] * m
    j = 0
    for i in range(1, m):
        while j and pattern[i] != pattern[j]:
            j = fail[j - 1]
        if pattern[i] == pattern[j]:
            j += 1
        fail[i] = j
    res = j = 0
    for i in range(len(nums) - 1):
        a, b = nums[i], nums[i + 1]
        s = (b > a) - (b < a)
        while j and s != pattern[j]:
            j = fail[j - 1]
        if s == pattern[j]:
            j += 1
        if j == m:
            res += 1
            j = fail[j - 1]
    return res

Java

public static int countMatchingSubarrays(int[] nums, int[] pattern) {
    int m = pattern.length;
    int[] fail = new int[m];
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) j = fail[j - 1];
        if (pattern[i] == pattern[j]) j++;
        fail[i] = j;
    }
    int res = 0;
    j = 0;
    for (int t = 0; t + 1 < nums.length; t++) {
        int s = Integer.compare(nums[t + 1], nums[t]);
        while (j > 0 && s != pattern[j]) j = fail[j - 1];
        if (s == pattern[j]) j++;
        if (j == m) { res++; j = fail[j - 1]; }
    }
    return res;
}

C++

int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
    int m = pattern.size();
    vector<int> fail(m, 0);
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && pattern[i] != pattern[j]) j = fail[j - 1];
        if (pattern[i] == pattern[j]) j++;
        fail[i] = j;
    }
    int res = 0;
    j = 0;
    for (int t = 0; t + 1 < (int) nums.size(); t++) {
        int s = (nums[t + 1] > nums[t]) - (nums[t + 1] < nums[t]);
        while (j > 0 && s != pattern[j]) j = fail[j - 1];
        if (s == pattern[j]) j++;
        if (j == m) { res++; j = fail[j - 1]; }
    }
    return res;
}

JavaScript

var countMatchingSubarrays = function(nums, pattern) {
    var m = pattern.length;
    var fail = new Array(m).fill(0);
    var j = 0;
    for (var i = 1; i < m; i++) {
        while (j > 0 && pattern[i] !== pattern[j]) j = fail[j - 1];
        if (pattern[i] === pattern[j]) j++;
        fail[i] = j;
    }
    var res = 0;
    j = 0;
    for (var t = 0; t + 1 < nums.length; t++) {
        var a = nums[t], b = nums[t + 1];
        var s = b > a ? 1 : (b === a ? 0 : -1);
        while (j > 0 && s !== pattern[j]) j = fail[j - 1];
        if (s === pattern[j]) j++;
        if (j === m) { res++; j = fail[j - 1]; }
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays