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 integer elements, write a program to find the length of the longest subarray with a sum equal to 0. In general, for all j > i, find max (j - i + 1) among all subarray with zero-sum. Note: the length of a 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]
Solution idea and steps
A basic solution would be to explore all possible subarrays, calculate the sum of each subarray and track the maximum length of the subarray with zero-sum using a variable.
Solution pseudocode
int largestSubarrayZeroSum(int X[], int n)
{
int maxZeroSubarray = 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 (maxZeroSubarray < j - i + 1)
maxZeroSubarray = j - i + 1
}
}
}
return maxZeroSubarray
}
Solution Analysis
Solution idea
Now the critical question is: can we further optimize the time complexity of the above approach? Can we avoid the inner loop from k = i to j for calculating the subarray sum? Let's think!
The idea is: if we know the sub-array sum from i to j, we can easily find 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]. Think!
Solution pseudocode
int largestSubarrayZeroSum(int X[], int n)
{
int maxZeroSubarray = 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[i]
if (subarraySum == 0)
maxZeroSubarray = max(maxZeroSubarray, j - i + 1)
}
}
return maxZeroSubarray
}
Solution analysis
Solution idea
The critical question is: can we improve the time complexity to O(n)? Can we solve this problem in a single loop by using some insights from the problem? Let’s think!
Suppose sum(i, j) is the sub-array sum from the index i to j where i < j. Here we can identify two properties related to sum(i, j).
So there could be two possibilities for the sub-array with zero sum:
Using the above hypothesis, we can solve the problem by traversing the array linearly and storing the sum of all the subarrays starting from the index 0 (Think!). Here is a step by step description :
We calculate the sub-array sum starting from the index 0. If we find the value of the sum equal to zero, then we update the variable maxLength.
if (sum == 0)
{
if (maxLength < i + 1)
maxLength = i + 1
}
Otherwise, if the sum value is already present in the hash table, let’s say sum till index i and sum till index j arethe same, it means that the sum of the subarray X[i + 1 ... j] is 0. In such a scenario, we update the value of the maximum length.
else if(H.search(sum) == true)
{
if(maxLength < i - H[sum])
maxLength = i - H[sum]
}
Solution Pseudocode
int largestZeroSubarray(int X[], int n)
{
HashTable H
int sum = 0
int maxLength = 0
for (int i = 0, i < n; i = i + 1)
{
sum = sum + X[i]
if (sum == 0)
{
if (maxLength < i + 1)
maxLength = i + 1
}
else if(H.search(sum))
{
if(maxLength < i - H[sum])
maxLength = i - H[sum]
}
else
H.insert(sum) = i
}
return maxLength
}
Solution Analysis
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!
The least frequently used (LFU) is a cache algorithm used to manage memory within a computer. In this method, the system keeps track of the number of times a block is referenced in memory, and when the cache is full, our system removes the item with the lowest reference frequency.
Given a binary tree, write a program to find its height. The height or depth of a binary tree is equal to the count of nodes on the longest path from the root to the leaf, i.e., the max number of nodes from the root to the most distant leaf. This is an excellent problem to learn problem-solving using DFS and BFS traversal.
Hashing is a technique to map (key, value) pairs into the hash table using a hash function. It uses an array of size proportional to the number of keys and calculates an array index from the key using a hash function. Explore this blog to learn how hash tables work in programming?
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.