Summary

Solution


Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

The simplest method is to consider every possible subarray of the given array, find the sum of the elements of each of those subarrays and check for the equality of the sum obtained with the given . Whenver the sum equals , we can increment the used to store the required result.

Complexity Analysis

  • Time complexity : . Considering every possible subarray takes time. For each of the subarray we calculate the sum taking time in the worst case, taking a total of time.

  • Space complexity : . Constant space is used.


Approach #2 Using Cummulative sum [Accepted]

Algorithm

Instead of determining the sum of elements everytime for every new subarray considered, we can make use of a cumulative sum array , . Then, in order to calculate the sum of elements lying between two indices, we can subtract the cumulative sum corresponding to the two indices to obtain the sum directly, instead of iterating over the subarray to obtain the sum.

In this implementation, we make use of a cumulative sum array, , such that is used to store the cumulative sum of array upto the element corresponding to the index. Thus, to determine the sum of elements for the subarray , we can directly use .

Complexity Analysis

  • Time complexity : . Considering every possible subarray takes time. Finding out the sum of any subarray takes time after the initial processing of for creating the cumulative sum array.

  • Space complexity : . Cumulative sum array of size is used.


Approach #3 Without space [Accepted]

Algorithm

Instead of considering all the and points and then finding the sum for each subarray corresponding to those points, we can directly find the sum on the go while considering different points. i.e. We can choose a particular point and while iterating over the points, we can add the element corresponding to the point to the sum formed till now. Whenver the equals the required value, we can update the value. We do so while iterating over all the indices possible for every index. Whenver, we update the index, we need to reset the value to 0.

Complexity Analysis

  • Time complexity : . We need to consider every subarray possible.

  • Space complexity : . Constant space is used.


Approach #4 Using hashmap [Accepted]

Algorithm

The idea behind this approach is as follows: If the cumulative sum(repreesnted by for sum upto index) upto two indices is the same, the sum of the elements lying in between those indices is zero. Extending the same thought further, if the cumulative sum upto two indices, say and is at a difference of i.e. if , the sum of elements lying between indices and is .

Based on these thoughts, we make use of a hashmap which is used to store the cumulative sum upto all the indices possible along with the number of times the same sum occurs. We store the data in the form: . We traverse over the array and keep on finding the cumulative sum. Every time we encounter a new sum, we make a new entry in the hashmap corresponding to that sum. If the same sum occurs again, we increment the count corresponding to that sum in the hashmap. Further, for every sum encountered, we also determine the number of times the sum has occured already, since it will determine the number of times a subarray with sum has occured upto the current index. We increment the by the same amount.

After the complete array has been traversed, the gives the required result.

The animation below depicts the process.

!?!../Documents/560_Subarray.json:1000,563!?!

Complexity Analysis

  • Time complexity : . The entire array is traversed only once.

  • Space complexity : . Hashmap can contain upto distinct entries in the worst case.


Analysis written by: @vinod23