Number of Subarrays That Match a Pattern II

Number of Subarrays That Match a Pattern II - 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] 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.

Input & Output

Example 1 — Basic Pattern Match

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

› Output: 3

💡 Note: Three subarrays match: [1,2,3] (1<2<3), [2,3,4] (2<3<4), [3,4,5] (3<4<5). Each satisfies pattern [1,1] meaning both comparisons are increasing.

Example 2 — Mixed Pattern

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

› Output: 1

💡 Note: Only subarray [1,4,4,1] matches: 1<4 (pattern[0]=1), 4=4 (pattern[1]=0), 4>1 (pattern[2]=-1).

Example 3 — No Matches

$ Input: nums = [1,2,3], pattern = [-1]

› Output: 0

💡 Note: Pattern [-1] requires decreasing, but we have [1,2] and [2,3] which are both increasing. No matches found.

Constraints

2 ≤ nums.length ≤ 10⁶
1 ≤ pattern.length ≤ nums.length - 1
pattern[i] is -1, 0, or 1
-10⁹ ≤ nums[i] ≤ 10⁹

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

nums array and pattern of comparison rules

Pattern Matching

Check subarrays against pattern rules

Count Matches

Return total number of matching subarrays

Key Takeaway

🎯 Key Insight: Transform numeric comparisons into string pattern matching for efficient searching

Asked in

G Google 25 f Facebook 18 M Microsoft 15

The key insight is to transform this into a string matching problem by converting adjacent number comparisons into symbols. The optimal approach uses KMP string matching after converting nums to comparison symbols and pattern to target string. Time: O(n + m), Space: O(n + m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check Every Subarray	O(n×m)	O(1)	Check each possible subarray of length m+1 against the pattern
Rolling Hash String Matching	O(n + m)	O(n + m)	Convert to string comparison problem and use efficient string matching

Brute Force - Check Every Subarray — Algorithm Steps

Iterate through all possible starting positions
For each position, check if subarray matches pattern
Count valid matches

Visualization

Tap to expand

Step-by-Step Walkthrough

Start Position

Select starting position for subarray

Pattern Check

Compare adjacent elements with pattern rules

Count Matches

Increment counter if pattern matches

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int numsSize, int* pattern, int patternSize) {
    int count = 0;
    
    // Check each possible starting position
    for (int i = 0; i <= numsSize - patternSize - 1; i++) {
        int match = 1;
        // Check if subarray nums[i:i+patternSize+1] matches pattern
        for (int j = 0; j < patternSize; j++) {
            if (pattern[j] == 1 && nums[i + j + 1] <= nums[i + j]) {
                match = 0;
                break;
            } else if (pattern[j] == 0 && nums[i + j + 1] != nums[i + j]) {
                match = 0;
                break;
            } else if (pattern[j] == -1 && nums[i + j + 1] >= nums[i + j]) {
                match = 0;
                break;
            }
        }
        
        if (match) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char line[10000];
    
    // Parse nums array
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0; // Remove newline
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse pattern array
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0; // Remove newline
    
    int pattern[1000];
    int patternSize = 0;
    token = strtok(line + 1, ",]"); // Skip opening bracket
    while (token != NULL) {
        pattern[patternSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize, pattern, patternSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×m)

For each of n-m starting positions, we check m pattern elements

✓ Linear Growth

Space Complexity

O(1)

Only using constant extra space for variables

✓ Linear Space

15.4K Views

Medium Frequency

~35 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check Every Subarray — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler