LC 0523 [M] Continuous Subarray Sum - ALawliet/algorithms GitHub Wiki
math trick (running sum remainder k) and a hashmap and sliding window
remainder theorem (start%k) is same as (start+(mult*k))%k For e.g. in case of the array [23,2,6,4,7] the running (prefix) sum is [23,25,31,35,42] and the remainders of k=(6) are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number (12) which is multiple of the k. Hope this clarifies your doubt :)
remainder => last index seen = l
cur calculate the prefix sum remainder of input array A
seen will record the first occurrence of the remainder at r.
If we have seen the same remainder before at l,
it means the subarray sum A[l:r+1] if a multiple of k
then also check if it is at least 2 indexes away r-l >= 2
Can someone explain how space complexity is O(min(k,n))
there could be only up to k key-value pairs.
must set d[0] = -1 for edge cases like [2,4,3], [0,1]
Another way of thinking of this is for the corner case that we have 2 elements at the start of the array.
For example,
[2, 3] and k = 5
we won't find curr_sum (5) % 5 ==0 in dic
Another solution could be adding a 0 at the start of the array to fix this issue
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
d = {0: -1} # remainder to index last seen
runsum = 0
for r, num in enumerate(nums):
runsum += num
rem = runsum % k
if rem in d:
l = d[rem]
if r - l >= 2:
return True
else:
d[rem] = r
return False
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
rem_to_firstindex = {0: -1}
cumsum = 0
for r, num in enumerate(nums):
cumsum += num
if k:
rem = cumsum % k # to find multiples of k, store the remainder
cumsum = rem # decrement the cumsum
# true if seen at least 2 indexes ago = subarray size of at least 2
# print(f'{r} {cumsumr} {cumsumr_to_firstindex}')
if rem in rem_to_firstindex:
l = rem_to_firstindex[rem]
if r - l >= 2:
return True
else:
rem_to_firstindex[rem] = r
return False
# to remove the if-else (get or)setdefault
l = rem_to_firstindex.setdefault(rem, r)
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
if len(nums) < 2:
return False
d = {}
mod = 0
for i in range(len(nums)):
mod =(mod+nums[i])%k
if mod == 0 and i+1 >= 2:
return True
if mod in d:
if i - d[mod] >= 2:
return True
else:
d[mod] = i
return False
We iterate through the input array exactly once, keeping track of the running sum mod k of the elements in the process. If we find that a running sum value at index j has been previously seen before in some earlier index i in the array, then we know that the sub-array (i,j] contains a desired sum.
cur calculate the prefix sum remainder of input array A seen will record the first occurrence of the remainder. If we have seen the same remainder before, it means the subarray sum if a multiple of k
remainder theorem (a+(n*x))%x is same as (a%x) For e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42] and the remainders are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number which is multiple of the k. Hope this clarifies your doubt :)
When the index difference is greater than 1(at least 2), that actually indicates a subarray with at least 3 items the size of array index from i to j should be j-i+1.
Running sum from first element to index i : sum_i. If we mod k, it will be some format like : sum_i = k * x + modk_1
Running sum from first element to index j : sum_j. If we mod k, it will be some format like : sum_j = k * y + modk_2
If they have the same mod, which is modk_1 == modk_2, subtracting these two running sum we get the difference sum_i - sum_j = (x - y) * k = constant * k, and the difference is the sum of elements between index i and j, and the value is a multiple of k.
Suppose sum_i represents the running sum starting from index 0 and ending at i, once we find a mod that has been seen, say modk, we have: current one: sum_i = mk + modk previous one: sum_j = nk + modk Thus, sum_i - sum_j = (m - n) *k
so many traps here : k can be 0, element of the array can be 0, and also a single element is not allowed, at least two continuous elements ..👨🏻💻
To be honest, I was quite confused when I first saw the most voted answers and struggled a long time to understand why we should have the line map.put(0, -1); after initializing our hash map to store sum % k and the current index in the input array as key-value pairs.
But thanks to this great post (the solution for #437 Path Sum III: https://leetcode.com/problems/path-sum-iii/solution/), which explains thoroughly how prefix sum works, I came up with this version which corresponds with the "two cases" discussed in that very post. The only difference is that instead of storing the prefix sum at each index into hash map, we are storing the prefix sum mod by k, and we have one restriction that the subarray size should be greater than 1.
So similarly, our code now looks like this:
Things we need to do
initialize hash map
initialize prefixSum variable
a for-loop to iterate over input array {
add up the current element to prefixSum, mod by k
discuss case 1 { found : return true }
discuss case 2 { found : return true }
store the current mod value into hash map if no answer is found, continue the for-loop
}
return false if we exhaust all possible cases