Sunday, 28 June 2020

Print all subarrays with 0 sum


Given an array, print all subarrays in the array which has sum 0.

Examples:

Input:  arr = [6, 3, -1, -3, 4, -2, 2,4, 6, -12, -7]
Output:  
Subarray found from Index 2 to 4
Subarray found from Index 2 to 6          
Subarray found from Index 5 to 6
Subarray found from Index 6 to 9
Subarray found from Index 0 to 10


package org.ms.ds.hashing;

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

public class PrintAllSubarraysWithZerSum {
public static void main(String[] args) {
PrintAllSubarraysWithZerSum print = new PrintAllSubarraysWithZerSum();
Integer[] elements = {3, 4, -7, 3, 1, 3, 1, -4, -2, -2};
// prefix sum {3, 7, 0, 3, 4, 7, 8, 4, 2, 0}
print.printZeroSumSubarray(elements);
}

void printZeroSumSubarray(Integer[] elements) {
// here in 2 condition subarray will be zero
//1. if sum is zero
//2. if if any key(sum) repeates (x(1st occurance), ....,x(2nd occurance)) => index of x+1 to x subarray will have sun as zero
Map<Integer, List<Integer>> map = new HashMap<>();
int sum = 0;
insert(map,0,-1); //
for (int i = 0; i < elements.length;i++) {
sum=sum+elements[i];
if(map.containsKey(sum)){
List<Integer> list=map.get(sum);
for(Integer value:list){
System.out.println("key(" +sum+") index : "+ (value+1) +" to "+ i);
}
}
insert(map,sum,i);
}
}

void insert(Map<Integer, List<Integer>> map, Integer sum, Integer ele) {
if (!map.containsKey(sum)) {
map.put(sum, new ArrayList<Integer>());
}
map.get(sum).add(ele);
}

}

No comments:

Post a Comment