Arrays - Continuous Subarray Sum

Given an integer array nums and an integer k, return true if nums has a good subarray or false otherwise.

A good subarray is a subarray where:

its length is at least two, and
the sum of the elements of the subarray is a multiple of k.

Note that:

A subarray is a contiguous part of the array.
An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k.

Input: nums = [23, 2, 4, 6, 7], k = 6
Output: true
Explanation: [2, 4] is a continuous subarray of size 2 whose elements sum up to 6.

Input: nums = [23, 2, 6, 4, 7], k = 6
Output: true
Explanation: [23, 2, 6, 4, 7] is an continuous subarray of size 5 whose elements sum up to 42.
42 is a multiple of 6 because 42 = 7 * 6 and 7 is an integer.

Input: nums = [23,2,6,4,7], k = 13
Output: false
Explanation: There is no contiguous subarray that adds upto 13 or multiples of 13.

Constraints:

1 < nums.length <= 10⁵
0 <= nums[i] <= 10⁹
0 <= sum(nums[i]) <= 2³¹ - 1
1 <= k <= 2³¹ - 1

Solution 1 - Create prefix sum array and then find if there is a possible continuous subarray with K multiples

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.

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Complexity Analysis: