3036. Number of Subarrays That Match a Pattern II LeetCode Solution
In this guide, you will get 3036. Number of Subarrays That Match a Pattern II LeetCode Solution with the best time and space complexity. The solution to Number of Subarrays That Match a Pattern II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Number of Subarrays That Match a Pattern II
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.
2 <= n == nums.length <= 106
1 <= nums[i] <= 109
1 <= m == pattern.length < n
-1 <= pattern[i] <= 1
Complexity Analysis
Time Complexity: O(|\texttt{nums}| + |\texttt{pattern}|)
Space Complexity: O(|\texttt{nums}| + |\texttt{pattern}|)
3036. Number of Subarrays That Match a Pattern II LeetCode Solution in C++
class Solution {
public:
// Same as 3034. Number of Subarrays That Match a Pattern I
int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
const vector<int> numsPattern = getNumsPattern(nums);
return kmp(numsPattern, pattern);
}
private:
int getNum(int a, int b) {
if (a < b)
return 1;
if (a > b)
return -1;
return 0;
}
vector<int> getNumsPattern(const vector<int>& nums) {
vector<int> numsPattern;
for (int i = 1; i < nums.size(); ++i)
numsPattern.push_back(getNum(nums[i - 1], nums[i]));
return numsPattern;
}
// Returns the number of occurrences of the pattern in `nums`.
int kmp(const vector<int>& nums, const vector<int>& pattern) {
const vector<int> lps = getLPS(pattern);
int res = 0;
int i = 0; // nums' index
int j = 0; // pattern's index
while (i < nums.size()) {
if (nums[i] == pattern[j]) {
++i;
++j;
if (j == pattern.size()) {
++res;
j = lps[j - 1];
}
} else if (j > 0) { // Mismatch after j matches.
// Don't match lps[0..lps[j - 1]] since they will match anyway.
j = lps[j - 1];
} else {
++i;
}
}
return res;
}
// Returns the lps array, where lps[i] is the length of the longest prefix of
// pattern[0..i] which is also a suffix of this substring.
vector<int> getLPS(const vector<int>& pattern) {
vector<int> lps(pattern.size());
for (int i = 1, j = 0; i < pattern.size(); ++i) {
while (j > 0 && pattern[j] != pattern[i])
j = lps[j - 1];
if (pattern[i] == pattern[j])
lps[i] = ++j;
}
return lps;
}
}; /* code provided by PROGIEZ */
3036. Number of Subarrays That Match a Pattern II LeetCode Solution in Java
class Solution {
// Same as 3034. Number of Subarrays That Match a Pattern I
public int countMatchingSubarrays(int[] nums, int[] pattern) {
int[] numsPattern = getNumsPattern(nums);
return kmp(numsPattern, pattern);
}
private int getNum(int a, int b) {
if (a < b)
return 1;
if (a > b)
return -1;
return 0;
}
private int[] getNumsPattern(int[] nums) {
int[] numsPattern = new int[nums.length - 1];
for (int i = 1; i < nums.length; ++i)
numsPattern[i - 1] = getNum(nums[i - 1], nums[i]);
return numsPattern;
}
// Returns the number of occurrences of the pattern in `nums`.
private int kmp(int[] nums, int[] pattern) {
int[] lps = getLPS(pattern);
int res = 0;
int i = 0; // nums' index
int j = 0; // pattern's index
while (i < nums.length) {
if (nums[i] == pattern[j]) {
++i;
++j;
if (j == pattern.length) {
++res;
j = lps[j - 1];
}
} else if (j > 0) { // Mismatch after j matches.
// Don't match lps[0..lps[j - 1]] since they will match anyway.
j = lps[j - 1];
} else {
++i;
}
}
return res;
}
// Returns the lps array, where lps[i] is the longest proper prefix of
// pattern[0..i] which is also a suffix of this substring.
private int[] getLPS(int[] pattern) {
int[] lps = new int[pattern.length];
for (int i = 1, j = 0; i < pattern.length; ++i) {
while (j > 0 && pattern[j] != pattern[i])
j = lps[j - 1];
if (pattern[i] == pattern[j])
lps[i] = ++j;
}
return lps;
}
} // code provided by PROGIEZ
3036. Number of Subarrays That Match a Pattern II LeetCode Solution in Python
class Solution:
# Same as 3034. Number of Subarrays That Match a Pattern I
def countMatchingSubarrays(self, nums: list[int], pattern: list[int]) -> int:
def getNum(a: int, b: int) -> int:
if a < b:
return 1
if a > b:
return -1
return 0
numsPattern = [getNum(a, b) for a, b in itertools.pairwise(nums)]
return self._kmp(numsPattern, pattern)
def _kmp(self, nums: list[int], pattern: list[int]) -> int:
"""Returns the number of occurrences of the pattern in `nums`."""
def getLPS(nums: list[int]) -> list[int]:
"""
Returns the lps array, where lps[i] is the length of the longest prefix of
nums[0..i] which is also a suffix of this substring.
"""
lps = [0] * len(nums)
j = 0
for i in range(1, len(nums)):
while j > 0 and nums[j] != nums[i]:
j = lps[j - 1]
if nums[i] == nums[j]:
lps[i] = j + 1
j += 1
return lps
lps = getLPS(pattern)
res = 0
i = 0 # s' index
j = 0 # pattern's index
while i < len(nums):
if nums[i] == pattern[j]:
i += 1
j += 1
if j == len(pattern):
res += 1
j = lps[j - 1]
elif j != 0: # Mismatch after j matches.
# Don't match lps[0..lps[j - 1]] since they will match anyway.
j = lps[j - 1]
else:
i += 1
return res # code by PROGIEZ
