Longest Subarray with Zero Sum

Problem Statement: Longest Subarray with Zero Sum

Given an array of integers, find the length of the longest sub-array with a sum that equals 0.

Example: arr[] = [15, -2, 2, -8, 1, 7, 10, 23]

Output: 5

Explanation: Explanation: The longest sub-array with elements sum to 0 is [-2, 2, -8, 1, 7]

Approach 1: Brute Force

A simple solution is to check for all subarrays one by one and see if its sum is equal to zero or not. For this, we generate all (i, j): i <= j pairs and calculate the sum between. Time complexity will be O(n³) i.e. not the optimal one so we need to optimise it.

Approach 2: Hash Table

The idea is to store the sum of all the subarrays starting from the beginning. From that, if any of the values repeat itself, let’s say sum till i index and sum till j index is same, it means that the sum of elements in the subarray A[i+1…..j] is 0. Moreover, if the sum any index i is 0, then the subarray A[0…i] has sum of its elements equal to 0.

Alogrithm

1. Create a hash table mapp and store sum and its ending index as key-value pairs.

2. Declare a variable maxlen = 0, which will store the maximum length of subarray whose sum is zero.

3. Iterate through the array and for every A[i], calculate the cummaltive sum from 0 to i. If sum turns out to be 0, then update maxLen to i, if (maxlen < i).

4. Check if that sum is present in the hash table or not. If present, then update the maxlen if ( i - mapp[sum] > maxlen ) to i - mapp[sum]. Else insert it in hashmap, mapp[sum] = i.

5. Return maxlen

int maxLen(int A[], int n)
{
    // Your code here
    unordered_map<int,int> mpp; 
    int maxi = 0;
    int sum = 0; 
    for(int i = 0;i<n;i++) {
        sum += A[i]; 
        if(sum == 0) {
            maxi = i + 1; 
        }
        else {
            if(mpp.find(sum) != mpp.end()) {
                maxi = max(maxi, i - mpp[sum]); 
            }
            else {
                mpp[sum] = i;
            }
        }   
    }

    return maxi; 
}

def max_subarray(arr):
	
	# NOTE: Dictonary in python in implemented as Hash Maps
	# Create an empty hash map (dictionary)
	mapp = {}

	# Initialize result
	max_len = 0

	# Initialize sum of elements
	curr_sum = 0

	# Traverse through the given array
	for i in range(len(arr)):
		
		# Add the current element to the sum
		curr_sum += arr[i]

		if arr[i] is 0 and max_len is 0:
			max_len = 1

		if curr_sum is 0:
			max_len = i + 1

		# NOTE: 'in' operation in dictionary to search
		# key takes O(1). Look if current sum is seen
		# before
		if curr_sum in mapp:
			max_len = max(max_len, i - mapp[curr_sum] )
		else:

			# else put this sum in dictionary
			mapp[curr_sum] = i

	return max_len


# test array
arr = [15, -2, 2, 8, 1, 7, 10, 13]

print("Length of the longest 0 sum subarray is % d" % max_subarray(arr))

Time Complexity: O(n)

Auxiliary Space: O(n), Since we are using hashmap for storing