"Subarray with 0 sum" Problem

There are some programming problems that need some kind of previous exposure to the related concept but then comes problems like this one that can be solved by our mere intelligence. The only thing you gotta do is to put your brain to work.

Just understand the problem, then try to solve the test cases yourself and cogitate the process you are doing mentally to find the solution. [ Subarray is a contiguous part of array ]

Problem Statement:-

Given an array of integers. Find if there is a subarray (of size at-least one) with 0 sum. You just need to return true/false depending upon whether there is a subarray present with 0-sum or not. Printing will be taken care by the driver code.

Example 1:

Input:
n = 5
arr = {4,2,-3,1,6}
Output: 
Yes
Explanation: 
2, -3, 1 is the subarray with sum 0.

Example 2:

Input:
n = 5
arr = {4,2,0,1,6}
Output: 
Yes
Explanation: 
0 is one of the element in the array so there exist a subarray with sum 0.

Your Task:
You only need to complete the function subArrayExists() that takes array and n as parameters and returns true or false.

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).

Constraints:
1 <= n <= 104
-105 <= a[i] <= 105

LOGIC EXPLANATION:-

Well, firstly the O(n^2) approach comes to mind in which we'll start from every number and then keep summing to see if we get summation 0. 

Considering [2,3,1,-4]:

Like, we try following cases:- 

a) 2, 2+3,  2+3+1, then 2+3+1-4, we didn't get 0 in either

b) 3,  3+1, 3+1-4 =0 ( got it! )

But the issue is that this approach( O(n^2) time complexity ) is tedious, and we don't want that, neither do the people who made this problem( reason being this approach is easy to come up with )

Final Solution:

1) We keep summing the integers and keep a record of what summation was there at each step

2) If we get a summation that was previously seen, then that means we got a "Subarray with 0 Sum"

Example [2,3,1,-4]:

a) We have Sum=0

b) Add 2, Sum=2

c) Add 3, Sum=5

d) Add 1, Sum=6

e) Add -4, Sum=2 ( we got a summation that had previously occurred, 2 )

With some contemplation you'll understand that when we got to -4 we just subtracted the contribution of 3 and 1 in the summation 6 till that point. This will always give us the correct output on whether we have a Subarray with 0 Sum or not.

If you got the idea by yourself, then it's great, but if you couldn't, then

Code Implementation:- 

( Remember Coding part is just like drawing a picture, but before that you need to know what you are drawing )

class Solution:

   

    #Function to check whether there is a subarray present with 0-sum or not.

    def subArrayExists(self,arr,n):

        currSum=0

        sums=set()

        for i in range(n):

            currSum+=arr[i]

           

            if(currSum==0 or currSum in sums):

                return True

               

            sums.add(currSum)

       

        return False