3036

3036. Number of Subarrays That Match a Pattern II (Hard)

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

Similar Questions:

• Match Substring After Replacement (Hard)

Hints:

• Create a second array nums2 such that nums2[i] = 1 if nums[i + 1] > nums[i], nums2[i] = 0 if nums[i + 1] == nums[i], and nums2[i] = -1 if nums[i + 1] < nums[i].
• The problem becomes: “Count the number of subarrays in nums2 that are equal to pattern.
• Use Knuth-Morris-Pratt or Z-Function algorithms.

Solution 1. KMP

Firstly, turn the array A into a string s with a, b, c (meaning -1, 0, 1) denoting the relative order of its consecutive letters.

For example, A = [1,4,4,1,3,5,5,3], then s = "cbaccba".

Secondly, convert pattern array into a string of a, b, c as well.

For example, P = [1,0,-1], then p = "cba".

Lastly, count the number of occurrence of p in s. We can use KMP to do this in O(M + N) time.

// OJ: https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-ii
// Author: github.com/lzl124631x
// Time: O(M + N)
// Space: O(M + N)
class Solution {
    vector<int> getLps(string &s) {
        int N = s.size(), i = 0;
        vector<int> lps(N); // lps[0] is always 0
        for (int j = 1; j < N; ++j) {
            while (i > 0 && s[i] != s[j]) i = lps[i - 1]; // when s[i] can't match s[j], keep moving `i` backwards to `lps[i-1]`
            i += s[i] == s[j]; // Move `i` if s[j] matches s[i]
            lps[j] = i; // Assign the matched length to lps[j]
        }
        return lps;
    }
    int KMPCount(string s, string t) {
        if (t.empty()) return 0;
        int M = s.size(), N = t.size(), i = 0, j = 0, ans = 0;
        auto lps = getLps(t);
        while (i < M) {
            if (s[i] == t[j]) {
                ++i;
                ++j;
                if (j == N) {
                    ++ans;
                    j = lps[j - 1]; // Full match found. Move `j` back to `lps[j-1]` to skip matched prefix
                }
            } else {
                if (j) j = lps[j - 1];
                else ++i;
            }
        }
        return ans;
    }
public:
    int countMatchingSubarrays(vector<int>& A, vector<int>& P) {
        int N = A.size(), M = P.size();
        string s, p;
        for (int i = 1; i < N; ++i) {
            s.push_back(A[i] > A[i - 1] ? 'a' : (A[i] == A[i - 1] ? 'b' : 'c'));
        }
        for (auto &n : P) {
            p.push_back(n == 1 ? 'a' : (n == 0 ? 'b' : 'c'));
        }
        return KMPCount(s, p);
    }
};