#3034

Medium

LeetCode Problem Workspace

Number of Subarrays That Match a Pattern I

Count all subarrays in a given integer array that strictly follow a defined numeric pattern using rolling hash checks efficiently.

array rolling hash string matching hash function

Problem Statement

You are given a 0-indexed integer array nums of size n, and a 0-indexed integer array pattern of size m containing only -1, 0, and 1. A subarray nums[i..i+m] matches the pattern if for every index k, nums[i+k+1] is greater than, equal to, or less than nums[i+k] according to pattern[k] being 1, 0, or -1 respectively.

Return the total number of subarrays in nums that satisfy the pattern constraints. Subarrays must be of length m+1, and each comparison must strictly follow the specified pattern directions.

Examples

Example 1

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

Output: 4

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

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 <= 100
1 <= nums[i] <= 109
1 <= m == pattern.length < n
-1 <= pattern[i] <= 1

Solution Approach

Iterate with Nested Loops

For each index i from 0 to n-m-1, check the subarray nums[i..i+m] by comparing consecutive elements according to pattern. Increment a count if all elements satisfy the pattern's signs.

Rolling Hash for Differences

Compute a rolling hash of differences between consecutive nums elements. Compare the hash with a precomputed pattern hash to quickly identify matching subarrays without checking every element explicitly.

Combine Direct Comparison and Hash Verification

Use direct comparison for the first few subarrays to confirm correctness, then rely on rolling hash to slide across the array efficiently. This ensures both accuracy and performance for medium-sized arrays.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n*m) for direct comparison, reduced to O(n) using rolling hash. Space complexity is O(1) extra for counters and O(m) for hash storage of the pattern.

What Interviewers Usually Probe

Looking for subarrays matching a sequence of relative comparisons, not exact values.
Hinting to consider pattern length and efficient checking, possibly via rolling hash.
Expect awareness of off-by-one errors when indexing subarrays.

Common Pitfalls or Variants

Common pitfalls

Forgetting that subarray length is pattern length plus one, leading to index errors.
Comparing values directly without considering the sign mapping of pattern elements.
Failing to update rolling hash correctly when sliding the window.

Follow-up variants

Pattern may include only increasing or decreasing sequences, simplifying checks.
Array elements could be negative or larger ranges, requiring hash adjustments.
Pattern length varies, affecting performance and hash collision probability.

FAQ

What is the main idea behind Number of Subarrays That Match a Pattern I?

The main idea is to count all subarrays of length m+1 where consecutive differences match the pattern of -1, 0, or 1.

Can rolling hash improve performance here?

Yes, a rolling hash on differences allows O(1) checks when sliding across subarrays instead of recalculating every comparison.

What is the role of pattern length?

Pattern length determines subarray size, affects loop ranges, and directly influences time complexity and hash size.

How do I handle equality in the pattern?

Pattern elements of 0 indicate consecutive numbers must be equal; verify this explicitly or via the hash of differences.

What errors should I avoid?

Avoid off-by-one errors, misinterpreting pattern signs, and incorrect rolling hash updates when moving the subarray window.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
        def f(a: int, b: int) -> int:
            return 0 if a == b else (1 if a < b else -1)

        ans = 0
        for i in range(len(nums) - len(pattern)):
            ans += all(
                f(nums[i + k], nums[i + k + 1]) == p for k, p in enumerate(pattern)
            )
        return ans

Continue Practicing

#3036 number of subarrays that match a pattern ii #3042 count prefix and suffix pairs i #3045 count prefix and suffix pairs ii