3036. Number of Subarrays That Match a Pattern II

Problem Description

You're given an integer array nums indexed from 0 to n-1, and another integer array pattern indexed from 0 to m-1, which contains only the integers -1, 0, and 1. The task is to find the count of subarrays in nums of size m + 1 that match the pattern. A subarray nums[i..j] matches the pattern if, for each 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.

Intuition

To find the matching subarrays efficiently, we first transform the nums array into a new array s that describes the relationship between consecutive elements using the same -1, 0, and 1 notation:

• s.append(1) if nums[i] > nums[i-1]
• s.append(0) if nums[i] == nums[i-1]
• s.append(-1) if nums[i] < nums[i-1]

This transformed array s captures the "pattern" of the nums array. We then perform pattern matching to find all occurrences of the pattern within the transformed array s. The pattern matching problem is similar to finding a substring in a string, which can be efficiently solved using the KMP (Knuth–Morris–Pratt) algorithm.

The partial function computes the longest proper prefix array (pi) which is also a suffix for all prefixes of pat. This array pi is used to avoid unnecessary comparisons during the pattern searching phase.

The match function uses the KMP algorithm with the computed pi from the partial function to find all matches of pattern within transformed array s. For each position in s, it tries to extend the matching. If a mismatch happens, it uses the pi array to skip characters in pat that are known to match already.

Finally, the count of matching subarrays of nums is the number of times the pattern is found in string s, which is determined by the length of the list of indices where matches are found (len(match(s, pattern))).

Solution Approach

The solution is implemented using the Knuth–Morris–Pratt (KMP) algorithm, which is a string searching (or substring searching) algorithm that improves upon the naive approach by avoiding unnecessary comparisons. Let's break down the implementation:

1. Transformation: Before applying the KMP algorithm, we transform the nums array into an array s as described previously, indicating the relationship {-1, 0, 1} between consecutive elements. This allows us to match the pattern against this transformed array instead of directly against nums.

2. Partial Match Table (also known as Prefix function): The partial function generates the longest prefix table for the pattern. This table, denoted as pi, will later be used to determine the next state in the search algorithm without re-inspecting the characters that have already been matched. The table is built progressively by comparing the pattern with itself.

   The partial function iterates over the pattern, maintaining a length (g) of the longest proper prefix that is also a suffix. Whenever a mismatch occurs (s[g] != s[i]), the algorithm finds the next best candidate for the longest prefix by referring to pi[g - 1], which stores the length of the best prefix for the substring ending before g.

3. Pattern Matching: The match function does the actual pattern matching using the table generated from partial and returns the starting indices of all subarrays of s that match the pattern.

   The function iterates over the transformed array s, and for each index, it tries to extend the current match. If a mismatch happens, instead of starting the match from the beginning, it uses the previously computed prefix table to skip a few characters and start matching from a position where the previous pattern has already matched, as indicated by pi[g-1]. When a full match of the pattern is found, the end index is added to the idx list.

4. Counting Matches: The solution class Solution method countMatchingSubarrays makes use of the transformation and match function to compute the final result. It constructs the transformed array s, finds all matches using match(s, pattern), and then returns the number of indices where matches begin, which is the count of matching subarrays.

By using the KMP algorithm, the solution avoids re-comparing characters that have been compared previously, reducing the time complexity from O(n*m) for the naive pattern matching approach to O(n+m), where n is the length of the nums array and m is the length of the pattern.

Below is the code fragment for generating the pi array (partial function) and for performing the KMP-based search (match function):

1def partial(s):
2    g, pi = 0, [0] * len(s)
3    for i in range(1, len(s)):
4        while g and (s[g] != s[i]):
5            g = pi[g - 1]
6        pi[i] = g = g + (s[g] == s[i])
7    return pi
8
9def match(s, pat):
10    pi = partial(pat)
11    g, idx = 0, []
12    for i in range(len(s)):
13        while g and pat[g] != s[i]:
14            g = pi[g - 1]
15        g += pat[g] == s[i]
16        if g == len(pi):
17            idx.append(i + 1 - g)
18            g = pi[g - 1]
19    return idx

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose we have: nums = [1, 2, 3, 2, 1, 2, 3] pattern = [-1, 1, -1]

With these inputs, our goal is to find out how many subarrays of nums of size 4 (m + 1, where m is the length of pattern) match the pattern. The pattern of -1, 1, -1 indicates that we're looking for subarrays where the first element is greater than the second, the second is less than the third, and the third is greater than the fourth.

1. Transformation: First, we transform nums into the array s to capture the "pattern" between consecutive elements: s = [] (initialize as empty)

   • Examine elements in nums: (2 > 1) so s.append(1)
   • Examine elements in nums: (3 > 2) so s.append(1)
   • Examine elements in nums: (2 < 3) so s.append(-1)
   • Examine elements in nums: (1 < 2) so s.append(-1)
   • Examine elements in nums: (2 > 1) so s.append(1)
   • Examine elements in nums: (3 > 2) so s.append(1)

   So, s = [1, 1, -1, -1, 1, 1]

2. Partial Match Table (Prefix function): Generate the prefix table for pattern: pat = [-1, 1, -1] pi = [0, 0, 0] (initialize pi array)

   • Set g = 0, and i = 1
   • Since there is no proper prefix which matches suffix, pi stays [0, 0, 0]

3. Pattern Matching: Perform KMP-based search to find pattern -1, 1, -1 in s:

   • Using pi, iterate through s and search for pattern
   • Matches are found at indices where the entire subarray [1, -1, 1] in s aligns with [-1, 1, -1] (after transformation accounting for the indices)
   • Two matches occur in s at indices 2, 4

4. Counting Matches:

   • Since there are two matching subarrays that start at indices 2 and 4 in s, the count of matching subarrays in nums is 2.

Therefore, for the given nums and pattern, there are two subarrays of nums that match the pattern. This demonstrates how the solution approach applies the KMP algorithm to efficiently find the count of matching subarrays.

Solution Implementation

Time and Space Complexity

The partial function has a time complexity of O(n) where n is the length of the pattern string pat. It runs a loop through the pattern, and even though there's a nested while loop, it does not lead to an extra multiplication of complexity since the g variable is always incremented and decremented in a way that it doesn't repeat comparisons (KMP algorithm property).

The space complexity for the partial function is O(m) where m is the length of the pattern string pat, that's used for the prefix array pi.

The match function has a time complexity of O(n + m) where n is the length of the string s and m is the length of the pattern pat. This accounts for the KMP matching which goes through the string s once and uses the failure function (prefix function) generated from the pattern pat. It doesn't compare each character of s with all characters of pat due to the preprocessing done in the partial function.

The space complexity for the match function is again O(m) which is mainly due to the space taken by the partial match table (pi array). The list idx that contains indices can, in the worst case, be O(n) if every index is a match. Therefore, the overall space complexity might be considered O(n + m) if we count the space for the indices list.

The string_find function shares the same time complexity as match being O(n + m) for the same reasons and space complexity of O(m) since it only returns a boolean and does not store the match indices.

The countMatchingSubarrays method from the Solution class has a time complexity which is essentially O(n + m) where n is the length of the nums list and m is the length of the pattern list. The initial loop to transform nums into a difference pattern adds an O(n) step, but this does not change the overall O(n + m) complexity.

The space complexity for the countMatchingSubarrays method is O(n + m) since it stores transformed list s along with the space required for the match function.

Learn more about how to find time and space complexity quickly using problem constraints.