Friday, September 4, 2015

List all zero sum sub arrays in the given array containing zero/positive/negative numbers

Problem:

Given an array containing negative/zero/positive elements.
Now list all the start and end positions of the sub arrays, whose sum is equal to zero.

For eg:
{2, -1, 0, 1, 1, -1, -2}

Output:
start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6

Algorithm:

maintain HashMap with key as current sum and value as a list of index positions
3 cases possible for every element:
1. current element is zero: output is: start=currentPosition, end=currentPosition
2. current sum is zero: output is: start=0, end=currentPosition
3. current sum is already present in the hashMap, which means that the sub array formed by positions "hashMap.get(currentSum)+1" and "currentPosition" sum is zero. so print all such possibilities with hashMap values

If the sum is not present in the hashMap, then insert (sum, {currentPosition})
if the sum is already present, then insert (sum, {previously inserted positions, currentPosition})

Program:

import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;

class PrintPositions {
static public void printPos(int[] in) {
Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();

int sum = 0;

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

if(in[i] == 0)
System.out.println("start=" + i + ", end=" + i);
else if(sum == 0)
System.out.println("start=0, end=" + i);
else {
if(map.containsKey(sum)) {
List<Integer> positions = map.get(sum);

for(int pos : positions)
System.out.println("start=" + (pos+1) + ", end=" + i);
}
}

if(map.get(sum) == null) {
List<Integer> list = new ArrayList<Integer>();
list.add(i);
map.put(sum, list);
} else {
List<Integer> list = map.get(sum);
list.add(i);
}
}
}

static public void main(String[] args) {
PrintPositions pp = new PrintPositions();

pp.printPos(new int[]{2, -1, 0, 1, 1, -1, -2});
}
}

output:

start=2, end=2
start=1, end=3
start=1, end=5
start=4, end=5
start=0, end=6
start=1, end=7
start=4, end=7
start=6, end=7

No comments:

Post a Comment