Given an array arr[] of length N, find the length of the longest sub-array with a sum equal to 0.
Input: arr[] = {15, -2, 2, -8, 1, 7, 10, 23}
Output: 5
Explanation: The longest sub-array with elements summing up to 0 is {-2, 2, -8, 1, 7}
Method1: Extreme Brute Force Method
In this, we consider all sub-arrays one by one and check the sum of every sub-array. If the sum of the current subarray is equal to zero then update the maximum length accordingly.
public class Brute {
public static void main(String[] args) {
int arr[] = { 15, -2, 2, -8, 1, 7, 10, 23 };
int N = arr.length;
// Function call
System.out.println("Length of the longest 0 sum "
+ "subarray is " + maxLen(arr, N));
}
private static int maxLen(int[] arr, int n) {
int max_Length =0;
for(int i =0;i<n;i++){
int curr_sum =0;
for(int j =i;j<n;j++){
curr_sum += arr[j];
// if sum equals to 0 then enter this if condition
if(curr_sum == 0){
// then compare the max length , here j-i+1 is the size of the window
// which gives 0 sum
max_Length = Math.max(max_Length, j-i+1);
}
}
}
return max_Length;
}
}
// Time Complexity: O(N2)
// Auxiliary Space: O(1)Method2: Using HashMap
In this, we create a variable (sum), length (max_len), and a hash map (hm) to store the sum-index pair as a key-value pair. Then start traversing the input array and for every index, then update the value of sum = sum + array[i]. Check every index, if the current sum is present in the hash map or not. If present, update the value of max_len to a maximum difference of two indices (current index and index in the hash-map) and max_len. Else, put the value (sum) in the hash map, with the index as a key-value pair. And finally, print the maximum length (max_len).
public class UsingHashMap {
public static void main(String[] args) {
int arr[] = { 15, -2, 2, -8, 1, 7, 10, 23 };
// Function call
System.out.println(
"Length of the longest 0 sum subarray is "
+ maxLen(arr));
}
private static int maxLen(int[] arr) {
// created a map
HashMap<Integer,Integer> map = new HashMap<>();
int sum =0;
int max_len =0;
for(int i =0;i<arr.length;i++){
sum += arr[i];
if(sum == 0) max_len = i +1;
// look this sum in hash table
Integer prev_i = map.get(sum); // if not present then will return null
// if sum is seen before , then update max_len if required
if(prev_i != null){
max_len = Math.max(max_len, i - prev_i);
}
else{
map.put(sum,i);
}
}
return max_len;
}
}
// Time Complexity: O(N)
// Auxiliary Space: O(N)