15. Print all sub-arrays without zero sum

15. Print all sub-arrays without zero sum

Problem link :- click here

package program;

import java.util.ArrayList;
import java.util.HashMap;

class Pair
{
	int first_index;
	int second_index;
	
	Pair(int a, int b)
	{
		this.first_index = a;
		this.second_index = b;
	}
}

public class Searching__15
{

	/*
	 	You are given an array arr[] of size n. Find the total count of sub-arrays having 
	 	their sum equal to 0.
	 			arr[] = {0, 0, 5, 5, 0, 0}
	 			output : 6
	 	
	 	REPEATED PROBLEM
	 */
	
	static ArrayList<Pair> zeroSubArrays(int arr[], int n)
	{
		//This is our output
		ArrayList<Pair> result = new ArrayList<>();
		
		//HashMap holds sum and the sub array whose sum is zero
		HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
		
		int sum = 0;
		for(int i=0; i<n; i++)
		{
			sum += arr[i];
			
			if(sum == 0)
				result.add( new Pair(0, 1) );
			
			//ArrayList of sub-array
			ArrayList<Integer> sub_array = new ArrayList<>();
			if( map.containsKey(sum) )
			{
				sub_array = map.get(sum);
				for(int j=0; j<sub_array.size(); j++)
					result.add( new Pair(sub_array.get(j) +1, i)   );
			}
			
			sub_array.add(i);
			map.put(sum, sub_array);
		}
		return result;
	}
	
	static void print(ArrayList<Pair> result)
	{
		for(int i=0; i<result.size(); i++)
		{
			Pair p = result.get(i);
			System.out.print("SubArray found from index " + p.first_index);
			System.out.println(" to " + p.second_index);
		}
	}
	
	public static void main(String[] args)
	{
		int arr[] = {0, 0, 5, 5, 0, 0};
		
		ArrayList<Pair> ans = zeroSubArrays(arr, arr.length);
		
		if(ans.size() == 0)
			System.out.println("No such sub-arrays ");
		else
			print(ans);
	}

}

Time complexity :- O(n)
Space complexity :- O(1)