Question 2: Check if Subarray with Zero Sum Exists

Check for subarray with zero sum

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;
		
		set.add(sum);
		
		for(int i = 0; i<A.length; i++) {
			sum = sum + A[i];
			
			if(set.contains(sum)) {
				return true;
			}
			
			set.add(sum);
			
		}//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));
	}
}