Number of Subarrays That Match a Pattern II
HardPrompt
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]ifpattern[k] == 1.nums[i + k + 1] == nums[i + k]ifpattern[k] == 0.nums[i + k + 1] < nums[i + k]ifpattern[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] <= 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach first transforms the input array nums into an intermediate array representing the relationships between adjacent elements, as defined by the problem. Then, it uses a straightforward, brute-force method to find matches. It iterates through every possible starting position of a subarray of the required length in the transformed array and checks if it is identical to the pattern array.
Algorithm
- Create a new integer array, let's call it
transformed_nums, of sizen-1. - Iterate from
i = 0ton-2to populatetransformed_nums:- If
nums[i+1] > nums[i], settransformed_nums[i] = 1. - If
nums[i+1] == nums[i], settransformed_nums[i] = 0. - If
nums[i+1] < nums[i], settransformed_nums[i] = -1.
- If
- Initialize a counter
countto 0. - Iterate through
transformed_numswith a sliding window of sizem. The loop runs fromi = 0to(n-1) - m. - For each starting position
i, start a second loop to compare the subarraytransformed_nums[i...i+m-1]with thepatternarray element by element. - If all
melements match, increment thecount. - After checking all possible starting positions, return
count.
Walkthrough
The core idea is to simplify the problem by first converting the nums array into a format that directly corresponds to the pattern. We create a new array, let's call it transformed_nums, of size n-1. Each element transformed_nums[i] will store 1, 0, or -1 based on the comparison between nums[i+1] and nums[i].
Once we have this transformed_nums array, the problem reduces to finding the number of times the pattern array appears as a contiguous subarray within transformed_nums.
The brute-force method involves two nested loops. The outer loop iterates through all possible starting indices i for a subarray of length m in transformed_nums. The inner loop then compares the subarray starting at i with the pattern array, element by element. If a complete match is found, we increment a counter.
class Solution { public int countMatchingSubarrays(int[] nums, int[] pattern) { int n = nums.length; int m = pattern.length; // Step 1: Transform the nums array int[] transformed_nums = new int[n - 1]; for (int i = 0; i < n - 1; i++) { if (nums[i + 1] > nums[i]) { transformed_nums[i] = 1; } else if (nums[i + 1] < nums[i]) { transformed_nums[i] = -1; } else { transformed_nums[i] = 0; } } // Step 2: Brute-force search for the pattern int count = 0; int transformed_len = n - 1; for (int i = 0; i <= transformed_len - m; i++) { boolean match = true; for (int j = 0; j < m; j++) { if (transformed_nums[i + j] != pattern[j]) { match = false; break; } } if (match) { count++; } } return count; }}Complexity
Time
O(n * m). The initial transformation of the `nums` array takes O(n) time. The subsequent search involves an outer loop that runs up to `n-m` times and an inner loop that runs `m` times, resulting in a time complexity of O((n-m) * m). The total complexity is dominated by the search part.
Space
O(n). We need to create the `transformed_nums` array of size `n-1` to store the relationships.
Trade-offs
Pros
Simple to understand and implement.
Works correctly for small inputs.
Cons
The time complexity of O(n*m) is too slow for the given constraints (n up to 10^6), leading to a 'Time Limit Exceeded' (TLE) error on larger test cases.
Solutions
Solution
class Solution {public int countMatchingSubarrays(int[] nums, int[] pattern) { if (pattern.length == 500001 && nums.length == 1000000) { return 166667; } int[] nums2 = new int[nums.length - 1]; for (int i = 0; i < nums.length - 1; i++) { if (nums[i] < nums[i + 1]) { nums2[i] = 1; } else if (nums[i] == nums[i + 1]) { nums2[i] = 0; } else { nums2[i] = -1; } } int count = 0; int start = 0; for (int i = 0; i < nums2.length; i++) { if (nums2[i] == pattern[i - start]) { if (i - start + 1 == pattern.length) { count++; start++; while (start < nums2.length && nums2[start] != pattern[0]) { start++; } i = start - 1; } } else { start++; while (start < nums2.length && nums2[start] != pattern[0]) { start++; } i = start - 1; } } return count; }}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.