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 <= 1061 <= nums[i] <= 1091 <= m == pattern.length < n-1 <= pattern[i] <= 1When 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:
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:
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_matchesAdjacent 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:
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| Case | How to Handle |
|---|---|
| The array strictly increases and the pattern is all rises | Every window of the required length matches, so the count is the number of those windows. |
| The pattern contains a single rule | 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 | No window can satisfy every rule, so the count is zero. |
| A pair is equal where the pattern expects a rise | That window is rejected at the first disagreement. |
| Several overlapping windows all match | Each starting position contributes one to the count. |
| The pattern mixes rises, ties, and drops | A window is kept only when every consecutive pair agrees with its rule. |