The Number of Subarrays That Match a Pattern I problem gives you an integer array nums and a pattern array where each pattern element is -1 (decrease), 0 (same), or 1 (increase). Count subarrays of nums whose consecutive differences match the pattern exactly. This coding problem uses rolling hash or KMP string matching after encoding nums's differences into a comparison string.
Uber, Visa, Amazon, and Google ask this because it requires transforming a numeric comparison problem into a string matching problem. By encoding each consecutive pair in nums as -1, 0, or 1, you get a comparison array that can be pattern-matched using KMP or rolling hash. The array, string matching, hash function, and rolling hash interview pattern is the core.
Encode + KMP/Rolling hash. Create array encoded[i] = sign(nums[i+1] - nums[i]) for i=0..n-2 (values: -1, 0, or 1). Now count occurrences of pattern as a subarray in encoded using KMP or rolling hash. This transforms the problem from numeric to string matching.
nums=[1,2,3,4,2,3]. pattern=[1,1] (increase, increase). encoded=[1,1,1,-1,1] (differences: +1,+1,+1,-2,+1 → signs: 1,1,1,-1,1). Find [1,1] in [1,1,1,-1,1]: positions 0,1,2. Count = 4 (at positions 0,1,2,3? Let's check: [1,1] at index 0-1 ✓, 1-2 ✓, 2-3? [1,-1]✗. So count=2).
sign(diff) must be exactly -1, 0, or 1.Pattern matching on derived comparison sequences is a powerful reduction technique. Convert any "monotone comparison pattern" to a ternary string (-1,0,1), then apply KMP. This transformation makes the problem solvable with standard string matching algorithms. Practice encoding-then-matching for problems involving "detect ascending patterns," "detect wave patterns," and similar sequence recognition tasks.