Continuous Subarray Sum

In this approach, we will first compute a prefix sum array, then to find contiguous subarray which is multiple of k is:

• Loop through prefix sum array, and divide the prefix sum with k and store the remainder and current index index into a HashMap. The reason why we are storing indexes is to check minimum array length when we find a subarray with multiple of k, the subarray length should be atleast 2.
• When you put remainder into HashMap, check if it already exists, that means current prefix is a multiple of k.
  For example if the input array is [23, 4, 2] and k=6, then prefix sum array will be [23, 27, 29]
  • If we divide 23 with 6, we get remainder as 5 for index 0.
  • For index 1, we get remainder as 3.
  • For index 2, we get remainder as 5, but there is already a remainder 5 at index 0, so this means that the cumulative sum after index 0, is a multiple of 6 (which is 4, 2).
• If the remainder not exists, then we simply add it to the HashMap with its index as value.
• There are two edge cases:
  • First number in the input array is multiple of k, for example [24,....] and k =6, we will get remainder as 0, but the array length at this index is 1.
  • 0 is also a multiple of k, so there may be scenario which has 0's in the input array, for example [0, 0, 2] . Checking for
  To handle these usecases, we will pre-populate remainder HashMap with 0 as key and -1 as value. So that when we check indexes differences it wont match minimum length of 2.

import java.util.Arrays;
import java.util.HashMap;

public class ContiguousSubArraySum {

    static boolean checkSubArraySum(int[] nums, int k) {
        HashMap<Integer, Integer> remainderToIndexMap = new HashMap<>(nums.length);
        remainderToIndexMap.put(0, -1);

        for(int i=0; i<nums.length; i++) {
            nums[i] = nums[i] + (i==0 ? 0 : nums[i-1]);
            int remainder  = nums[i] % k;
            Integer index = remainderToIndexMap.get(remainder);
            if(index == null) {// remainder not exists, then we add it
                remainderToIndexMap.put(remainder, i);
            } else if (i - index >=2) { // subarray min length of 2 or more, we have found answer
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        System.out.println(checkSubArraySum(new int[] {23,2,4,6,7}, 6));
        System.out.println(checkSubArraySum(new int[] {24,2,4,6,7}, 6));
        System.out.println(checkSubArraySum(new int[] {24,0}, 6));
        System.out.println(checkSubArraySum(new int[] {0,0}, 6));

        System.out.println(checkSubArraySum(new int[] {24}, 6)); // will produce false, since length is 1.
        System.out.println(checkSubArraySum(new int[] {24,1}, 6)); // will produce false, since length is 1.

    }
}

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the length of nums array.
Space complexity: O(n), since we are creating prefix sum array with size n and a HashMap to keep the remainders and indexes.