Popular Posts

Thursday, July 28, 2011

Contiguous subarray with sum zero

Given an array with + and - numbers, including zero, Write an algorithm to find all the possible sub arrays which sum up to zero.
For example, if given array is
20 , -9 , 3 , 1, 5 , 0, -6 , 9
Then possible sub arrays are:
-9, 3, 1, 5
0
1, 5, 0, -6
Solution: 
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class ZeroSumContiguousSubArray {

public static void main(String[] args) {
int[] a = {20 , -9 , 3 , 1, 5 , 0, -6 , 9};
System.out.println("actual array elements are :");
printArray(a,0,a.length-1);
getSubArraysWithZeroSum(a);
}

private static void getSubArraysWithZeroSum(int[] a) {

if(a==null || a.length==0) return;


//construct a temporary array with sums
int[] temp = new int[a.length+1];
//add '0' as first element in the temporary array to simplify the code and cover edge conditions.
temp[0] = 0;
temp[1]=a[0];
for(int i=2;i<temp.length;i++){
temp[i]=temp[i-1]+a[i-1];
}

//construct a hash map with sum as keys and list of positions as values;
Map<Integer,List<Integer>> map = new HashMap<Integer, List<Integer>>();

for(int i=0;i<temp.length;i++){
if(map.get(temp[i])==null){
List list = new ArrayList<Integer>();
list.add(i);
map.put(temp[i], list);
}else{
List list = map.get(temp[i]);
list.add(i);
map.put(temp[i], list);
}
}
//Retrieve the lists from map and check if list size is greater than one.
//if the list size greater than one,get combinations and call print methods
for(List<Integer> list : map.values()){
if(list.size()>1){
getCombinations(a,list);
}
}
}

private static void getCombinations(int[] a, List<Integer> list) {
//select two elements from the list and call print method with element positions as starting and ending
for(int i=1;i<list.size();i++){//here we can modify the code to select any two elements instead of side by side elements so that it prints all combinations
printArray(a, list.get(i-1), list.get(i)-1);
}
}

private static void printArray(int[] a,int start,int end) {
System.out.println();
for(int i=start;i<=end;i++){
System.out.print(" "+a[i]);
}
System.out.println();
}
}

No comments:

Post a Comment