Longest Subarray Zero Sum
Given an array arr of length N consisting of positive and negative integers, return the length of the longest subarray whose sum is zero.

Input Format:

The first line of input contains an integer N, the length of the array. The second line of input contains N integers, the elements of the array.

Output Format:

The single line contains an integer, the length of the longest subarray whose sum is zero.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

0

Question

Longest Subarray Zero Sum

Given an array arr of length N consisting of positive and negative integers, return the length of the longest subarray whose sum is zero.

Input Format:

The first line of input contains an integer N, the length of the array.

The second line of input contains N integers, the elements of the array.

Output Format:

The single line contains an integer, the length of the longest subarray whose sum is zero.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

0 <= N <= 10^6    
-10^9 <= arr[i] <= 10^9

Time Limit: 1sec

Accepted Answer

Brute Force

The brute force approach will be to calculate the sum for all possible subarrays. To calculate this, for each element(ith, where 0 <= i < N) in the array fix it as the first end of the subarray, initialize the subarray sum with zero, and iterate on the remaining elements(jth, where i <= j < N) of the array, keep adding the current element to the subarray sum and fix it as the second end of the array. If the sum becomes equals to zero then update the largest length.

Space Complexity: O(1)Explanation:

O(1)

In the worst case, only constant extra space is required.

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number of integers in the array.

In the worst case, we will be checking for all possible subarrays. As there will be N^2 number of subarrays possible for a given array of length N. So the time complexity will be of the order of N^2.

Accepted Answer

Using HashMap

In this approach, we will use a hashmap to store the prefix sums as keys and the value as the lowest index till which the prefix sum occurred. If any prefix sum occurs again in the array(let’s say i is the first index and j is the new index at which the prefix sum occurred again) this means that the sum of elements from (i + 1)th to jth index equals to zero and we will update the largest length.

Note: we will only keep the first index(lowest index) of a prefix sum as we need to find the largest length.

Space Complexity: O(n)Explanation:

O(N), where N is the number of integers in the array.

In the worst case, we can store the prefix sum for all indexes in the map.

Time Complexity: O(n)Explanation:

O(N), where N is the number of integers in the array.

In the worst case, we will be iterating on each element only once.

Given an array arr of length N consisting of positive and negative integers, return the length of the longest subarray whose sum is zero.

Input Format:

Output Format:

Note:

Constraints:

Top NatWest Group Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern