Number of Subarrays That Match a Pattern I

Medium
1765.

Number of Subarrays That Match a Pattern I

Number of Subarrays That Match a Pattern I is a medium coding problem on arrays, rolling hash and string matching, asked in Amazon interviews.

You are given an integer array nums of length n and an array pattern of length m whose entries are each -1, 0 or 1.

A subarray nums[i..i+m] (of size m + 1) matches the pattern when, for every k from 0 to m - 1:

  • 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 number of subarrays of nums that match pattern.

Example 1

Input
nums = [1,2,3,4,5,6], pattern = [1,1]
Output
4
Explanation
Every window of three consecutive values is strictly increasing: [1,2,3], [2,3,4], [3,4,5] and [4,5,6].

Example 2

Input
nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output
2
Explanation
[1,4,4,1] and [3,5,5,3] go up, stay level, then go down.

Example 3

Input
nums = [7,7,7,7], pattern = [0,0,0]
Output
1
Explanation
The only subarray of size 4 is the whole array, and it never changes.

Constraints

  • 2 <= n == nums.length <= 100
  • 1 <= nums[i] <= 10^9
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number[]} pattern
 * @return {number}
 */
var countMatchingSubarrays = function(nums, pattern) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Subarrays That Match a Pattern I — Solution

Number of Subarrays That Match a Pattern I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Number of Subarrays That Match a Pattern I is a medium coding problem on arrays, rolling hash and string matching, asked in Amazon interviews.

  • Difficulty: Medium
  • Topics: Arrays, Rolling Hash, String Matching
  • Asked at: Amazon
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given an integer array nums of length n and an array pattern of length m whose entries are each -1, 0 or 1.

A subarray nums[i..i+m] (of size m + 1) matches the pattern when, for every k from 0 to m - 1:

  • 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 number of subarrays of nums that match pattern.

Example 1

Input: nums = [1,2,3,4,5,6], pattern = [1,1]
Output: 4
Explanation: Every window of three consecutive values is strictly increasing: [1,2,3], [2,3,4], [3,4,5] and [4,5,6].

Example 2

Input: nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output: 2
Explanation: [1,4,4,1] and [3,5,5,3] go up, stay level, then go down.

Example 3

Input: nums = [7,7,7,7], pattern = [0,0,0]
Output: 1
Explanation: The only subarray of size 4 is the whole array, and it never changes.

Constraints

  • 2 <= n == nums.length <= 100
  • 1 <= nums[i] <= 10^9
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1

Hints for Number of Subarrays That Match a Pattern I

  1. Hint 1

    A pattern entry only describes how one element compares with the next one.

  2. Hint 2

    For every start i, walk k from 0 to m - 1 and compare the sign of nums[i + k + 1] - nums[i + k] with pattern[k].

  3. Hint 3

    Stop a start early at its first mismatch and count the starts that survive all m comparisons.

How to solve Number of Subarrays That Match a Pattern I

With n <= 100 each of the n - m candidate subarrays can be checked against the pattern directly — one comparison of neighbours per pattern entry.

Approach

  1. For every start i with i + m < n:
  2. for k = 0 .. m - 1, compute s = 1 if nums[i+k+1] > nums[i+k], 0 if equal, -1 if smaller; if s != pattern[k], the start fails.
  3. Count the starts that never fail.

Why it works

The definition of a match is exactly these m neighbour comparisons, and every subarray of size m + 1 is identified by its start i, so each candidate is tested once against the full definition.

Complexity

  • Time — O(n * m)
  • Space — O(1)

Pitfalls

  • The subarray has m + 1 elements, so the last start is n - m - 1.
  • Compare values rather than subtracting into a sign in languages where a difference could overflow — here values are at most 10^9, so a difference fits in 32 bits, but a comparison is clearer.

Reference solution

Python

from typing import List

def countMatchingSubarrays(nums: List[int], pattern: List[int]) -> int:
    n, m = len(nums), len(pattern)
    res = 0
    for i in range(n - m):
        ok = True
        for k in range(m):
            a, b = nums[i + k], nums[i + k + 1]
            s = 1 if b > a else (0 if b == a else -1)
            if s != pattern[k]:
                ok = False
                break
        if ok:
            res += 1
    return res

Java

public static int countMatchingSubarrays(int[] nums, int[] pattern) {
    int n = nums.length, m = pattern.length, res = 0;
    for (int i = 0; i + m < n; i++) {
        boolean ok = true;
        for (int k = 0; k < m; k++) {
            int s = Integer.compare(nums[i + k + 1], nums[i + k]);
            if (s != pattern[k]) { ok = false; break; }
        }
        if (ok) res++;
    }
    return res;
}

C++

int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
    int n = nums.size(), m = pattern.size(), res = 0;
    for (int i = 0; i + m < n; i++) {
        bool ok = true;
        for (int k = 0; k < m; k++) {
            int a = nums[i + k], b = nums[i + k + 1];
            int s = (b > a) - (b < a);
            if (s != pattern[k]) { ok = false; break; }
        }
        if (ok) res++;
    }
    return res;
}

JavaScript

var countMatchingSubarrays = function(nums, pattern) {
    var n = nums.length, m = pattern.length, res = 0;
    for (var i = 0; i + m < n; i++) {
        var ok = true;
        for (var k = 0; k < m; k++) {
            var a = nums[i + k], b = nums[i + k + 1];
            var s = b > a ? 1 : (b === a ? 0 : -1);
            if (s !== pattern[k]) { ok = false; break; }
        }
        if (ok) res++;
    }
    return res;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays