Number of Subarrays That Match a Pattern I solution and explanation
9 more videos on this problem
Number of Subarrays That Match a Pattern | Brute Force | Optimal | KMP | Leetcode 3034 | 3036codestorywithMIK · 37:38 · 3K views
3034 Number of Subarrays That Match a Pattern I || Brute Force to KMP ✅ || O(N*N) - O(N+M) 🔥Ayush Rao · 13:57 · 761 views
Leetcode 3034: Number of Subarrays That Match a Pattern I | Weekly ContestAlgorithms Casts · 7:04 · 538 views
3034. Number of Subarrays That Match a Pattern I (Leetcode Medium)Programming Live with Larry · 13:52 · 347 views
3034. Number of Subarrays That Match a Pattern I || Weekly Contest 384 || C++Priyanshi Porwal · 11:13 · 106 views
3034. Number of Subarrays That Match a Pattern I , 3036. Number of Subarrays That Match a Pattern IIShivam Mishra LeetCode · 14:28 · 69 views
Number of Subarrays That Match a Pattern I | LeetCodeFrancisco Veiras · 16:54 · 62 views
Leetcode 3034 | Number of Subarrays That Match a Pattern I | Weekly Contest 384 | Python | Mediumcodingwithme · 5:22 · 29 views
Number of Subarrays That Match a Pattern I | Leetcode Weekly Contest 384 | Solution walk throughLogic Before Lines · 16:08 · 26 views
Number of Subarrays that match the pattern-I,II | Leetcode Weekly contest 384 #dsa #leetcodeCosmoky_19 · 20:33 · 29 views
The problem
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]ifpattern[k] == 1.nums[i + k + 1] == nums[i + k]ifpattern[k] == 0.nums[i + k + 1] < nums[i + k]ifpattern[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 <= 1001 <= nums[i] <= 1091 <= m == pattern.length < n-1 <= pattern[i] <= 1
Approach overview
Problem Overview: You are given an integer array nums and a pattern array containing values -1, 0, and 1. Each pattern value describes the relationship between two consecutive numbers: decreasing, equal, or increasing. The task is to count how many subarrays of length pattern.length + 1 produce the same sequence of comparisons.
Approach 1: Brute Force Comparison (Time: O(n * m), Space: O(1))
The direct method checks every possible subarray of length m + 1 where m is the pattern length. For each candidate start index, iterate through the next m pairs and compute the relationship between adjacent elements: 1 if increasing, 0 if equal, and -1 if decreasing. Compare this generated relation with the corresponding pattern value. If all comparisons match, increment the result. This approach uses basic array traversal and is easy to implement, but it repeatedly recomputes comparisons for overlapping windows.
Approach 2: Optimized Sliding Window (Time: O(n), Space: O(n))
A more efficient approach converts the original array into a difference pattern first. Build a new array where each element represents the relation between nums[i] and nums[i+1]. This produces a sequence of -1, 0, and 1 values. The problem then becomes a classic string matching task: count how many times the pattern appears inside this difference array.
Using a sliding window of size m, compare the window against the pattern while moving one step at a time. Because the comparison array already encodes relationships, each shift only requires checking the window values rather than recalculating numeric comparisons. Some implementations further optimize this using rolling hash to treat the relation sequence like a hashed string and detect matches in constant time per step.
This reduces repeated work and processes the array in a single pass after preprocessing. The time complexity becomes O(n) since each comparison relation is computed once and each window is checked once.
Recommended for interviews: Start with the brute force approach to demonstrate that you understand how the pattern maps to pairwise comparisons. Then move to the optimized sliding window or string‑matching interpretation. Interviewers typically expect the linear-time idea because it avoids recomputing comparisons for overlapping subarrays and shows familiarity with pattern matching techniques.
Approach 1: Brute Force Approach
This approach involves iterating over all possible subarrays of the given array nums and checking each subarray against the specified pattern. Since we have an array pattern of length m, the length of the subarrays we need to check is m + 1. For each subarray, verify that it matches the pattern by checking the conditions at each step.
def count_subarrays(nums, pattern):
n = len(nums)
m = len(pattern)
count = 0
for i in range(n - m):
for j in range(m):
if (pattern[j] == 1 and nums[i + j + 1] <= nums[i + j]) or \
(pattern[j] == 0 and nums[i + j + 1] != nums[i + j]) or \
(pattern[j] == -1 and nums[i + j + 1] >= nums[i + j]):
break
else:
count += 1
return count
nums = [1,2,3,4,5,6]
pattern = [1,1]
print(count_subarrays(nums, pattern)) # Output: 4public class SubarrayPattern {
public static int countSubarrays(int[] nums, int[] pattern) {
int n = nums.length;
int m = pattern.length;
int count = 0;
for (int i = 0; i <= n - m - 1; i++) {
int j;
for (j = 0; j < m; j++) {
if ((pattern[j] == 1 && nums[i + j + 1] <= nums[i + j]) ||
(pattern[j] == 0 && nums[i + j + 1] != nums[i + j]) ||
(pattern[j] == -1 && nums[i + j + 1] >= nums[i + j])) {
break;
}
}
if (j == m) count++;
}
return count;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5,6};
int[] pattern = {1,1};
int result = countSubarrays(nums, pattern);
System.out.println(result); // Output: 4
}
}#include <iostream>
#include <vector>
int countSubarrays(const std::vector<int>& nums, const std::vector<int>& pattern) {
int n = nums.size();
int m = pattern.size();
int count = 0;
for (int i = 0; i <= n - m - 1; ++i) {
int j;
for (j = 0; j < m; ++j) {
if ((pattern[j] == 1 && nums[i + j + 1] <= nums[i + j]) ||
(pattern[j] == 0 && nums[i + j + 1] != nums[i + j]) ||
(pattern[j] == -1 && nums[i + j + 1] >= nums[i + j])) {
break;
}
}
if (j == m) count++;
}
return count;
}
int main() {
std::vector<int> nums = {1,2,3,4,5,6};
std::vector<int> pattern = {1,1};
int result = countSubarrays(nums, pattern);
std::cout << result << std::endl; // Output: 4
return 0;
}function countSubarrays(nums, pattern) {
const n = nums.length;
const m = pattern.length;
let count = 0;
for (let i = 0; i <= n - m - 1; i++) {
let j = 0;
for (; j < m; j++) {
if ((pattern[j] === 1 && nums[i + j + 1] <= nums[i + j]) ||
(pattern[j] === 0 && nums[i + j + 1] !== nums[i + j]) ||
(pattern[j] === -1 && nums[i + j + 1] >= nums[i + j])) {
break;
}
}
if (j === m) count++;
}
return count;
}
const nums = [1,2,3,4,5,6];
const pattern = [1,1];
console.log(countSubarrays(nums, pattern)); // Output: 4#include <stdio.h>
int countSubarrays(int* nums, int numsSize, int* pattern, int patternSize) {
int count = 0;
for (int i = 0; i <= numsSize - patternSize - 1; i++) {
int j;
for (j = 0; j < patternSize; j++) {
if (pattern[j] == 1 && nums[i + j + 1] <= nums[i + j]) break;
if (pattern[j] == 0 && nums[i + j + 1] != nums[i + j]) break;
if (pattern[j] == -1 && nums[i + j + 1] >= nums[i + j]) break;
}
if (j == patternSize) count++;
}
return count;
}
int main() {
int nums[] = {1,2,3,4,5,6};
int pattern[] = {1,1};
int result = countSubarrays(nums, 6, pattern, 2);
printf("%d\n", result); // Output: 4
return 0;
}using System;
public class Subarrays {
public static int CountSubarrays(int[] nums, int[] pattern) {
int n = nums.Length;
int m = pattern.Length;
int count = 0;
for (int i = 0; i <= n - m - 1; i++) {
int j;
for (j = 0; j < m; j++) {
if ((pattern[j] == 1 && nums[i + j + 1] <= nums[i + j]) ||
(pattern[j] == 0 && nums[i + j + 1] != nums[i + j]) ||
(pattern[j] == -1 && nums[i + j + 1] >= nums[i + j])) {
break;
}
}
if (j == m) count++;
}
return count;
}
public static void Main() {
int[] nums = {1,2,3,4,5,6};
int[] pattern = {1,1};
Console.WriteLine(CountSubarrays(nums, pattern)); // Output: 4
}
}Python's implementation utilizes a range loop to iterate over starting indices, with an inner loop evaluating pattern conditions. The else block of the loop executes if no break statement is hit, increasing the count.
Time Complexity: O(n * m), where n is the length of nums and m is the length of pattern.
Space Complexity: O(1), using minimal temporary storage.
Approach 2: Optimized Sliding Window
By using a sliding window approach, we can optimize the search for matching subarrays. The core idea is to progress through nums with a window of size m+1 and dynamically verify the pattern in real-time for each window shift. This eliminates unnecessary re-evaluation of indices already validated or invalidated as we move forward.
def count_subarrays(nums, pattern):
matches = 0
currentMatchLength = 0
for i in range(len(nums) - 1):
valid = False
if pattern[currentMatchLength] == 1 and nums[i+1] > nums[i]:
valid = True
elif pattern[currentMatchLength] == 0 and nums[i+1] == nums[i]:
valid = True
elif pattern[currentMatchLength] == -1 and nums[i+1] < nums[i]:
valid = True
if valid:
currentMatchLength += 1
else:
currentMatchLength = 0
if currentMatchLength == len(pattern):
matches += 1
currentMatchLength = len(pattern) - 1
return matches
nums = [1,2,3,4,5,6]
pattern = [1,1]
print(count_subarrays(nums, pattern)) # Output: 4public class SubarrayPatternOptimized {
public static int countSubarrays(int[] nums, int[] pattern) {
int matches = 0;
int currentMatchLength = 0;
for (int i = 0; i < nums.length - 1; i++) {
boolean valid = false;
if (pattern[currentMatchLength] == 1 && nums[i+1] > nums[i]) valid = true;
else if (pattern[currentMatchLength] == 0 && nums[i+1] == nums[i]) valid = true;
else if (pattern[currentMatchLength] == -1 && nums[i+1] < nums[i]) valid = true;
if (valid) currentMatchLength++;
else currentMatchLength = 0;
if (currentMatchLength == pattern.length) {
matches++;
currentMatchLength = pattern.length - 1;
}
}
return matches;
}
public static void main(String[] args) {
int[] nums = {1,2,3,4,5,6};
int[] pattern = {1,1};
int result = countSubarrays(nums, pattern);
System.out.println(result); // Output: 4
}
}function countSubarrays(nums, pattern) {
let matches = 0;
let currentMatchLength = 0;
for (let i = 0; i < nums.length - 1; i++) {
let valid = false;
if (pattern[currentMatchLength] === 1 && nums[i+1] > nums[i]) valid = true;
else if (pattern[currentMatchLength] === 0 && nums[i+1] === nums[i]) valid = true;
else if (pattern[currentMatchLength] === -1 && nums[i+1] < nums[i]) valid = true;
if (valid) currentMatchLength++;
else currentMatchLength = 0;
if (currentMatchLength === pattern.length) {
matches++;
currentMatchLength = pattern.length - 1;
}
}
return matches;
}
const nums = [1,2,3,4,5,6];
const pattern = [1,1];
console.log(countSubarrays(nums, pattern)); // Output: 4#include <stdio.h>
int countSubarrays(int* nums, int numsSize, int* pattern, int patternSize) {
int matches = 0;
int currentMatchLength = 0;
for (int i = 0; i < numsSize - 1; i++) {
int valid = 0;
if (pattern[currentMatchLength] == 1 && nums[i+1] > nums[i]) valid = 1;
else if (pattern[currentMatchLength] == 0 && nums[i+1] == nums[i]) valid = 1;
else if (pattern[currentMatchLength] == -1 && nums[i+1] < nums[i]) valid = 1;
if (valid) currentMatchLength++;
else currentMatchLength = 0;
if (currentMatchLength == patternSize) {
matches++;
currentMatchLength = patternSize - 1;
}
}
return matches;
}
int main() {
int nums[] = {1,2,3,4,5,6};
int pattern[] = {1,1};
int result = countSubarrays(nums, 6, pattern, 2);
printf("%d\n", result); // Output: 4
return 0;
}Python further simplifies handling window tracking by adjusting currentMatchLength dynamically, ensuring only direct comparisons are made per window shift.
Time Complexity: O(n), linear scan due to window-based tracking.
Space Complexity: O(1), restricted to integer tracking variables.
Approach 3: Enumeration
We can enumerate all subarrays of array nums with a length of m + 1, and then check whether they match the pattern array pattern. If they do, we increment the answer by one.
The time complexity is O(n times m), where n and m are the lengths of the arrays nums and pattern respectively. The space complexity is O(1).
function countMatchingSubarrays(nums: number[], pattern: number[]): number {
const f = (a: number, b: number) => (a === b ? 0 : a < b ? 1 : -1);
const n = nums.length;
const m = pattern.length;
let ans = 0;
for (let i = 0; i < n - m; ++i) {
let ok = 1;
for (let k = 0; k < m && ok; ++k) {
if (f(nums[i + k], nums[i + k + 1]) !== pattern[k]) {
ok = 0;
}
}
ans += ok;
}
return ans;
}func countMatchingSubarrays(nums []int, pattern []int) (ans int) {
f := func(a, b int) int {
if a == b {
return 0
}
if a < b {
return 1
}
return -1
}
n, m := len(nums), len(pattern)
for i := 0; i < n-m; i++ {
ok := 1
for k := 0; k < m && ok == 1; k++ {
if f(nums[i+k], nums[i+k+1]) != pattern[k] {
ok = 0
}
}
ans += ok
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m), where n is the length of nums and m is the length of pattern. Space Complexity: O(1), using minimal temporary storage. |
| Optimized Sliding Window | Time Complexity: O(n), linear scan due to window-based tracking. Space Complexity: O(1), restricted to integer tracking variables. |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Comparison | O(n * m) | O(1) | Useful for understanding the comparison logic or when the pattern length is very small. |
| Sliding Window on Difference Array | O(n) | O(n) | General optimal solution for large arrays. Converts numeric comparisons into a pattern matching problem. |
Frequently asked questions
Is Number of Subarrays That Match a Pattern I easy or hard?
The problem is rated Medium because it requires recognizing that pairwise comparisons can be converted into a pattern matching problem. The brute force approach is simple, but identifying the linear-time optimization requires familiarity with sliding window or string matching techniques.
Number of Subarrays That Match a Pattern I Python/Java solution
Most implementations first build the comparison array and then slide a window over it to check matches. This logic is straightforward to implement in Python, Java, C++, or JavaScript and typically runs in O(n) time with O(n) extra space.
How to solve Number of Subarrays That Match a Pattern I in O(n)?
First convert the array into a relation array where each element represents whether nums[i+1] is greater than, equal to, or less than nums[i]. Then slide a window of size equal to the pattern length across this relation array and compare it to the pattern. Each position is checked once, producing an O(n) solution.
What is the best approach for Number of Subarrays That Match a Pattern I?
The most efficient method converts the array into a sequence representing pairwise relationships (-1, 0, 1) and then searches for the pattern inside this sequence using a sliding window. This avoids recomputing comparisons for overlapping subarrays and runs in O(n) time after building the difference array.
Is Number of Subarrays That Match a Pattern I asked at Google/Amazon/Meta?
Pattern matching and sliding window problems are common in interviews at companies like Google, Amazon, and Meta. This problem specifically tests the ability to transform numeric comparisons into a sequence and apply efficient pattern searching techniques.
What data structure is used in Number of Subarrays That Match a Pattern I?
The solution mainly uses arrays. The optimized approach also treats the comparison array like a string and applies techniques from string matching or rolling hash to detect pattern occurrences efficiently.
What is the time complexity of Number of Subarrays That Match a Pattern I?
The brute force solution checks every candidate subarray and compares each pair against the pattern, resulting in O(n * m) time where n is the array size and m is the pattern length. The optimized sliding window approach processes the array once and runs in O(n) time.