Taro Logo

Number of Subarrays That Match a Pattern II

Hard
Asked by:
Profile picture
15 views
Topics:
ArraysStrings

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

Solution


Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

  1. Is a matching subarray always exactly one element longer than the pattern?
  2. Does one require a strict rise, zero an equal pair, and negative one a strict drop?
  3. Are overlapping windows counted separately when each of them matches?
  4. If the pattern is empty, is every position in the array a match?
  5. What is returned when the pattern is longer than the adjacent pairs that exist?

Brute Force Solution

Approach

Every starting position that can hold a window one element longer than the pattern is examined. Inside that window, each pattern rule is compared with the neighboring pair at the same offset, and the first disagreement rejects the window. Each window that survives every rule adds one to the count.

Here's how the algorithm would work step-by-step:

  1. Set the match count to zero.
  2. Walk each starting index that leaves enough room for the pattern.
  3. At that start, assume the window matches until a rule fails.
  4. Read the pair of values sitting under the current pattern rule.
  5. Reject the window when a rise, tie, or drop disagrees with that rule.
  6. Stop checking the rest of a window as soon as it is rejected.
  7. Add one when every rule in the window agrees.

Code Implementation

class Solution:
    def countMatchingSubarrays(self, nums: list[int], pattern: list[int]) -> int:
        number_of_matches = 0
        nums_length = len(nums)
        pattern_length = len(pattern)

        # This loop iterates through all possible starting points for a subarray in nums.
        for starting_index in range(nums_length - pattern_length):
            is_match = True

            # This loop checks if the subarray starting at 'starting_index' matches the pattern.
            for pattern_index in range(pattern_length):
                current_num = nums[starting_index + pattern_index]
                next_num = nums[starting_index + pattern_index + 1]
                pattern_rule = pattern[pattern_index]

                # The core logic is to verify if the relationship between adjacent numbers in the subarray
                # conforms to the rule specified by the current element of the pattern.
                if pattern_rule == 1 and not (next_num > current_num):
                    is_match = False
                    break
                elif pattern_rule == 0 and not (next_num == current_num):
                    is_match = False
                    break
                elif pattern_rule == -1 and not (next_num < current_num):
                    is_match = False
                    break
            
            if is_match:
                number_of_matches += 1
        
        return number_of_matches

Big(O) Analysis

Time Complexity
O(n * m) – Let n be the length of the array and let m be the length of the pattern. The number of candidate starts is proportional to n, because each start only needs m plus one elements. Each start inspects up to m neighboring pairs, and the worst case checks every pair in every window. Multiplying the starts by the pattern length gives O(n * m) comparisons. No auxiliary table is built before the scan.
Space Complexity
O(1) – The scan keeps a match flag, the two indexes, and the running count. Those values are reused for every window. The array and the pattern are read in place. No copy of a window is stored. The extra memory is O(1).

Optimal Solution

Approach

Adjacent values are first rewritten as a rise, a tie, or a drop, so the pattern becomes an ordinary sequence search. A prefix table records, for each pattern position, the longest border that is both a prefix and a suffix. The search then walks the trend once, jumping to that border after a mismatch or a full match, and every time the pattern pointer reaches the end, one window has been found.

Here's how the algorithm would work step-by-step:

  1. Replace the array by the rise, tie, or drop between each adjacent pair.
  2. Return immediately when the pattern is empty or longer than that trend.
  3. Build the prefix table by growing a border while pattern symbols agree.
  4. On a disagreement inside the table, shrink the border to the border of the previous border.
  5. Walk the trend with a pattern pointer that advances on equal symbols.
  6. On a mismatch, move the pattern pointer through the prefix table, or advance the trend when the pointer is already at the start.
  7. Count a match whenever the pattern pointer reaches the pattern length, then resume at the pattern's own border.

Code Implementation

class Solution:
    def countMatchingSubarrays(self, nums: list[int], pattern: list[int]) -> int:
        def transform_to_trend(input_list):
            trend_sequence = []
            for index in range(len(input_list) - 1):
                if input_list[index+1] > input_list[index]:
                    trend_sequence.append(1)
                elif input_list[index+1] == input_list[index]:
                    trend_sequence.append(0)
                else:
                    trend_sequence.append(-1)
            return trend_sequence

        main_trend_sequence = transform_to_trend(nums)
        target_trend = pattern

        if not target_trend:
            return len(main_trend_sequence) + 1
        if len(target_trend) > len(main_trend_sequence):
            return 0

        # This 'recipe' (LPS array) pre-calculates the longest proper prefix of the pattern
        # that is also a suffix, enabling smart jumps on mismatches.
        longest_prefix_suffix_recipe = [0] * len(target_trend)
        length_of_previous_longest_prefix = 0
        index = 1
        while index < len(target_trend):
            if target_trend[index] == target_trend[length_of_previous_longest_prefix]:
                length_of_previous_longest_prefix += 1
                longest_prefix_suffix_recipe[index] = length_of_previous_longest_prefix
                index += 1
            else:
                if length_of_previous_longest_prefix != 0:
                    length_of_previous_longest_prefix = longest_prefix_suffix_recipe[length_of_previous_longest_prefix - 1]
                else:
                    longest_prefix_suffix_recipe[index] = 0
                    index += 1

        matches_found_count = 0
        main_sequence_pointer = 0
        target_trend_pointer = 0

        while main_sequence_pointer < len(main_trend_sequence):
            if target_trend[target_trend_pointer] == main_trend_sequence[main_sequence_pointer]:
                main_sequence_pointer += 1
                target_trend_pointer += 1
            else:
                # A mismatch occurred. We consult the 'recipe' to find the next best position
                # to resume matching, avoiding a full reset.
                if target_trend_pointer != 0:
                    target_trend_pointer = longest_prefix_suffix_recipe[target_trend_pointer - 1]
                else:
                    main_sequence_pointer += 1

            # If we've matched the entire pattern, we've found a valid subarray.
            if target_trend_pointer == len(target_trend):
                matches_found_count += 1

                # The 'recipe' helps us make the smartest jump forward to continue the search,
                # using the knowledge of the matched suffix.
                target_trend_pointer = longest_prefix_suffix_recipe[target_trend_pointer - 1]

        return matches_found_count

Big(O) Analysis

Time Complexity
O(n + m) – Building the trend looks at each adjacent pair once, which is proportional to n. Building the prefix table moves an index forward across the pattern, and every time the border shrinks it falls back to a shorter border that was already computed, so the table work is proportional to m. The search pointer on the trend also moves forward only, and the pattern pointer's retreats are paid for by earlier advances. Together the preparation and the search are O(n + m). Each symbol comparison is constant work.
Space Complexity
O(n + m) – The trend sequence stores one symbol for every adjacent pair, so it is proportional to n. The prefix table stores one integer for every pattern symbol, so it is proportional to m. A few pointers and the match count take constant space. The original array is not copied beyond the trend. The extra memory is O(n + m).

Edge Cases

The array strictly increases and the pattern is all rises
How to Handle:
Every window of the required length matches, so the count is the number of those windows.
The pattern contains a single rule
How to Handle:
Each adjacent pair is judged on its own, and each pair that agrees is counted.
The pattern is longer than the adjacent pairs in the array
How to Handle:
No window can satisfy every rule, so the count is zero.
A pair is equal where the pattern expects a rise
How to Handle:
That window is rejected at the first disagreement.
Several overlapping windows all match
How to Handle:
Each starting position contributes one to the count.
The pattern mixes rises, ties, and drops
How to Handle:
A window is kept only when every consecutive pair agrees with its rule.