The original question can be found here.
This question is quite tricky. I will say best of luck to you if this is the first time you see this question during a real interview. I’ll skip the brute force solution and let’s directly jump to the optimal solution.
We need to know a popular topic when dealing with subarray questions: prefix sum. If you are not familiar with this topic, please visit my another post here.
In this question, it’s a little different since we’ll be tracking sum’s remainder, with k as divisor. Consider the following example:
array: [23, 2, 4, 6, 7] k=6
prefix_remainder: [0, 5, 1, 5, 5, 0]When we get to element 4(index 2) in original array, the current remainder is 5, and we already have a 5 in the prefix_remainder hash table(or dictionary if you prefer). We know that elements between current 5 (inclusive) and the first 5 (exclusive), the sum of the numbers can be divided by k with no remainder, which means, it’s a multiple of k, then we find the answer.
2 things to note:
- Make sure the size of subarray is at least 2
- Remember to add
{0: -1}into the hash table. Why? Say this case[23, 2, 4, 6, 6] with k=7, and the corresponding prefix_mod is[2, 4, 1, 0, 6]. We know that 23+2+4+6=35 which is divisible by 7, but 0 never appeared in the hash table before, so we can add{0: -1}to fix this edge case.
Here’s the code:
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
# key is remainder, value is index in nums array
prefix_remainder_seen = {0: -1}
prefix_remainder = 0
for i in range(len(nums)):
prefix_remainder = (prefix_remainder + nums[i]) % k
if prefix_remainder in prefix_remainder_seen:
if i - prefix_remainder_seen[prefix_remainder] > 1:
return True
else:
prefix_remainder_seen[prefix_remainder] = i
return FalseTime complexity is: O(n), space complexity is: O(n).