Number of subarrays with given sum k

An algorithm to find the number of subarrays with given sum k.

We are going to implement two different algorithms to find the number of subarrays with a given sum in javascript. Everything will be written in ES6.

Bruteforce approach O(n ^ 2)

Implementation

• We will use two loops to traverse all the elements of the given array and find the subarrays.
• If the sum of all the elements of the subarray will equal to k then we will increase the count.

function countSubArrays(arr, k){
   //get the size the of the array
   let length = arr.length;
   
   //Keep the count
   let count = 0;

   //traverse through the array
   for(let i = 0; i < length; i++){
      //temp variables to store the sum
      let sum = 0;
     
      //traverse through the every next element after i
      for(let j = i; j < length; j++){    
         sum += arr[j];
         
         //if sum is equal to k then increase the count.
         if(sum === k){
           count++;
         }
      }
   }

   return count;
}

Input:
console.log(countSubArrays([3,4,-7,1,3,3,1,-4], 7));

Output:
4

Time complexity: O(N ^ 2).
Space complexity: O(1).

• We are using nested loops to find all the subarrays, so Time complexity is O(n ^ 2).
• We are using constant space to keep track of the count, so Space complexity is O(1).

Using hashtable to find the number of subarrays with given sum

The brute force solution works fine but it is slow. An effecient solution is to use map to find all the subarrays with given sum k and count them.

Implementation

• We will use a hashmap to keep track of sum of all the elements of the array.
• Then we will loop through the each element of array and add them to the current sum.
• If the current sum is equal to the given sum k then increase the count.
• If there is a element with the difference of current sum and given sum k in the hashmap then add its count to the total count.
• If the current sum is not in the hashmap then add it with count 1, else increment its count and repeat this for each element of the array.

function countSubArrays(arr, sum){
   //HashMap to keep track of the elements
   let prevSum = new Map();  
  
   //To count the subarrays
   let count = 0;  
        
   // Sum of elements so far.  
   let currsum = 0;  
        
   for (let i = 0; i < arr.length; i++) {  
        
      // Add current element to sum so far.  
      currsum += arr[i];  
        
      // If currsum is equal to desired sum,  
      // then a new subarray is found.   
      // So increase count of subarrays.  
      if (currsum == sum){   
           count++;          
      }
        
      // currsum has element
      // then add it to the count
      if (prevSum.has(currsum - sum)) {
          count += prevSum.get(currsum - sum); 
      }
                
        
      // Add currsum value to count of   
      // different values of sum.  
      let total = prevSum.get(currsum); 
      if (!total) {
          prevSum.set(currsum, 1); 
      }
      else{
         prevSum.set(currsum, total+1); 
      }
  }  
  
  return count;  
}

Input:
console.log(countSubArrays([3,4,-7,1,3,3,1,-4], 7));

Output:
4

Time complexity: O(n).
Space complexity: O(n).

• We are traversing each element of the array, so Time complexity is O(n).
• We are using hashmap to store the prevsum, so Space complexity is O(n).