Program to check if a subarray with 0 sum exits or not

We will implement a simple algorithm in javascript to check if an array has a subarray with 0 sum or not. Everything will be written in ES6.

Example

Input:
[3, 4, -7, 3, 1, 3, 1, -4, -2, -2]

Output:
true
[3, 4, -7]
[4, -7, 3]
[-7, 3, 1, 3]
[3, 1, -4]
[3, 1, 3, 1, -4, -2, -2]
[3, 4, -7, 3, 1, 3, 1, -4, -2, -2]

A naive solution O(n ^ 2).

Implementation

• We are going to traverse and sum all the subarrays of the given array and check if they are equal to 0.
• If they are equal to 0 then return true else return false.

let subWithZero = (arr) => {
  //loop through the array
  for(let i = 0; i < arr.length; i++){
    let sum = arr[i];
    //Check if initial item is zero then return true 
    if(sum === 0){
      return true;
    }
    
    for(let j = i; j < arr.length; j++){
      //If there is any subarray with zero then return true
      sum += arr[j];
      if(sum === 0){
        return true;
      }
    }
  }
  
  //Else return false
  return false;
}

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

Output:
true
false

Time complexity: O(n ^ 2).

Space complexity: O(1).

Time and Space complexity

• We traversing twice with inner loop, so Time complexity is O(n^2).
• We are using constant space, so Space complexity is O(1).

---

Using Set.

Implementation

• We will be using Set to store the sum and check if there is sum with 0 or not.
• If there is sum with 0 then return true else return false.

let subWithZero = (arr) => {
 //create a new set
 let set = new Set();

 //add 0 to handle the case when first  element in array is 0 
 set.add(0);
 
  //To calculate the sum
  let sum = 0;

  //loop through the array
  for(let i = 0; i < arr.length; i++){

    //calculate the sum of the subarrays
    sum += arr[i];
    
    //if sum is already there, then subarray with 0 is found
    if(set.has(sum)){
       return true;
    }
    
    //Add sum to the set
    set.add(sum);
  }
  
  //Return false by default
  return false;
}

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

Output:
true
false

Time complexity: O(n).

Space complexity: O(n).

Time and Space complexity

• We are iterating through the given array only once, so Time complexity is O(n).
• We are using Set to store the subarrays, so Space complexity is O(n).