Missing Test Case - 3036. Number of Subarrays That Match a Pattern II #20278
Description
LeetCode Username
b03201008
Problem number, title, and link
Number of Subarrays That Match a Pattern II https://leetcode.com/problems/number-of-subarrays-that-match-a-pattern-ii/
Category of the bug
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
Description of the bug
Code that uses fixed base and mod in hashing got "Accepted" verdict, while there are many tests when collision happens.
Language used for code
Python3
Code used for Submit/Run operation
class Solution:
def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
n = len(nums)
arr = []
for i in range(1, n):
if nums[i] == nums[i-1]:
arr.append(0)
if nums[i] > nums[i-1]:
arr.append(1)
if nums[i] < nums[i-1]:
arr.append(-1)
p = 234213
mod = 10**9+7
a = 0
base = 1
for i in pattern:
a *= p
a %= mod
a += i + 10123
a %= mod
base *= p
base %= mod
m = len(pattern)
b = 0
res = 0
for i in range(n-1):
b *= p
b %= mod
b += arr[i] + 10123
b %= mod
if i >= m:
b -= base * (arr[i - m] + 10123)
b %= mod
if b == a:
res += 1
# print(a, b)
return res
Expected behavior
When
nums = [8,7,6,5,4,3,4,3,4,5,4,3,2,1,2]
pattern = [1,0,1,0,0,-1,-1,-1,-1,1,1,1,0,-1]
the expected answer is 0, but the code outputs 1.
Screenshots
