subarry with sum of 0

Q: An array contain positive and negative elements, find maximum subarray whose sum is equal to zero.

Algorithm:

Lets take input array as a[]={-3,2,4,-6,-8,10,11}

Make an array b [] such that b[i]=b[i-1]+a[i]; means b[i] = sum(a[0],…, a[i]);

So b[]={-3,-1,3,-3,-11,-1,10}

Now all those pairs at indexes (i,j)in array b[] having equal numbers are the indexes of subarrays from (i+1,j) having sum as zero.

we have to find some (i, j) so: a[i] + a[i+1] + … + a[j] = 0. But a[i] + a[i+1] + … + a[j] = b[j] – b[i-1].
when creating the map using b values, the key in map is the value from b and the value in map is the index of from b. if a new key exists, this means we found a solution.

Finding all pairs in O(n) can be done by using map.

Working JAVA Code
---------------------------
import java.util.Comparator;
public class Index implements Comparable{
Integer start;
Integer end;
public Integer getStart() {
return start;
}
public void setStart(Integer start) {
this.start = start;
}
public Integer getEnd() {
return end;
}
public void setEnd(Integer end) {
this.end = end;
}
public int compareTo(Object index1) {
index1 = (Index) index1;
Index index2 = (Index) this;
Integer index1Distance = ((Index) index1).getEnd().intValue() - ((Index) index1).getStart().intValue();
Integer index2Distance = ((Index) index2).getEnd().intValue() - ((Index) index2).getStart().intValue();
if (index1Distance > index2Distance)
return 1;
else if (index1Distance == index2Distance)
return 0;
else
return -1;
}
}

import java.util.HashMap;
import java.util.Map;
public class SubarraywithSumZero {
public Index findLongestSubArraywithSumZero(long[] inputArray) {
// 1. Generate a cummulative array
for (int i=1; i < inputArray.length; i++) {
inputArray[i] += inputArray[ (i-1)];
}
//2. Read the array, store it in map
// For a subraary with 0 there should + and - numbers
// we need to figure the longest distance indexes which have same numbers
// since our array is cummulative postives and negatives which sum to 0 will bring the
// intermittent array back to same number where it started
// eg intermittent array = -6, -8, -10, -6, -4, 1, 2, 3, 4, 1
// now from -6 we again reach -6
// and later from 1 back to 1 which implies these two arrays are summing to 0
// we just need the longest one
Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
Index maxIndex = null;
for (int i=0; i < inputArray.length; i++) {
Integer index = new Integer(i);
Integer val = new Integer((int) inputArray[i]);
if (indexMap.get(val) == null) {
indexMap.put(val, index);
}
else {
if (maxIndex == null) {
maxIndex = new Index();
//collosion found the subarray
maxIndex.setStart(indexMap.get(val));
maxIndex.setEnd(new Integer(i));
}
else {
Index index1 = new Index();
index1.setStart(indexMap.get(val));
index1.setEnd(new Integer(i));
if (maxIndex.compareTo(index1) <= 0) {
maxIndex = index1;
}
}
}
}
return maxIndex;
}
public static void main(String[] args) {
long inputArray[] = {3,2,4,-6,-8,10,11};
SubarraywithSumZero subarraywithSumZero = new SubarraywithSumZero();
Index maxIndex = subarraywithSumZero.findLongestSubArraywithSumZero(inputArray);
System.out.println("Longgest Subarray with sum starts at [" + maxIndex.getStart() + " ] and ends at [" + maxIndex.getEnd() + "]");
}
}

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s