Scale Engineer

Number of Subarrays That Match a Pattern I

Med
#2702Time: O(n * m). The outer loop runs `n - m` times, and for each iteration, the inner loop runs `m` times. This gives a total complexity proportional to `(n-m)*m`.Space: O(1). We only use a few variables to keep track of the count and loop indices, so the space used is constant.3 companies
Patterns
String MatchingRolling HashHash Function
Data structures
Array
Companies
VisaCapital OneAutodesk

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. We iterate through all possible starting positions for a subarray of size m+1 in the nums array. For each potential subarray, we check if it matches the given pattern by comparing adjacent elements according to the pattern's rules.

Algorithm

  • Initialize a counter count to 0.
  • Iterate with an index i from 0 to n - m - 1. This i represents the start of a potential matching subarray in nums.
  • For each i, assume a match is found by setting a boolean flag, e.g., isMatch = true.
  • Start an inner loop with index k from 0 to m - 1. This k corresponds to the index in the pattern array.
  • Inside the inner loop, check the relationship between nums[i + k + 1] and nums[i + k] against pattern[k].
  • If the condition for pattern[k] is not satisfied, set isMatch to false and break the inner loop.
  • After the inner loop, if isMatch is still true, increment count.
  • Return count after the outer loop finishes.

Walkthrough

We need to find subarrays of nums of length m+1. A subarray can start at index i and end at index i+m. The possible values for i range from 0 to n - (m + 1). We use an outer loop to iterate through each possible starting index i. Inside this loop, we assume the current subarray is a match and use an inner loop to verify this assumption. The inner loop iterates from k = 0 to m-1, checking the condition for pattern[k]. For each k, we compare nums[i + k + 1] with nums[i + k]. If any of these conditions are not met, the current subarray starting at i is not a match. We break the inner loop and proceed to the next starting index i+1. If the inner loop completes without finding any mismatch, it means the subarray nums[i...i+m] is a valid match, and we increment a counter. After the outer loop finishes, the counter will hold the total number of matching subarrays.

class Solution {    public int countMatchingSubarrays(int[] nums, int[] pattern) {        int n = nums.length;        int m = pattern.length;        int count = 0;        // Iterate through all possible starting positions of a subarray of size m+1        for (int i = 0; i <= n - m - 1; i++) {            boolean isMatch = true;            // Check if the subarray nums[i...i+m] matches the pattern            for (int k = 0; k < m; k++) {                if (pattern[k] == 1) {                    if (nums[i + k + 1] <= nums[i + k]) {                        isMatch = false;                        break;                    }                } else if (pattern[k] == 0) {                    if (nums[i + k + 1] != nums[i + k]) {                        isMatch = false;                        break;                    }                } else { // pattern[k] == -1                    if (nums[i + k + 1] >= nums[i + k]) {                        isMatch = false;                        break;                    }                }            }            if (isMatch) {                count++;            }        }        return count;    }}

Complexity

Time

O(n * m). The outer loop runs `n - m` times, and for each iteration, the inner loop runs `m` times. This gives a total complexity proportional to `(n-m)*m`.

Space

O(1). We only use a few variables to keep track of the count and loop indices, so the space used is constant.

Trade-offs

Pros

  • Easy to understand and implement.

  • Minimal space usage (O(1)).

  • Sufficiently fast for the given constraints (n <= 100).

Cons

  • Inefficient for larger inputs, as it involves nested loops leading to a time complexity of O(n*m).

Solutions

public class Solution {    public int CountMatchingSubarrays(int[] nums, int[] pattern) {        int n = nums.Length, m = pattern.Length;        int ans = 0;        for (int i = 0; i < n - m; ++i) {            int ok = 1;            for (int k = 0; k < m && ok == 1; ++k) {                if (f(nums[i + k], nums[i + k + 1]) != pattern[k]) {                    ok = 0;                }            }            ans += ok;        }        return ans;    }    private int f(int a, int b) {        return a == b ? 0 : (a < b ? 1 : -1);    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem