Continuous Subarray Sum [Medium] — Prefix Modulo Map
Sanjeev SharmaAdvertisement
Problem Statement
Return true if the array has a good subarray (length >= 2) whose sum is a multiple of k.
Input: nums=[23,2,4,6,7], k=6 → true ([2,4])
Input: nums=[23,2,6,4,7], k=6 → true ([23,2,6,4,7] sum=42)
Intuition
If prefix[j] % k == prefix[i] % k and j-i >= 2, then subarray [i+1..j] is a multiple of k. Store first occurrence of each remainder.
Solutions
C++
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<int,int> first; first[0]=-1;
int prefix=0;
for(int i=0;i<nums.size();i++){
prefix=(prefix+nums[i])%k;
if(first.count(prefix)){if(i-first[prefix]>=2)return true;}
else first[prefix]=i;
}
return false;
}
Java
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer,Integer> first=new HashMap<>(); first.put(0,-1);
int prefix=0;
for(int i=0;i<nums.length;i++){
prefix=(prefix+nums[i])%k;
if(first.containsKey(prefix)){if(i-first.get(prefix)>=2)return true;}
else first.put(prefix,i);
}
return false;
}
Python
def checkSubarraySum(nums: list[int], k: int) -> bool:
first = {0: -1}
prefix = 0
for i, n in enumerate(nums):
prefix = (prefix + n) % k
if prefix in first:
if i - first[prefix] >= 2:
return True
else:
first[prefix] = i
return False
Complexity
- Time: O(n), Space: O(k)
Advertisement
