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

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.