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 returnfalse
.
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 returnfalse
.
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).