3034. Number of Subarrays That Match a Pattern I

MediumArrayString MatchingHash FunctionRolling Hash
Leetcode Link

Problem Description

In this problem, you're provided with two arrays, nums and pattern. The nums array is a basic integer array that begins with an index of 0 and has a size "n". The pattern array is also 0-indexed and contains a series of m integers that can only be -1, 0, or 1.

Your goal is to determine how many subarrays of nums match the pattern array. A subarray from nums is considered a match if for each element pattern[k] within the pattern array the relationship between the subsequent elements in the nums subarray follows the rule defined by the value of pattern[k]: If pattern[k] equals 1, then the element next in line in the nums subarray must be greater than its predecessor. If it's 0, they must be equal. And if it's -1, the next element must be less than its predecessor.

The size of the subarray you are looking for in the nums array is always m + 1, which corresponds to the pattern length plus one, because you're comparing adjacent elements to be matched against the elements of pattern. The final answer should be the total number of such subarrays found in nums.

Intuition

To approach this problem, intuitively, you can think of sliding a window of size m + 1 across the nums array and compare each slice of the array to the pattern. For every position in nums where you place the starting point of your sliding window, you check if the differences between adjacent elements in the nums subarray line up with the specified pattern in pattern. This involves a direct translation of the pattern's -1, 0, and 1 into "less than", "equal to" and "greater than" respectively, which can be done using straightforward comparisons.

One way to facilitate this process is to define a helper function that encapsulates the comparison logic: it takes two numbers (adjacent elements from the nums array) and returns 0 if they're equal, 1 if the first is less than the second, or -1 if the first is greater than the second. This aligns perfectly with the elements of the pattern.

The main function iterates through the nums array by index but stops early to avoid out-of-bounds errors, specifically it stops when there are only m elements left on the right side. In each iteration, it uses the helper function to compare adjacent elements in the currently considered subarray with the corresponding pattern elements. If all the comparisons for a given subarray meet the pattern, that counts as one match. Keep a tally, and the result is the total number of such matches for the entire nums array.

Solution Approach

The solution provided is a straightforward brute force enumeration that involves iterating through the nums array and comparing slices of it against the pattern. To implement this approach, the solution does not depend on any special data structures or advanced algorithms. It relies on the use of a nested loop to access subarrays and the built-in comparison operators <, ==, and > to check against the pattern.

For the enumeration, the outer loop runs through the indices of the nums array, starting from 0 and going up to len(nums) - len(pattern) to ensure that at each step there are enough elements left in the array to form a complete subarray of length m + 1.

Within the outer loop, a comprehension is used with the all function, which returns True only if all elements in the iterable are True. This comprehension iterates over the pattern using enumerate, which provides both the index k and the value p(pattern element) together.

At each iteration of this comprehension, the helper function f is used which takes two arguments from the nums subarray at the positions i + k and i + k + 1 and returns a comparison result (-1, 0, or 1). If this result matches the current element p of the pattern, the subarray can still be considered a match for the pattern. If any comparison fails, that subarray does not match the pattern, and all will return False.

If all does return True, meaning the current subarray does match the pattern, the ans variable is incremented by one. After the outer loop finishes, ans, which contains the count of all matching subarrays, is returned as the final answer.

This solution's time complexity is O(n * m), where n is the length of the nums array and m is the length of the pattern, as it entails checking each subarray of size m + 1 in a linear manner against the pattern. No extra space is used outside of the input and variables for counting, so the space complexity is O(1).

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which two pointer techniques do you use to check if a string is a palindrome?

Example Walkthrough

Let's consider the nums array as [5, 3, 4, 2, 1, 3] and the pattern array as [1, -1, 0]. We need to find subarrays of length m + 1 = 4 that match the pattern where 1 in the pattern dictates the next number should be greater, -1 means the next number should be lesser, and 0 means the next number should be equal.

The length of the pattern array m is 3. Therefore, the window size for comparison is 3 + 1 = 4. We will iterate through the nums array, taking sequences of 4 consecutive elements and comparing the changes between each to the pattern.

  1. The first window is [5, 3, 4, 2]. Here:

    • 5 to 3 is a decrease (pattern[0] should be 1, but it is -1)
    • 3 to 4 is an increase (pattern[1] should be -1, but it is 1)
    • 4 to 2 is a decrease (pattern[2] is 0, but it should be equal)

    This window does not match the pattern.

  2. Slide the window one position to the right to [3, 4, 2, 1]:

    • 3 to 4 is an increase (matches pattern[0] which is 1)
    • 4 to 2 is a decrease (matches pattern[1] which is -1)
    • 2 to 1 is a decrease (does not match pattern[2] which is 0)

    This window also does not match the pattern.

  3. Slide the window over one more to [4, 2, 1, 3]:

    • 4 to 2 is a decrease (does not match pattern[0] which is 1)
    • 2 to 1 is a decrease (matches pattern[1] which is -1)
    • 1 to 3 is an increase (matches pattern[2] which is 0, but it should be equal)

    This window does not match the pattern either.

  4. Lastly, slide to the final window [2, 1, 3, 6] (assuming the array had a 6 at the end):

    • 2 to 1 is a decrease (does not match pattern[0] which is 1)
    • 1 to 3 is an increase (matches pattern[1] which is -1)
    • 3 to 6 is an increase (matches pattern[2] which is 0, but it should be equal)

    This window, like the others, does not match the pattern.

None of the sliding windows for our chosen nums and pattern result in a match. Therefore, according to the above solution approach, this will return an answer of 0.

Through the iteration, we perform the comparisons and increase our answer count when a subarray matches the pattern; however, in this example, since we didn’t find any matching subarrays, the answer remains 0. This illustrates the brute force method that was described in the solution approach.

Solution Implementation

1from typing import List
2
3class Solution:
4    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
5        # Helper function to compare two numbers and return 
6        # 0 if equal, 1 if first is less, and -1 if first is greater.
7        def compare(a: int, b: int) -> int:
8            if a == b:
9                return 0
10            else:
11                return 1 if a < b else -1
12
13        # Initialize the count of matching subarrays.
14        match_count = 0
15
16        # Iterate over nums to check for each subarray starting at index 'i'.
17        for i in range(len(nums) - len(pattern) + 1):
18            # Check if the pattern of comparisons matches for the subarray starting at 'i'.
19            if all(compare(nums[i + k], nums[i + k + 1]) == pattern_val for k, pattern_val in enumerate(pattern)):
20                match_count += 1  # If it matches, increment the count.
21
22        # Return the total count of matching subarrays.
23        return match_count
24
1class Solution {
2
3    // Method to count the number of subarrays matching a given pattern.
4    public int countMatchingSubarrays(int[] nums, int[] pattern) {
5        int numLength = nums.length;          // Length of the input array.
6        int patternLength = pattern.length;   // Length of the pattern array.
7        int count = 0;                        // Variable to hold the count of matching subarrays.
8
9        // Iterate over the input array up to the point where comparison with the pattern makes sense.
10        for (int i = 0; i <= numLength - patternLength; ++i) {
11            int matchesPattern = 1; // Flag to check if the current subarray matches the pattern (1 for true).
12
13            // Iterating through the elements of the subarray and the pattern.
14            for (int k = 0; k < patternLength && matchesPattern == 1; ++k) {
15                // Compare the result of the function `f` with the current element of the pattern.
16                if (f(nums[i + k], nums[i + k + 1]) != pattern[k]) {
17                    matchesPattern = 0; // If they do not match, set the flag to false (0).
18                }
19            }
20          
21            // If the subarray matches the pattern, increment the count.
22            count += matchesPattern;
23        }
24      
25        // Return the total count of matching subarrays.
26        return count;
27    }
28
29    // Helper function to compare two integers and return -1, 0, or 1 based on their relationship.
30    private int f(int a, int b) {
31        if (a == b) {
32            return 0;     // If both integers are equal, return 0.
33        } else if (a < b) {
34            return 1;     // If the first integer is less than the second, return 1.
35        } else {
36            return -1;    // If the first integer is greater than the second, return -1.
37        }
38    }
39}
40
1class Solution {
2public:
3    // Function to count the number of subarrays in 'nums' that match the comparison pattern described in 'pattern'
4    int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
5        int n = nums.size(); // Size of the input array
6        int m = pattern.size(); // Size of the pattern array
7        int count = 0; // Initialize the count of matching subarrays
8
9        // Helper lambda function to compare two numbers and output -1, 0, or 1 based on their relation
10        auto compare = [](int a, int b) {
11            if (a == b) {
12                return 0;
13            } else if (a < b) {
14                return 1;
15            } else {
16                return -1;
17            }
18        };
19
20        // Loop through the main array to check every subarray of size equal to the pattern size
21        for (int i = 0; i <= n - m; ++i) { // Fix: Updated the loop condition with '=' to include last subarray
22            bool isMatch = true; // Flag to check if the current subarray matches the pattern
23
24            // Loop through the pattern
25            for (int k = 0; k < m && isMatch; ++k) {
26                // Compare adjacent elements in 'nums' using the 'compare' function, and check against the pattern
27                if (compare(nums[i + k], nums[i + k + 1]) != pattern[k]) {
28                    isMatch = false; // If any comparison does not match the pattern, set the flag to false
29                }
30            }
31
32            // If the subarray matches the pattern, increment the count
33            if (isMatch) {
34                count++;
35            }
36        }
37
38        // Return the total count of matching subarrays
39        return count;
40    }
41};
42
1function countMatchingSubarrays(nums: number[], pattern: number[]): number {
2    // A comparator function to compare two numbers based on the problem's criteria.
3    const compare = (a: number, b: number): number => {
4        if (a === b) {
5            return 0;
6        } else {
7            return a < b ? 1 : -1;
8        }
9    };
10
11    // Store the length of the 'nums' array and the 'pattern' array.
12    const numsLength = nums.length;
13    const patternLength = pattern.length;
14
15    // Initialize the count of matching subarrays to 0.
16    let matchingSubarraysCount = 0;
17
18    // Iterate over the 'nums' array, checking each possible subarray of length equal to 'pattern'.
19    for (let i = 0; i <= numsLength - patternLength; ++i) {
20        // Initialize a flag indicating if the current subarray matches the 'pattern'.
21        let isMatching = true;
22      
23        // Compare each element of the subarray with the next one and check against the 'pattern'.
24        for (let k = 0; k < patternLength && isMatching; ++k) {
25            // If the comparison does not match the pattern, set the flag to false.
26            if (compare(nums[i + k], nums[i + k + 1]) !== pattern[k]) {
27                isMatching = false;
28            }
29        }
30      
31        // If the flag is still true after the comparison, increment the count.
32        matchingSubarraysCount += isMatching ? 1 : 0;
33    }
34
35    // Return the total count of matching subarrays.
36    return matchingSubarraysCount;
37}
38

Time and Space Complexity

The time complexity of the provided code is O(n * m) where n is the length of the nums array and m is the length of the pattern array. This is because for each starting index in nums, the code checks whether the subarray beginning there matches the pattern by comparing each subsequent element until the end of pattern. There are n - m + 1 possible starting points in nums for a matching subarray, and for each starting point, it potentially checks m elements (the length of pattern). This results in O((n - m + 1) * m), which simplifies to O(n * m).

The space complexity of the code is O(1) since the algorithm only uses a few extra variables (ans, i, and k) and does not allocate any additional space that grows with the input size; the space used is constant regardless of the input size.

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


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a good use case for backtracking?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄