Find the largest continuous sequence in an array which sums to zero.

Example:
Input: { 1 , 3 , -1 , 2 , -4 , 1} Output: {3 , -1 , 2 ,-4}

NOTE : If there are multiple correct answers, return the sequence which occurs first in the array.

Solution

There are multiple solutions to the problem.

Solution 1 : Brute Force

A simple solution is to explore all the possible Sub Array and find out sum of it. We can run two nested loops, Outer loops i will be the starting point of the array and inner loop j will be the endpoint of the subarray.

Time Complexity: O(n2)

Space Complexity: O(1)

Solution 2 : Hashing with Prefix Sum

With Prefix sum of the array, we can get linear time complexity. Prefix sum at ith node is sum of all elements from 0 to i.

Prefix Sum for an array { 1 , 3 , -1 , 2 , -4 , 1} is { 1 , 4 , 3 , 5 , 1 , 2}. If sub-array having sum is 0 means we should get two elements having the same prefix sum. For example in the above prefix sum at index 0 sum is 1 and at index 4 sum is 1, which indicates sub-array starting from index 1 to 4 having sum is 0.

We can use HashSet to do a fast lookup for the prefix sum.

Time Complexity: O(n)

Space Complexity: O(n)

Code

Output

[1, 2, -3]

We acknowledge you to write a comment if you have a better solution or having any doubt on the above topic.

Leave a Reply

Your email address will not be published. Required fields are marked *