523. Continuous Subarray Sum

Problem Statement

Pattern: Pattern Prefix Array

---

Solution

public static boolean checkSubArraySum(int[] nums, int k) {
	if (k == 0) return true;
 
	Map<Integer, Integer> map = new HashMap<>();
	int currSumMod = 0, index = -1;
	map.put(currSumMod,index++);
	
	for (; index < nums.length; index++) {
		// currSumMod is mod of sum so far
		currSumMod = (currSumMod + nums [index]) % k;
		// get prevIndex of currSumMod
		Integer prevIndex = map.get(currSumMod);
		// if prevIndex exists
		if (prevIndex != null) {
			// and index - prevIndex > 1
			if (index - prevIndex > 1) return true;
		}
		// else insert index for currSumMod
		else map.put(currSumMod, index);
	}
	return false;
}

Notes

• We simply store the Mod k of the current sum, in currSumMod
• If currSumMod gets repeated, then we know that the numbers in between the prevIndex and current index must add upto some multiple of k
  • For e.g. in case of the array [23,2,6,4,7] and k=6 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.
• Edge case: we initialise map with currSumMod = 0 and index = -1 since sum starts with 0, and we store it before the start of the array so index-prevIndex > 1 works
  • say at index = 1 currSumMod is 0. nums[0] + nums[1] == n . k (some multimple of k).
  • in that case it will look for 0 in the map, and if (index - prevIndex > 1) will return true like it should!