Number of Subarrays That Match a Pattern I - KMP Algorithm [JS]
Description Solution: KMP Algorithm Create an array relation of length n - 1 representing the relationship between each pair of adjacent numbers in nums . nums[i] < nums[i + 1]: 1 nums[i] === nums[i + 1]: 0 nums[i] > nums[i + 1]: -1 From there, the problem boils down to finding the number of exact matches of pattern in relation . Use the KMP algorithm to find the number of matches in O(n + m) . n = length of nums , m = length of pattern Time Complexity: O(n + m) Space Complexity: O(n + m) var countMatchingSubarrays = function ( nums, pattern ) { let n = nums.length, relation = Array (n - 1 ).fill( 0 ); for ( let i = 0 ; i < n - 1 ; i++) { if (nums[i] < nums[i + 1 ]) relation[i] = 1 ; else if (nums[i] === nums[i + 1 ]) relation[i] = 0 ; else relation[i] = - 1 ; } return kmp(relation, pattern); }; function kmp ( arr, subarray ) { let lps = getLPS(subarray); let n...