Difficulty: Medium, Asked-in: Microsoft, Amazon
Key takeaway: An excellent problem to learn problem-solving using a hash table.
Given an array X[] of n integers, write a program to find the length of longest subarray with sum equal to 0. In general, for all j > i, find max (j - i + 1) among all subarray with zero-sum. Note: Length of subarray starting from index i and ending at index j = j - i + 1.
Example 1
Input: X[] = [14, -1, 1, -6, 1, 5, 12, 17], Output: 5
Explanation: The longest sub-array with elements summing up to 0 is [-1, 1, -6, 1, 5].
Example 2
Input: X[] = [1, 5, 10], Output: 0
Explanation: There is no subarray with 0 sum.
Example 3
Input: X[] = [1, 0, 2], Output: 1
Explanation: The longest sub-array with elements summing up to 0 is [0]
A basic solution would be to explore all possible subarrays, calculate the sum of each subarray and track maximum length of subarray with zero-sum using a variable.
int largestSubarrayZeroSum(int X[], int n)
{
int maxLength = 0
for (int i = 0, i < n; i = i + 1)
{
for (int j = i; j < n; j = j + 1)
{
int subArraySum = 0
for (int k = i; k <= j; k = k + 1)
subArraySum = subArraySum + X[k]
if (subArraySum == 0)
{
if (maxLength < j - i + 1)
maxLength = j - i + 1
}
}
}
return maxLength
}
def largestSubarrayZeroSum(X):
maxLength = 0
for i in range(len(X)):
for j in range(i, len(X)):
subArraySum = 0
for k in range(i, j + 1):
subArraySum = subArraySum + X[k]
if subArraySum == 0:
maxLength = max(maxLength, j - i + 1)
return maxLength
We are running three nested loops. So, time complexity in the worst case = O(n³). Note: Explore the last part of this blog to understand the analysis of above three nested loops: analysis of loop in programming.
We are using constant extra space. Space complexity = O(1)
Now critical questions are: Can we further optimize the time complexity? Can we avoid the innermost loop from k = i to j to calculate subarray sum? Let's think! One idea is: If we know sub-array sum from i to j, we can easily calculate the sub-array sum from i to j + 1 in O(1). Subarray sum from i to j + 1 = Subarray sum from i to j + X[j + 1].
Here we run outer loop from i = 0 to n - 1 to pick the starting index i, and run inner loop from j = i to n - 1 to calculate the running sum of all sub-arrays starting from index i. Inside inner loop, if subarray sum is equal to zero, we calculate its length and update max subarray length found so far. This is an optimized version of the above approach, where we are running only two nested loops and exploring sub-array starting at all positions.
int largestSubarrayZeroSum(int X[], int n)
{
int maxLength = 0
for (int i = 0, i < n; i = i + 1)
{
int subArraySum = 0
for (int j = i; j < n; j = j + 1)
{
subArraySum = subArraySum + X[j]
if (subArraySum == 0)
maxLength = max(maxLength, j - i + 1)
}
}
return maxLength
}
def largestSubarrayZeroSum(X):
maxLength = 0
for i in range(len(X)):
subArraySum = 0
for j in range(i, len(X)):
subArraySum = subArraySum + X[j]
if subArraySum == 0:
maxLength = max(maxLength, j - i + 1)
return maxLength
We are running two nested loops to explore each subarray from (i, j), where i <= j. Total number of loop iteration = n + (n - 1) + .... + 2 + 1 = n(n + 1)/2 = O(n^2). At each iteration, we are doing O(1) operations. So time complexity = Total number of nested loops iteration * O(1) = O(n^2) * O(1).
We are using constant extra space. So space complexity = O(1)
Now critical questions are: Can we improve time complexity to O(n)? Can we solve this problem in using single loop? Let’s think! Suppose sum(j, i) is the sub-array sum from index j to i where j < i. Here we can identify two properties related to sum(j, i).
So there could be two possibilities for sub-array with zero sum:
Using the above hypothesis, we can solve the problem by traversing array linearly and storing the sum of all subarrays starting from the index 0 in the hash table (Think!).
If subArraySum is equal to zero, we have found case 1 of the above possibilities. So we update variable maxLength i.e. if (maxLength < i + 1), maxLength = i + 1.
subArraySum = subArraySum + X[i]
if (subArraySum == 0)
{
if (maxLength < i + 1)
maxLength = i + 1
}
Otherwise, we have already stored some previous index H[subArraySum] in the hash table with the same value of subArraySum. This is a case 2 where subarray sum from index 0 to current index i is equal to subarray sum from index 0 to index H[subArraySum]. In other words, we can say that the sum of subarray from index H[subArraySum] + 1 to index i is equal to zero. So we update the value of maximum length i.e. if(maxLength < i - H[subArraySum]), maxLength = i - H[subArraySum].
else if (H.search(subArraySum) == false)
H.insert(subArraySum) = i
else
{
if (maxLength < i - H[subArraySum])
maxLength = i - H[subArraySum]
}
int largestZeroSubarraySum(int X[], int n)
{
HashTable H
int subArraySum = 0
int maxLength = 0
for (int i = 0, i < n; i = i + 1)
{
subArraySum = subArraySum + X[i]
if (subArraySum == 0)
{
if (maxLength < i + 1)
maxLength = i + 1
}
else if (H.search(subArraySum) == false)
H.insert(subArraySum) = i
else
{
if (maxLength < i - H[subArraySum])
maxLength = i - H[subArraySum]
}
}
return maxLength
}
int largestZeroSubarraySum(int X[], int n)
{
unordered_map<int, int> H;
int subArraySum = 0;
int maxLength = 0;
for (int i = 0; i < n; i = i + 1)
{
subArraySum = subArraySum + X[i];
if (subArraySum == 0)
maxLength = max(maxLength, i + 1);
else if (H.find(subArraySum) == H.end())
H[subArraySum] = i;
else
maxLength = max(maxLength, i - H[subArraySum]);
}
return maxLength;
}
def largestZeroSubarraySum(X: List[int]) -> int:
H = defaultdict(int)
subArraySum = 0
maxLength = 0
for i, x in enumerate(X):
subArraySum = subArraySum + x
if subArraySum == 0:
maxLength = max(maxLength, i + 1)
elif subArraySum not in H:
H[subArraySum] = i
else:
maxLength = max(maxLength, i - H[subArraySum])
return maxLength
int largestZeroSubarraySum(int[] X)
{
HashMap<Integer, Integer> H = new HashMap<>();
int subArraySum = 0;
int maxLength = 0;
for (int i = 0; i < X.length; i = i + 1)
{
subArraySum = subArraySum + X[i];
if (subArraySum == 0)
maxLength = Math.max(maxLength, i + 1);
else if (!H.containsKey(subArraySum))
H.put(subArraySum, i);
else
maxLength = Math.max(maxLength, i - H.get(subArraySum));
}
return maxLength;
}
We are linearly traversing the array and performing one search or one insert operation at each step of the iteration. Time complexity of one insert/search operation = O(1) average. So overall time complexity = n*O(1) = O(n). Space complexity = O(n), for the hash table.
Enjoy learning,Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.