# Question 2: Check if Subarray with Zero Sum Exists

Question 2

You are given an integer array. You need to check if the array contains sub-array with zero sum.

For example:

Input: A = {4, -1, -3, 1}

Output: Subarray with zero sum exists

{4, -1, -3}

#### Solution 1: Inefficient Solution – Quadratic Time – O(n2)

In this solution we take running sum of all each element with every other element, and each time we check if the sum is equal to zero. If yes then we return true.

The Java code is given below:

```/*
* Written by: Kindson The Genius
*/
public class ZeroSumSubarray1 {

public static boolean zeroSumSubarray(int A[]) {
int sum;

for(int i = 0; i < A.length; i++) {
sum = 0;

for(int j = i; j < A.length; j++) {
sum = sum + A[j];
if(sum == 0) {
System.out.println("Subarray exists");
return true;
}
}//end of for loop
}//end of for loop

System.out.println("Subarray does not exist");
return false;
}//end of zeroSumSubarray

public static void main(String[] args) {
int ar[] = {4, -1, -3, 1};
zeroSumSubarray(ar);
}
}
```

#### Solution 2: Using a Hash Table – Linear Time O(n)

In this solution, start from the first element and take running sum. Then for each element, we store the sum so far in a hash table. Before we store an element, we check the hash tableĀ  to see if the sum already exists (ie if it has been seen before). If yes, then we know hat there isĀ  a sub-array with zero sum that ends at the current index.

The Java program is given below:

```/*
* Written by Kindson the Genius
* Check is Subarry with zero sum exists
*/

import java.util.HashSet;
import java.util.Set;

public class ZeroSumSubarray2 {

public static Boolean ZeroSumSubarray(int A[]) {
Set<Integer> set = new HashSet<Integer>();

int sum = 0;

for(int i = 0; i<A.length; i++) {
sum = sum + A[i];

if(set.contains(sum)) {
return true;
}

}//end of for loop

return false;
}//end of function

public static void main(String[] args) {

int ar[]  = {1, -4, 3, 4};

System.out.println(ZeroSumSubarray(ar));
}
}
```