523. Continuous Subarray Sum


Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

  1. The length of the array won't exceed 10,000.
  2. You may assume the sum of all the numbers is in the range of a signed 32-bit integer.


Solution

Approach #1 Brute Force [Time Limit Exceeded]

The brute force approach is trivial. We consider every possible subarray of size greater than or equal to 2, find out its sum by iterating over the elements of the subarray, and then we check if the sum obtained is an integer multiple of the given .

Complexity Analysis

  • Time complexity : . Three for loops iterating over the array are used.
  • Space complexity : . Constant extra space is used.

Approach #2 Better Brute Force [Accepted]

Algorithm

We can optimize the brute force approach to some extent, if we make use of an array that stores the cumulative sum of the elements of the array, such that stores the sum of the elements upto the element of the array.

Thus, now as before, we consider every possible subarray for checking its sum. But, instead of iterating over a new subarray everytime to determine its sum, we make use of the cumulative sum array. Thus, to determine the sum of elements from the index to the index, including both the corners, we can use: .

Complexity Analysis

  • Time complexity : . Two for loops are used for considering every subarray possible.

  • Space complexity : . array of size is used.

Approach #3 Using HashMap [Accepted]

Algorithm

In this solution, we make use of a HashMap that is used to store the cumulative sums upto the index after some processing along with the index . The processing done is taking the modulus of the the sum upto the index with the given . The reasoning behind this will become clear soon.

We traverse over the given array, and keep on calculating the values upto the current index. Whenever we find a new value, which isn't present in the HashMap already, we make an entry in the HashMap of the form, .

Now, assume that the given value at the index be equal to . Now, if any subarray follows the element, which has a sum equal to the integer multiple of , say extending upto the index, the sum value to be stored in the HashMap for the index will be: , where is some integer > 0. We can observe that , which is the same value as stored corresponding to the index.

From this observation, we come to the conclusion that whenever the same value is obtained corresponding to two indices and , it implies that sum of elements betweeen those indices is an integer multiple of . Thus, if the same value is encountered again during the traversal, we return a directly.

The slideshow below depicts the process for the array nums: [2, 5, 33, 6, 7, 25, 15] and k=13.

!?!../Documents/523_Continous_Subarray_Sum.json:640,360!?!

Complexity Analysis

  • Time complexity : . Only one traversal of the array is done.

  • Space complexity : . The HashMap can contain upto different pairings.

Analysis written by: @vinod23

Submit Solution