Longest Subarray with Zero Sum Editorial

Practice Problem Link: https://workat.tech/problem-solving/practice/longest-subarray-zero-sum

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement 

Given an array A, find the length of the longest subarray which has a sum equal to 0.

Naive Approach

The simple solution to this problem is to check all the subarrays and find the maximum subarray with a sum equal to zero.

• Initialize the maximum length as 0.
• Run two nested loops, the outer loop from i = 0 to i = n and the inner loop from j = i to j = n
• Calculate the sum for every i to j and if at any point the sum equals zero, update the maximum length.

Analysis

• Time Complexity: O(n2)
• Auxiliary Space Complexity: O(1)

Implementation

C++

int longestSubarrayWithZeroSum(vector<int> &A) {
    int n = A.size();
	int maxSubarray = 0;
	for (int i = 0; i < n; i++) {
		int sum = 0;
		for (int j = i; j < n; j++) {
			sum += A[j];
			if (sum == 0) {
				maxSubarray = max(maxSubarray, j - i + 1);
			}
		}
	}
	return maxSubarray;
}

Java

class Solution {
	int longestSubarrayWithZeroSum(int[] A) {
	    int n = A.length;
		int maxSubarray = 0;
		for (int i = 0; i < n; i++) {
			int sum = 0;
			for (int j = i; j < n; j++) {
				sum += A[j];
				if (sum == 0) {
					maxSubarray = Math.max(maxSubarray, j - i + 1);
				}
			}
		}
		return maxSubarray;
	}
}

Optimal Approach

Let's say sumi denotes the sum from 0 to i and sumj denotes the sum from 0 to j where (i < j).

If sumiis equal to sumj then the sum of all the elements from i + 1 to j must be 0.

This idea can be used to solve the problem efficiently just by hashing all the prefix sums encountered up to index i.

• Initialize maximum length as 0.
• Traverse the array and keep updating the sum for every i. Check if the sum is present in the hashmap or not.
• If the sum is not present in the hashmap then put the sum in the hash map with the index as key-value pair.
• If the sum is present in the hashmap, take the difference between the current index and the index stored in the hashmap and update the maximum length.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

int longestSubarrayWithZeroSum(vector<int> &A) {
    int n = A.size();
	int maxSubarray = 0;
	int sum = 0;
	unordered_map<int, int> prefixSum;
	prefixSum[0] = -1;
	for (int i = 0; i < n; i++) {
		sum += A[i];
		if (prefixSum[sum] == 0 && sum == A[0]) {    //Check the 0th index
			maxSubarray = max(maxSubarray, i);
		} else if (prefixSum[sum] != 0) {
			maxSubarray = max(maxSubarray, i - prefixSum[sum]);
		} else {
			prefixSum[sum] = i;
		}
	}
	return maxSubarray;
}

Java

class Solution {
	int longestSubarrayWithZeroSum(int[] A) {
	    int n = A.length;
		int maxSubarray = 0;
		int sum = 0;
		HashMap<Integer, Integer> prefixSum = new HashMap <Integer, Integer> ();
		prefixSum.put(0, -1);
		for (int i = 0; i < n; i++) {
			sum += A[i];
			Integer prevIndex = prefixSum.get(sum);
			if (prevIndex == null) {
				prefixSum.put(sum, i);
			} else {
				maxSubarray = Math.max(maxSubarray, i - prevIndex);
			}
		}
		return maxSubarray;
	}
}