Number of Subarrays That Match a Pattern in Java
In this tutorial, we are going to learn about Number of Subarrays That Match a Pattern in Java. Provided a 0-indexed integer array pattern of size m made up of the integers -1, 0, and 1, and a 0-indexed integer array numbs of size n. The objective is to count the number of subarrays in a 0-indexed integer array that matches a pattern of size m. For any element pattern[k], a subarray numbs[i..j] of size m + 1 is considered to match the pattern if each of the following criteria is satisfied: In the case that pattern[k] == 1, numbs[i + k + 1] > numbs[i + k]. suppose if pattern[k] == 0, then numbs[i + k + 1] == numbs[i + k]. else if pattern[k] == -1, then numbs[i + k + 1] < numbs[i + k]. Let’s see a few examples to understand it.
Example 1:
Input: numbs = [5, 6, 7, 8, 9, 10], pattern = [1,1].
Output: 4.
Explanation: We are looking for strictly increasing subarrays of size 3, as indicated by the pattern [1,1]. The subarrays [5,6,7], [6,7,8], [7,8,9], and [8,9,10] in the array numbs meet this pattern. As a result, 4 subarrays in numbs match the pattern. Therefore, 4 is the result.
Example 2:
Input: numbs = [2, 5, 5, 2, 4, 6, 6, 4], pattern = [1, 0, -1].
Output: 2
Explanation: In the supplied input, the pattern [1,0,-1] indicates that we are looking for subarrays in which the first number is less than the second, the second equals the third, and the third exceeds the fourth. The subarrays [4,6,6,4] and [2,5,5,2] in the array numbs match to this pattern. As a result, the pattern matches two subarrays in numbs. Thus, the result is 2.
Approach: using Brute force
Observe the steps to solve the problem with the help of the Brute Force Approach.
Step 1: Set the variables n, m, and cnt to hold the length of the pattern, the number of matching subarrays, and the count of matching subarrays, respectively.
Step 2: Iterate over the numbs array.
Step 3: Determine whether the current subarray matches the pattern by initialising a boolean variable called validSubarray true for each iteration.
Step 4: Iterate over the ptrn array:
Step 4.1: For each element in ptrn, compare it with the corresponding element in numbs based on the current index.
Step 4.2: If the element in ptrn is 1 and the element in numbs at the next index is less than or equal to the current element, set validSubarray to false.
Step 4.3: If the element in ptrn is 0 and the element in numbs at the next index is not equal to the current element, set validSubarray to false.
Step 4.4: If the element in ptrn is -1 and the element in numbs at the next index is greater than or equal to the current element, set validSubarray to false.
Step 5: After that, check if validSubarray is still true. If it is, increment the cnt variable by 1.
Step 6: Repeat steps 2 to 5 for all possible subarrays in the numbs array.
Step 7: Finally, return the value of cnt, which represents the total count of subarrays that match the pattern.
FileName: NoOfSubArraysMatchPattern.java
public class NoOfSubArraysMatchPattern { // method to count subarrays that match pattern public int countOfSubarraysMatched(int[] numbs, int[] ptrn) { int n = numbs.length; int m = ptrn.length; int cnt = 0; // iterating through the array for (int i = 0; i <= n - m -1; i++) { boolean validSubarray = true; // verify if the current subarray matches the pattern for (int j = 0; j < m; j++) { if (ptrn[j] == 1 && numbs[i + j + 1] <= numbs[i + j]) { validSubarray = false; break; } else if (ptrn[j] == 0 && numbs[i + j + 1] != numbs[i + j]) { validSubarray = false; break; } else if (ptrn[j] == -1 && numbs[i + j + 1] >= numbs[i + j]) { validSubarray = false; break; } } if (validSubarray) { cnt++; // incrementing if valid subarray } } return cnt; } // main method public static void main(String[] args) { // provide input values int[] numbs = {2, 5, 5, 2, 4, 6, 6, 4}; int[] ptrn = {1,0,-1}; NoOfSubArraysMatchPattern smp = new NoOfSubArraysMatchPattern(); int matchingSubarrays = smp.countOfSubarraysMatched(numbs, ptrn); System.out.println("Number of matching subarrays: " + matchingSubarrays); } }
Output:
Number of matching subarrays: 2
Complexity analysis: The time complexity is O(n * m), where n is the length of the numbs array and m is the length of the pattern array. Because the countOfSubarraysMatched method iterates over each index of the numbs array, running from 0 to n - m - 1, while the inner loop iterates over each element of the pattern array, with a constant length of m. The space complexity is O(1). Because indexing variables (i, j), validSubarray, and cnt require constant space.
Approach: Using a sliding window
Step 1: Create arrays named numbs to represent the input array and ptrn to represent the pattern to match. Also, set a counter variable cnt to keep track of the number of matching subarrays.
Step 2: Determine the lengths of the pattern array ptrn and the input array numbs, respectively, and assign them to variables n and m.
Step 3: Iterate over the input array numbs from index 0 to n - m, where n is the length of numbs and m is the length of ptrn.
Step 4: Verify whether the current subarray matches the pattern.
Step 4.1: Evaluate each element in the input array numbs by iterating through the pattern array ptrn and comparing it with the matching element.
Step 4.2: Return false if any element is not matched.
Step 4.3: Else, return true.
Step 5: If step 4 returns true, increment the counter cnt.
Step 6: Finally, return the cnt value, which represents the count of the number of subarrays that match the pattern.
FileName: NoOfSubArraysMatchPattern.java
public class NoOfSubArraysMatchPattern { // method to count the number of subarrays that match the pattern public int countOfSubarraysMatched(int[] numbs, int[] ptrn) { int cnt = 0; int n = numbs.length; int m = ptrn.length; // Slide the window for (int i = 0; i < n - m; i++) { // Check if the current subarray matches the pattern if (matchesPattern(numbs, ptrn, i)) { cnt++; } } return cnt; } // method to verify if the subarray starting index matches the pattern private boolean matchesPattern(int[] numbs, int[] ptrn, int start) { for (int i = 0; i < ptrn.length; i++) // comparing adjacent elements in the subarray if (Integer.compare(numbs[start + i + 1], numbs[start + i]) != ptrn[i]) return false; return true; } // main method public static void main(String[] args) { // provide input values int[] numbs = {2, 5, 5, 2, 4, 6, 6, 4}; int[] ptrn = {1,0,-1}; NoOfSubArraysMatchPattern smp = new NoOfSubArraysMatchPattern(); int matchingSubarrays = smp.countOfSubarraysMatched(numbs, ptrn); System.out.println("Number of matching subarrays: " + matchingSubarrays); } }
Output:
Number of matching subarrays: 2
Complexity analysis: The program uses a for loop to slide the window through the input array, with a time complexity of O(n - m). The matchesPattern method takes O(n) time. The overall time complexity is O((n - m) * m). The space complexity is O(n + m) due to input arrays numbs and ptrn, and O(1) for the matchesPattern method, resulting in an overall complexity of O(n + m).
Approach: Using Queue
Observe the below steps to solve the problem.
Step 1: Set the variables cnt to count the number of matching subarrays and len to store the length of the pattern array plus one.
Step 2: Create a deque q to hold elements from the array numbs.
Step 3: Add the first len numbs elements to deque q.
Step 4: Check if the subarray represented by the elements in q matches the pattern specified in ptrn by iterating through the elements of ptrn and comparing them to the corresponding elements in q. Increment cnt by 1 if they match.
Step 5: Start at index len and iterate through the array numbs. For each iteration:
Step 5.1: Remove the initial element of the deque q.
Step 5.2: Add the current element of numbs to deque q.
Step 5.3: Verify whether the pattern specified by ptrn is matched by the subarray represented by the elements in q. Increase cnt by 1 if they match.
Step 6: Return the count cnt, which counts the number of subarrays that match the pattern.
Now, let’s do the implementation of the above steps.
FileName: NoOfSubArraysMatchPattern.java
import java.util.*; public class NoOfSubArraysMatchPattern { // Method to count the number of subarrays matched with the pattern public int countOfSubarraysMatched(int[] numbs, int[] ptrn) { int len = ptrn.length + 1; int cnt = 0; // Deque to maintain the sliding window Dequeq = new ArrayDeque<>(); for (int i = 0; i < len; i++) { q.addLast(numbs[i]); } if (check(q, ptrn)) { cnt++; } int n = numbs.length; // sliding the window for (int i = len; i < n; i++) { q.removeFirst(); q.addLast(numbs[i]); if (check(q, ptrn)) { cnt++; } } return cnt; } // Method to check if a window matches the given pattern public boolean check(Deque q, int[] a) { // create a copy of the deque Deque temp = new ArrayDeque<>(q); // iterating through the array pattern for (int i : a) { int first = temp.removeFirst(); int second = temp.getFirst(); if (i == 1) { if (second <= first) { return false; } } if (i == 0) { if (first != second) { return false; } } if (i == -1) { if (first <= second) { return false; } } } return true; } // main method public static void main(String[] args) { // provide input values int[] numbs = {2, 5, 5, 2, 4, 6, 6, 4}; int[] ptrn = {1,0,-1}; NoOfSubArraysMatchPattern smp = new NoOfSubArraysMatchPattern(); int matchingSubarrays = smp.countOfSubarraysMatched(numbs, ptrn); System.out.println("Number of matching subarrays: " + matchingSubarrays); } }
Output:
Number of matching subarrays: 2
Complexity analysis: The time complexity of O(n * m), where n is the numbs length and m is the ptrn length. Because the countOfSubarraysMatched() method iterates through the numbs array once, then calls the check() method, which iterates through the ptrn array once. The program uses a Deque named q to store subarray elements with a space complexity of O(n). A temporary Deque named temp is created for comparison with the pattern array that takes O(n) space. Therefore, the overall space complexity is O(n)