Skip to main content
Talentd

Number of Subarrays That Match a Pattern II - Solution & Explanation

HardArrayRolling HashString MatchingHash Function11 min readAsked at: Autodesk, Thoughtworks
Practice this problem

Problem Statement

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.

 

Constraints:

  • 2 <= n == nums.length <= 106
  • 1 <= nums[i] <= 109
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1

Approach Overview

Problem Overview: You get an integer array nums and a pattern array containing values -1, 0, and 1. The pattern describes how consecutive elements should compare (decreasing, equal, increasing). The task is to count how many subarrays of nums produce the same comparison pattern.

Approach 1: Sliding Window + Rolling Hash (O(n) time, O(n) space)

Convert the array into a comparison sequence where each adjacent pair becomes -1, 0, or 1. The problem then becomes classic pattern matching: find how many times the pattern appears inside this derived sequence. Apply a rolling hash (similar to Rabin–Karp) while sliding a window of length m across the comparison array. Each step updates the hash in constant time and compares it with the pattern hash. This avoids recomputing comparisons for every window and keeps the scan linear.

The key insight: subarray validity depends only on adjacent comparisons, not the actual numbers. By transforming the input into a comparison string, the task reduces to efficient substring matching using a rolling hash or other string matching technique.

Approach 2: Two-Pointer Optimization (O(n) time, O(1) space)

Instead of hashing, scan the comparison array using two pointers. Start a window where the pattern could match and compare each step with the expected pattern value. If a mismatch occurs, shift the starting pointer forward and restart matching. When all m comparisons match, increment the result and move forward to search for overlapping matches. Since each element participates in only a small number of checks, the overall complexity stays linear.

This approach relies purely on pointer movement and direct comparisons, making it memory efficient. It works well when the pattern length is relatively small compared to the input size.

Recommended for interviews: The sliding window with rolling hash is the most scalable and closest to standard pattern matching problems. Interviewers expect candidates to recognize the transformation from numeric comparisons to a sequence and apply techniques from array processing and substring search. The two-pointer approach demonstrates strong intuition and space optimization, but the hashing solution more clearly shows algorithmic pattern recognition.

Approach 1: Sliding Window Approach

This approach uses a sliding window that iterates over the nums array, checking each subarray of length m+1 to see if it matches the given pattern. By moving a window of this fixed length through nums, we can efficiently count the matching subarrays. This is a straightforward way to ensure that we are considering each subarray only once and directly comparing adjacent elements as specified by pattern.

This solution iterates through the array nums, using a sliding window of size m+1. For each potential starting index, it checks the conditions dictated by pattern on the subarray nums[i..i+m]. If all conditions are satisfied, we increment our counter for matching subarrays.

Code

PythonC++JavaJavaScript

Python

C++

Java

JavaScript

Complexity

The time complexity of this approach is O(n*m), as we're iterating over the nums array with a window of size m, and for each window position, we're checking conditions which take O(m) time. The space complexity is O(1) as we're using only a constant amount of extra space.

Try this approach in the editor →

Approach 2: Two-Pointer Optimization

This approach attempts to further optimize the sliding window by using two pointers, i and j, to skip unnecessary comparisons and focus only on valid starting points. This optimization works by finding the first valid point where a match might start, thereby potentially reducing average case runtime compared to the naive sliding window.

This attempt uses a while loop allowing for more advanced control over pointer movement, which can enable you to skip some repetitive computations on certain conditions. However, this is more complex and may not show significant gains compared to the sliding window in worst-case scenarios.

Code

Python

Python

Complexity

The time complexity remains O(n*m) in the worst case, but the two-pointer technique can sometimes offer O(n) on average if the skipping logic is soundly applied. Space complexity remains O(1).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sliding Window Approach

The time complexity of this approach is O(n*m), as we're iterating over the nums array with a window of size m, and for each window position, we're checking conditions which take O(m) time. The space complexity is O(1) as we're using only a constant amount of extra space.

Two-Pointer Optimization

The time complexity remains O(n*m) in the worst case, but the two-pointer technique can sometimes offer O(n) on average if the skipping logic is soundly applied. Space complexity remains O(1).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sliding Window + Rolling HashO(n)O(n)Best general solution for large arrays and long patterns
Two-Pointer OptimizationO(n)O(1)When pattern length is small and memory usage should stay minimal

Video Solution

3036. Number of Subarrays That Match a Pattern II | KMP | String Matching • Aryan Mittal • 4,712 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Number of Subarrays That Match a Pattern II easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing a transformation from numeric comparisons to pattern matching. Efficient solutions rely on rolling hash or linear scanning techniques rather than brute force enumeration of subarrays.
Number of Subarrays That Match a Pattern II Python/Java solution
Python, Java, C++, and JavaScript implementations typically convert the array into a comparison sequence and then apply sliding window hashing. Python versions often use simple integer hashing, while Java and C++ implementations may use modular rolling hash for collision safety.
How to solve Number of Subarrays That Match a Pattern II in O(n)?
First build a derived array that records whether each adjacent pair increases, decreases, or stays equal. Then search for the pattern inside this derived array using a rolling hash or linear sliding window comparison. Because the sequence is scanned once and hash updates are constant time, the total runtime is O(n).
What is the best approach for Number of Subarrays That Match a Pattern II?
The most reliable approach converts the array into a comparison sequence and applies sliding window pattern matching with a rolling hash. This reduces the task to substring search and runs in O(n) time. It scales well for large inputs and avoids recomputing comparisons for every subarray.
Is Number of Subarrays That Match a Pattern II asked at Google/Amazon/Meta?
Problems combining pattern matching and array transformations commonly appear in interviews at companies like Google, Amazon, and Meta. Variants test whether candidates recognize reductions to string matching techniques such as Rabin–Karp or KMP while maintaining linear complexity.
What data structure is used in Number of Subarrays That Match a Pattern II?
The solution primarily uses arrays along with a sliding window. Many implementations also rely on rolling hash values or hash-based comparisons to detect matches efficiently. These techniques come from string matching and hash function design.
What is the time complexity of Number of Subarrays That Match a Pattern II?
The optimal solution runs in O(n) time where n is the length of the input array. After converting the array into a comparison sequence of length n-1, a sliding window or rolling hash scans it once. Space complexity ranges from O(1) to O(n) depending on whether auxiliary arrays or hashing structures are used.

Ready to solve this problem?

Practice Number of Subarrays That Match a Pattern II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Match Substring After Replacement