Longest Subarray with Zero Sum

Ninja enjoys working with numbers, and as a birthday challenge, his friend provides him with an array consisting of both positive and negative integers. Ninja is curious to identify the length of the longest subarray within this array that sums to zero.

Input:

The first line contains a single integer T, representing the number of test cases. The first line of each test case consists of the integer N, which represents the number of elements in the array. The second line of each test case contains N space-separated integers representing the array's elements.

Output:

A single line for each test case, indicating the integer value of the length of the longest subarray with a sum of zero.

Example:

If T = 2, and the arrays are arr1 = [1, -1, 3, 2, -2, -3, 3] and arr2 = [1, 2, -3, 3, -2, -1, 2], the outputs should be 4 and 5 respectively.

Constraints:

1

Question

Longest Subarray with Zero Sum

Ninja enjoys working with numbers, and as a birthday challenge, his friend provides him with an array consisting of both positive and negative integers. Ninja is curious to identify the length of the longest subarray within this array that sums to zero.

Input:

The first line contains a single integer T, representing the number of test cases.
The first line of each test case consists of the integer N, which represents the number of elements in the array.
The second line of each test case contains N space-separated integers representing the array's elements.

Output:

A single line for each test case, indicating the integer value of the length of the longest subarray with a sum of zero.

Example:

If T = 2, and the arrays are arr1 = [1, -1, 3, 2, -2, -3, 3] and arr2 = [1, 2, -3, 3, -2, -1, 2], the outputs should be 4 and 5 respectively.

Constraints:

1 <= T <= 10
1 <= N <= 10^4
-10^5 <= arr[i] <= 10^5
Time Limit: 1 sec

Accepted Answer

Find the length of the longest subarray with zero sum in an array of integers.

Iterate through the array and keep track of the running sum using a hashmap.
If the running sum is seen before, the subarray between the current index and the previous index with the same sum is a subarray with zero sum.
Update the length of the longest subarray with zero sum as you iterate through the array.
Example: For arr1 = [1, -1, 3, 2, -2, -3, 3], the longest subarray with zero sum is [3, 2, -2, -3].

Accepted Answer

I solved this problem using hashmaps because of their O(1) search operation. I applied 2 nested loops and then used the hashmap to search for the third element to make the sum zero. Time Complexity of this approach - O(n^2)

Another approach that uses sorting also took O(n^2) time.

Asked in Bharti Airtel