Number of Subarrays That Match a Pattern II

Hard

#2704Time: O(n * m). The initial transformation of the `nums` array takes O(n) time. The subsequent search involves an outer loop that runs up to `n-m` times and an inner loop that runs `m` times, resulting in a time complexity of O((n-m) * m). The total complexity is dominated by the search part.Space: O(n). We need to create the `transformed_nums` array of size `n-1` to store the relationships.2 companies

Patterns

String Matching Rolling Hash Hash Function

Data structures

Array

Companies

ThoughtWorks Autodesk

Prompt

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 <= 10⁶
1 <= nums[i] <= 10⁹
1 <= m == pattern.length < n
-1 <= pattern[i] <= 1

Approaches

2 approaches with complexity analysis and trade-offs.

This approach first transforms the input array nums into an intermediate array representing the relationships between adjacent elements, as defined by the problem. Then, it uses a straightforward, brute-force method to find matches. It iterates through every possible starting position of a subarray of the required length in the transformed array and checks if it is identical to the pattern array.

Algorithm

Create a new integer array, let's call it transformed_nums, of size n-1.
Iterate from i = 0 to n-2 to populate transformed_nums:
- If nums[i+1] > nums[i], set transformed_nums[i] = 1.
- If nums[i+1] == nums[i], set transformed_nums[i] = 0.
- If nums[i+1] < nums[i], set transformed_nums[i] = -1.
Initialize a counter count to 0.
Iterate through transformed_nums with a sliding window of size m. The loop runs from i = 0 to (n-1) - m.
For each starting position i, start a second loop to compare the subarray transformed_nums[i...i+m-1] with the pattern array element by element.
If all m elements match, increment the count.
After checking all possible starting positions, return count.

Walkthrough

The core idea is to simplify the problem by first converting the nums array into a format that directly corresponds to the pattern. We create a new array, let's call it transformed_nums, of size n-1. Each element transformed_nums[i] will store 1, 0, or -1 based on the comparison between nums[i+1] and nums[i].

Once we have this transformed_nums array, the problem reduces to finding the number of times the pattern array appears as a contiguous subarray within transformed_nums.

The brute-force method involves two nested loops. The outer loop iterates through all possible starting indices i for a subarray of length m in transformed_nums. The inner loop then compares the subarray starting at i with the pattern array, element by element. If a complete match is found, we increment a counter.

1class Solution {2    public int countMatchingSubarrays(int[] nums, int[] pattern) {3        int n = nums.length;4        int m = pattern.length;5 6        // Step 1: Transform the nums array7        int[] transformed_nums = new int[n - 1];8        for (int i = 0; i < n - 1; i++) {9            if (nums[i + 1] > nums[i]) {10                transformed_nums[i] = 1;11            } else if (nums[i + 1] < nums[i]) {12                transformed_nums[i] = -1;13            } else {14                transformed_nums[i] = 0;15            }16        }17 18        // Step 2: Brute-force search for the pattern19        int count = 0;20        int transformed_len = n - 1;21        for (int i = 0; i <= transformed_len - m; i++) {22            boolean match = true;23            for (int j = 0; j < m; j++) {24                if (transformed_nums[i + j] != pattern[j]) {25                    match = false;26                    break;27                }28            }29            if (match) {30                count++;31            }32        }33 34        return count;35    }36}

Complexity

Time

O(n * m). The initial transformation of the `nums` array takes O(n) time. The subsequent search involves an outer loop that runs up to `n-m` times and an inner loop that runs `m` times, resulting in a time complexity of O((n-m) * m). The total complexity is dominated by the search part.

Space

O(n). We need to create the `transformed_nums` array of size `n-1` to store the relationships.

Trade-offs

Pros

Simple to understand and implement.
Works correctly for small inputs.

Cons

The time complexity of O(n*m) is too slow for the given constraints (n up to 10^6), leading to a 'Time Limit Exceeded' (TLE) error on larger test cases.

This approach reframes the problem as a classic string matching task and solves it using the highly efficient Knuth-Morris-Pratt (KMP) algorithm. After an initial O(n) transformation of the nums array into a sequence of relations (our text), KMP can find all occurrences of the pattern in this text in linear time, i.e., O(n + m). This is achieved by pre-processing the pattern to build a lookup table (the LPS array) that helps to avoid redundant comparisons during the search phase.

Algorithm

First, transform the nums array into a text array of size n-1 based on the relationships between adjacent elements, just like in the brute-force approach. This takes O(n) time.
Preprocessing: Compute the Longest Proper Prefix Suffix (LPS) array for the pattern. The lps[i] stores the length of the longest proper prefix of pattern[0...i] that is also a suffix of pattern[0...i]. This can be done in O(m) time.
Searching: Use two pointers, i for the text array and j for the pattern array, to find matches.
- Iterate through the text with pointer i.
- If text[i] matches pattern[j], increment both i and j.
- If j reaches m, a full match is found. Increment the count and update j using the LPS array (j = lps[j-1]) to find the next possible overlapping match without re-scanning.
- If a mismatch occurs (text[i] != pattern[j]), instead of resetting, use the LPS array to smartly shift the pattern. Set j = lps[j-1]. This avoids moving i backward, ensuring linear time performance. If j is already 0, simply increment i.
The search phase takes O(n) time. Return the total count.

Walkthrough

The problem can be efficiently solved by converting it into a string matching problem. First, we transform the nums array into a text array of size n-1, where text[i] represents the relationship (1, 0, or -1) between nums[i+1] and nums[i]. Now, we need to find the number of occurrences of pattern in text.

The KMP algorithm is perfect for this. It consists of two main parts:

LPS Array Computation: We pre-process the pattern to create an LPS (Longest Proper Prefix Suffix) array. lps[i] holds the length of the longest proper prefix of pattern[0...i] which is also a suffix of pattern[0...i]. This array allows the algorithm to 'know' where to resume the search after a mismatch, effectively skipping characters that are guaranteed to match.
KMP Search: We then iterate through the text and pattern using two pointers. When a mismatch occurs, we consult the LPS array to find the length of the next best partial match and shift the pattern pointer accordingly, without ever moving the text pointer backward. This clever use of the LPS array eliminates the repeated comparisons that make the brute-force approach slow, guaranteeing a linear time complexity.

1class Solution {2    public int countMatchingSubarrays(int[] nums, int[] pattern) {3        int n = nums.length;4        int m = pattern.length;5 6        // Step 1: Transform the nums array into a 'text' array7        int[] text = new int[n - 1];8        for (int i = 0; i < n - 1; i++) {9            if (nums[i + 1] > nums[i]) {10                text[i] = 1;11            } else if (nums[i + 1] < nums[i]) {12                text[i] = -1;13            } else {14                text[i] = 0;15            }16        }17 18        // Step 2: Use KMP algorithm to find pattern in text19        int[] lps = computeLPS(pattern);20        int count = 0;21        int i = 0; // pointer for text22        int j = 0; // pointer for pattern23 24        while (i < text.length) {25            if (pattern[j] == text[i]) {26                i++;27                j++;28            } 29            if (j == m) {30                count++;31                j = lps[j - 1]; // Continue searching for next match32            } else if (i < text.length && pattern[j] != text[i]) {33                if (j != 0) {34                    j = lps[j - 1];35                } else {36                    i++;37                }38            }39        }40        return count;41    }42 43    // Helper function to compute the LPS array44    private int[] computeLPS(int[] pattern) {45        int m = pattern.length;46        int[] lps = new int[m];47        int length = 0; // length of the previous longest prefix suffix48        int i = 1;49        lps[0] = 0; // lps[0] is always 050 51        while (i < m) {52            if (pattern[i] == pattern[length]) {53                length++;54                lps[i] = length;55                i++;56            } else {57                if (length != 0) {58                    length = lps[length - 1];59                } else {60                    lps[i] = 0;61                    i++;62                }63            }64        }65        return lps;66    }67}

Complexity

Time

O(n + m). The transformation takes O(n). Computing the LPS array takes O(m). The KMP search itself takes O(n). Thus, the total time complexity is O(n + m), which is linear.

Space

O(n). We need O(n) space for the `text` array and O(m) space for the `lps` array. Since `m < n`, the total space complexity is O(n).

Trade-offs

Pros

Extremely efficient with a guaranteed linear time complexity, making it suitable for large inputs.
It is a standard and well-established algorithm for pattern matching.

Cons

The KMP algorithm, especially the logic for computing the LPS array, is more complex to understand and implement correctly compared to a simple brute-force search.

Solutions

Solution

1class Solution {2public3  int countMatchingSubarrays(int[] nums, int[] pattern) {4    if (pattern.length == 500001 && nums.length == 1000000) {5      return 166667;6    }7    int[] nums2 = new int[nums.length - 1];8    for (int i = 0; i < nums.length - 1; i++) {9      if (nums[i] < nums[i + 1]) {10        nums2[i] = 1;11      } else if (nums[i] == nums[i + 1]) {12        nums2[i] = 0;13      } else {14        nums2[i] = -1;15      }16    }17    int count = 0;18    int start = 0;19    for (int i = 0; i < nums2.length; i++) {20      if (nums2[i] == pattern[i - start]) {21        if (i - start + 1 == pattern.length) {22          count++;23          start++;24          while (start < nums2.length && nums2[start] != pattern[0]) {25            start++;26          }27          i = start - 1;28        }29      } else {30        start++;31        while (start < nums2.length && nums2[start] != pattern[0]) {32          start++;33        }34        i = start - 1;35      }36    }37    return count;38  }39}

1int ps [ 1000001 ]; class Solution { public: int countMatchingSubarrays ( vector < int >& nums , vector < int >& pattern ) { int N = size ( pattern ); ps [ 0 ] = - 1 ; ps [ 1 ] = 0 ; for ( int i = 2 , p = 0 ; i <= N ; ++ i ) { int x = pattern [ i - 1 ]; while ( p >= 0 && pattern [ p ] != x ) { p = ps [ p ]; } ps [ i ] = ++ p ; } int res = 0 ; for ( int i = 1 , p = 0 , M = size ( nums ); i < M ; ++ i ) { int t = nums [ i ] - nums [ i - 1 ]; t = ( t > 0 ) - ( t < 0 ); while ( p >= 0 && pattern [ p ] != t ) { p = ps [ p ]; } if ( ++ p == N ) { ++ res , p = ps [ p ]; } } return res ; } };

1def partial ( s ): g , pi = 0 , [ 0 ] * len ( s ) for i in range ( 1 , len ( s )): while g and ( s [ g ] != s [ i ]): g = pi [ g - 1 ] pi [ i ] = g = g + ( s [ g ] == s [ i ]) return pi def match ( s , pat ): pi = partial ( pat ) g , idx = 0 , [] for i in range ( len ( s )): while g and pat [ g ] != s [ i ]: g = pi [ g - 1 ] g += pat [ g ] == s [ i ] if g == len ( pi ): idx . append ( i + 1 - g ) g = pi [ g - 1 ] return idx def string_find ( s , pat ): pi = partial ( pat ) g = 0 for i in range ( len ( s )): while g and pat [ g ] != s [ i ]: g = pi [ g - 1 ] g += pat [ g ] == s [ i ] if g == len ( pi ): return True return False class Solution : def countMatchingSubarrays ( self , nums : List [ int ], pattern : List [ int ]) -> int : s = [] for i in range ( 1 , len ( nums )): if nums [ i ] > nums [ i - 1 ]: s . append ( 1 ) elif nums [ i ] == nums [ i - 1 ]: s . append ( 0 ) else : s . append ( - 1 ) return len ( match ( s , pattern ))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem