3034. Number of Subarrays That Match a Pattern I
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.
What is the running time of the following code?
1int sqrt(int n) { 2 for (int guess = 1; guess * guess <= n; guess++) { 3 if (guess * guess == n) { 4 return guess; 5 } 6 } 7 return -1; 8}
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).
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
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.
-
The first window is
[5, 3, 4, 2]. Here:5to3is a decrease (pattern[0]should be1, but it is-1)3to4is an increase (pattern[1]should be-1, but it is1)4to2is a decrease (pattern[2]is0, but it should be equal)
This window does not match the pattern.
-
Slide the window one position to the right to
[3, 4, 2, 1]:3to4is an increase (matchespattern[0]which is1)4to2is a decrease (matchespattern[1]which is-1)2to1is a decrease (does not matchpattern[2]which is0)
This window also does not match the pattern.
-
Slide the window over one more to
[4, 2, 1, 3]:4to2is a decrease (does not matchpattern[0]which is1)2to1is a decrease (matchespattern[1]which is-1)1to3is an increase (matchespattern[2]which is0, but it should be equal)
This window does not match the pattern either.
-
Lastly, slide to the final window
[2, 1, 3, 6](assuming the array had a6at the end):2to1is a decrease (does not matchpattern[0]which is1)1to3is an increase (matchespattern[1]which is-1)3to6is an increase (matchespattern[2]which is0, 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
241class 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}
401class 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};
421function 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}
38Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is
[3, 7, 40, 80].
What is the recurrence relation?
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.
What's the output of running the following function using the following tree as input?
1def serialize(root):
2 res = []
3 def dfs(root):
4 if not root:
5 res.append('x')
6 return
7 res.append(root.val)
8 dfs(root.left)
9 dfs(root.right)
10 dfs(root)
11 return ' '.join(res)
121import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4 StringJoiner res = new StringJoiner(" ");
5 serializeDFS(root, res);
6 return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10 if (root == null) {
11 result.add("x");
12 return;
13 }
14 result.add(Integer.toString(root.val));
15 serializeDFS(root.left, result);
16 serializeDFS(root.right, result);
17}
181function serialize(root) {
2 let res = [];
3 serialize_dfs(root, res);
4 return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8 if (!root) {
9 res.push("x");
10 return;
11 }
12 res.push(root.val);
13 serialize_dfs(root.left, res);
14 serialize_dfs(root.right, res);
15}
16Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Teaching 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.