LeetCode 3034 - Number of Subarrays That Match a Pattern I

LeetCode Problem 3034

Difficulty: 🟡 Medium
Topics: Array, Rolling Hash, String Matching, Hash Function

Solution

Problem Understanding

The problem asks us to count how many contiguous subarrays of nums match a given relationship pattern.

Instead of comparing exact values, the pattern describes how adjacent numbers should relate to each other. Each value in pattern represents a comparison between two consecutive elements in a subarray:

• 1 means the next number must be greater than the current number.
• 0 means the next number must be equal to the current number.
• -1 means the next number must be smaller than the current number.

If pattern has length m, then any matching subarray must have length m + 1, because each pattern entry describes the relationship between two neighboring numbers. For example, if the pattern length is 3, we need 4 numbers to produce 3 comparisons.

We must examine every subarray of size m + 1 in nums and determine whether all pairwise comparisons match the required pattern. The final answer is simply the number of matching subarrays.

For example:

nums = [1,4,4,1]
pattern = [1,0,-1]

The comparisons are:

1 -> 4  => increasing (1)
4 -> 4  => equal (0)
4 -> 1  => decreasing (-1)

This exactly matches [1,0,-1], so this subarray counts.

Understanding the Constraints

The constraints are:

• 2 <= nums.length <= 100
• 1 <= pattern.length < nums.length
• pattern[i] ∈ {-1, 0, 1}

The most important observation is that n <= 100, which is very small. Even an O(n * m) solution is completely acceptable.

A brute force approach that checks every possible subarray and validates it against the pattern will run comfortably within limits.

However, the problem is tagged with rolling hash and string matching because we can transform the problem into pattern matching over a derived comparison array. This leads to a cleaner and more scalable solution.

Important Edge Cases

One important edge case is when pattern has length 1. In this case, every subarray of size 2 only requires a single comparison, making the logic simpler but still requiring careful handling.

Another edge case is repeated values in nums. Since 0 in the pattern means equality, implementations that only check increasing or decreasing relationships can easily fail.

We must also correctly handle negative transitions (-1), since it is easy to accidentally reverse the comparison direction.

The problem guarantees that pattern.length < nums.length, so there will always be at least one candidate subarray to examine.

Approaches

Brute Force

The most straightforward solution is to check every possible subarray of size m + 1.

For every starting index i, we examine the next m adjacent pairs and compare them against the corresponding value in pattern.

If at any position the comparison does not match, we immediately stop checking that subarray and move to the next one. If all comparisons match, we increment our answer.

This approach is correct because it directly follows the problem definition. Every valid subarray is checked exactly once, and we only count it if every required relationship matches.

The downside is that for each starting position we may scan the entire pattern, leading to O(n * m) time complexity.

Optimal Approach, Transform Into Pattern Matching

The key observation is that the problem is really asking whether a sequence of comparisons matches the pattern.

Instead of repeatedly comparing numbers inside each subarray, we can preprocess nums into a comparison array.

For every adjacent pair:

nums[i] and nums[i+1]

we compute:

1   if nums[i+1] > nums[i]
0   if nums[i+1] == nums[i]
-1  if nums[i+1] < nums[i]

This creates a derived array of length n - 1.

Now the problem becomes:

Count how many contiguous segments in this comparison array exactly equal pattern.

This is now a standard pattern matching problem. Since constraints are tiny, a simple sliding comparison works efficiently in O(n * m).

The advantage is conceptual clarity and extensibility. If constraints were larger, techniques like KMP or rolling hash could reduce the complexity to linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × m)	O(1)	Directly checks every candidate subarray
Optimal	O(n × m)	O(n)	Converts comparisons into an array and performs pattern matching

Algorithm Walkthrough

Step 1: Build the comparison array

Create a new array relations of size n - 1.

For every adjacent pair in nums:

• Add 1 if the sequence increases
• Add 0 if values are equal
• Add -1 if the sequence decreases

For example:

nums = [1,4,4,1,3]

relations = [1,0,-1,1]

This preprocessing converts the numeric problem into a sequence matching problem.

Step 2: Slide over the comparison array

Since pattern has length m, we check every window of length m inside relations.

For every starting index:

relations[i : i + m]

we compare it element by element with pattern.

Step 3: Validate the window

Compare each position:

relations[i + j] == pattern[j]

If any mismatch occurs, stop immediately and move to the next starting position.

Early termination avoids unnecessary work.

Step 4: Count matches

If all m comparisons match, increment the answer counter.

Step 5: Return the result

After checking all valid windows, return the total count.

Why it works

The comparison array preserves exactly the information required by the problem. Every entry corresponds to the relationship between adjacent elements in nums.

A subarray of size m + 1 matches the pattern if and only if its sequence of adjacent comparisons exactly equals pattern. Therefore, counting occurrences of pattern inside the comparison array is mathematically equivalent to counting valid subarrays.

Python Solution

from typing import List

class Solution:
    def countMatchingSubarrays(
        self,
        nums: List[int],
        pattern: List[int]
    ) -> int:
        n = len(nums)
        m = len(pattern)

        relations = []

        for i in range(n - 1):
            if nums[i + 1] > nums[i]:
                relations.append(1)
            elif nums[i + 1] < nums[i]:
                relations.append(-1)
            else:
                relations.append(0)

        count = 0

        for start_index in range(len(relations) - m + 1):
            matches = True

            for j in range(m):
                if relations[start_index + j] != pattern[j]:
                    matches = False
                    break

            if matches:
                count += 1

        return count

The implementation begins by constructing the relations array. Each adjacent pair in nums is converted into one of three possible values: 1, 0, or -1.

Once preprocessing is complete, we iterate over every possible window of size m in relations. Since pattern also has size m, we can compare the two arrays position by position.

The boolean flag matches helps us stop early whenever we detect a mismatch. This prevents unnecessary comparisons and keeps the implementation efficient.

Finally, every fully matching window increments the result counter, which is returned at the end.

Go Solution

func countMatchingSubarrays(nums []int, pattern []int) int {
	n := len(nums)
	m := len(pattern)

	relations := make([]int, 0, n-1)

	for i := 0; i < n-1; i++ {
		if nums[i+1] > nums[i] {
			relations = append(relations, 1)
		} else if nums[i+1] < nums[i] {
			relations = append(relations, -1)
		} else {
			relations = append(relations, 0)
		}
	}

	count := 0

	for start := 0; start <= len(relations)-m; start++ {
		matches := true

		for j := 0; j < m; j++ {
			if relations[start+j] != pattern[j] {
				matches = false
				break
			}
		}

		if matches {
			count++
		}
	}

	return count
}

The Go implementation follows the exact same algorithmic structure as the Python solution.

Since Go does not have dynamic lists like Python, we create relations using make() with capacity n - 1 for efficiency.

Go slices are naturally bounds-safe, so iterating with:

start <= len(relations)-m

ensures every valid window is checked exactly once.

There are no integer overflow concerns because values only involve -1, 0, and 1, and the answer is at most n.

Worked Examples

Example 1

nums = [1,2,3,4,5,6]
pattern = [1,1]

First construct the comparison array:

Adjacent Pair	Comparison
1 → 2	1
2 → 3	1
3 → 4	1
4 → 5	1
5 → 6	1

So:

relations = [1,1,1,1,1]

Now slide a window of length 2.

Window Start	Window	Matches Pattern?	Count
0	[1,1]	Yes	1
1	[1,1]	Yes	2
2	[1,1]	Yes	3
3	[1,1]	Yes	4

Final answer:

4

Example 2

nums = [1,4,4,1,3,5,5,3]
pattern = [1,0,-1]

Construct the comparison array:

Adjacent Pair	Comparison
1 → 4	1
4 → 4	0
4 → 1	-1
1 → 3	1
3 → 5	1
5 → 5	0
5 → 3	-1

So:

relations = [1,0,-1,1,1,0,-1]

Check windows of length 3.

Window Start	Window	Matches Pattern?	Count
0	[1,0,-1]	Yes	1
1	[0,-1,1]	No	1
2	[-1,1,1]	No	1
3	[1,1,0]	No	1
4	[1,0,-1]	Yes	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n × m)	We check every valid window and compare up to m elements
Space	O(n)	The comparison array stores n - 1 values

The preprocessing step takes O(n) time to build the comparison array. After that, we examine up to n - m windows, and each window comparison takes O(m) time in the worst case.

Since n <= 100, this solution is easily fast enough.

Test Cases

solution = Solution()

# Example 1
assert solution.countMatchingSubarrays(
    [1, 2, 3, 4, 5, 6],
    [1, 1]
) == 4  # strictly increasing windows

# Example 2
assert solution.countMatchingSubarrays(
    [1, 4, 4, 1, 3, 5, 5, 3],
    [1, 0, -1]
) == 2  # mixed comparisons

# Minimum valid input
assert solution.countMatchingSubarrays(
    [1, 2],
    [1]
) == 1  # single increasing pair

# Single mismatch
assert solution.countMatchingSubarrays(
    [2, 1],
    [1]
) == 0  # expected increase but got decrease

# All equal values
assert solution.countMatchingSubarrays(
    [5, 5, 5, 5],
    [0, 0]
) == 2  # equality pattern

# Strictly decreasing
assert solution.countMatchingSubarrays(
    [5, 4, 3, 2],
    [-1, -1]
) == 2  # decreasing windows

# Pattern length 1
assert solution.countMatchingSubarrays(
    [1, 3, 2, 2],
    [1]
) == 1  # only one increasing pair

# No matching subarrays
assert solution.countMatchingSubarrays(
    [1, 2, 3],
    [-1, -1]
) == 0  # impossible pattern

# Mixed repeated values
assert solution.countMatchingSubarrays(
    [3, 3, 2, 2, 5],
    [0, -1]
) == 1  # one matching sequence

# Entire array is one candidate
assert solution.countMatchingSubarrays(
    [1, 5, 5, 2],
    [1, 0, -1]
) == 1  # full array match

Test	Why
[1,2,3,4,5,6], [1,1]	Verifies repeated increasing matches
[1,4,4,1,3,5,5,3], [1,0,-1]	Confirms mixed comparison handling
[1,2], [1]	Minimum valid input
[2,1], [1]	Verifies mismatch handling
[5,5,5,5], [0,0]	Tests equality comparisons
[5,4,3,2], [-1,-1]	Tests decreasing relationships
[1,3,2,2], [1]	Validates smallest pattern size
[1,2,3], [-1,-1]	Ensures zero matches work correctly
[3,3,2,2,5], [0,-1]	Tests repeated values with decrease
[1,5,5,2], [1,0,-1]	Validates single full-array candidate

Edge Cases

Pattern Length Equals One

When pattern has only one element, each candidate subarray contains exactly two numbers. This can expose off-by-one errors because the window size becomes very small.

For example:

nums = [1, 3, 2]
pattern = [1]

Only the pair [1,3] matches. The implementation handles this naturally because relations becomes length n - 1, and we simply compare one element at a time.

Repeated Equal Numbers

Equality conditions can easily introduce bugs if the implementation only checks greater-than or less-than comparisons.

For example:

nums = [5,5,5,5]
pattern = [0,0]

The comparison array becomes:

[0,0,0]

Our implementation explicitly adds 0 when adjacent values are equal, ensuring equality patterns work correctly.

No Matching Subarrays

Some inputs may contain no valid matches at all.

For example:

nums = [1,2,3]
pattern = [-1,-1]

The comparison array is:

[1,1]

Since no window matches the target pattern, the counter remains 0. The implementation safely returns zero without any special handling.

Entire Array Is the Only Candidate

When:

pattern.length = nums.length - 1

there is only one possible subarray to check.

For example:

nums = [1,5,5,2]
pattern = [1,0,-1]

The algorithm still works because the sliding window loop runs exactly once and verifies the only candidate correctly.