Given an array of positive and negative numbers. Find if there is a subarray (of size at-least one) with 0 sum.
Example 1:
Input:
5
4 2 -3 1 6
Output: 
Yes
Explanation: 
2, -3, 1 is the subarray 
with sum 0.
Example 2:
Input:
5
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 depending upon whether there is a subarray present with 0-sum or not. Printing will be taken care by the drivers code.
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).
Constraints:
1 <= n <= 10^{4}
-10^{5} <= a[i] <= 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Amortized analysis

Starter code: #User function Template for python3

class Solution:
    
    #Function to check whether there is a subarray present with 0-sum or not.
    def subArrayExists(self,arr,n):
        ##Your code here
        #Return true or false

Solutions:
class Solution:

	def subArrayExists(self, arr, n):
		n_sum = 0
		s = set()
		for i in range(len(arr)):
			n_sum += arr[i]
			if n_sum == 0 or n_sum in s:
				return True
			s.add(n_sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		curr_sum = 0
		d = {}
		for i in range(n):
			curr_sum = curr_sum + arr[i]
			if curr_sum == 0 or curr_sum in d:
				return True
			d[curr_sum] = i
		return False


class Solution:

	def subArrayExists(self, arr, n):
		st = set()
		st.add(0)
		sum = 0
		for i in range(n):
			sum += arr[i]
			if sum in st:
				return True
			st.add(sum)
		if sum != 0:
			return False
		return True


class Solution:

	def subArrayExists(self, arr, n):
		sumhashmap = {0: 1}
		localsum = 0
		for val in arr:
			if val == 0:
				return True
			localsum += val
			if localsum in sumhashmap:
				return True
			else:
				sumhashmap[localsum] = 1
		return False


class Solution:

	def subArrayExists(self, arr, n):
		hm = {}
		if sum(arr) == 0:
			return True
		curr_sum = 0
		for i in range(n):
			curr_sum += arr[i]
			if curr_sum == 0:
				return True
			if curr_sum in hm:
				return True
			else:
				hm[curr_sum] = i
		return False


class Solution:

	def subArrayExists(self, arr, n):
		s = 0
		a = 0
		x = 0
		d = {}
		for i in range(n):
			s = s + arr[i]
			if s == 0:
				x = x + 1
				break
			if s not in d:
				d[s] = i
			else:
				x = x + 1
				break
		if x == 0:
			return False
		else:
			return True


class Solution:

	def subArrayExists(self, arr, n):
		d = {}
		s = 0
		for i in arr:
			s += i
			if s == 0 or i == 0 or s in d:
				return True
			else:
				d[s] = 1
		return False


class Solution:

	def subArrayExists(self, arr, n):
		dici = {}
		sumi = 0
		for i in range(n):
			sumi += arr[i]
			if sumi in dici or sumi == 0:
				return True
			dici[sumi] = 1
		return False


class Solution:

	def subArrayExists(self, arr, n):
		ns = 0
		s = set()
		for i in range(n):
			ns += arr[i]
			if ns == 0 or ns in s:
				return 1
			s.add(ns)
		return 0


class Solution:

	def subArrayExists(self, arr, n):
		prefix_sum = [0] * (n + 1)
		for i in range(1, n + 1):
			prefix_sum[i] = prefix_sum[i - 1] + arr[i - 1]
		hmap = {}
		for i in prefix_sum:
			if i not in hmap:
				hmap[i] = 1
			else:
				return True
		return False


class Solution:

	def subArrayExists(self, arr, n):
		sum = 0
		s = set()
		d = True
		f = False
		for i in range(n):
			sum = sum + arr[i]
			if sum == 0 or sum in s:
				return d
			s.add(sum)
		return f
		if d:
			return 'Yes'
		else:
			return 'No'


class Solution:

	def subArrayExists(self, arr, n):
		hash = set()
		for i in range(n):
			if i == 0:
				if arr[i] == 0:
					return True
			else:
				arr[i] += arr[i - 1]
				if arr[i] in hash or arr[i] == 0:
					return True
			hash.add(arr[i])
		return False


class Solution:

	def subArrayExists(self, arr, n):
		seen_sums = set()
		running_sum = 0
		for num in arr:
			running_sum += num
			if running_sum == 0 or running_sum in seen_sums:
				return True
			seen_sums.add(running_sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		h = {}
		res = 0
		for i in range(n):
			res += arr[i]
			if res == 0:
				return 1
			if res in h:
				return 1
			h[res] = 1
		return 0


class Solution:

	def subArrayExists(self, arr, n):
		sum = 0
		s = set()
		for each in arr:
			sum += each
			if sum in s or sum == 0:
				return True
			s.add(sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		pref_sum = {0: 1}
		curr_sum = 0
		for elem in arr:
			curr_sum += elem
			if curr_sum in pref_sum:
				return True
			else:
				pref_sum[curr_sum] = 1
		return False


class Solution:

	def subArrayExists(self, arr, n):
		sum = 0
		s = set()
		for i in range(n):
			sum = sum + arr[i]
			if sum == 0 or sum in s:
				return True
			else:
				s.add(sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		addSum = 0
		maxLen = 0
		d = {}
		for i in range(len(arr)):
			addSum += arr[i]
			if addSum == 0:
				maxLen = i + 1
			elif addSum in d:
				maxLen = max(maxLen, i - d[addSum])
			else:
				d[addSum] = i
		if maxLen >= 1:
			return True
		else:
			return False


class Solution:

	def subArrayExists(self, arr, n):
		sm = 0
		dic = {0}
		for el in arr:
			if el == 0:
				return True
			sm += el
			if sm in dic:
				return True
			dic.add(sm)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		prefix_sum_set = set()
		prefix_sum = 0
		for i in range(n):
			prefix_sum += arr[i]
			if prefix_sum == 0 or prefix_sum in prefix_sum_set:
				return True
			prefix_sum_set.add(prefix_sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		d = {0: 1}
		sumVal = 0
		for i in arr:
			sumVal += i
			if sumVal in d:
				return 1
			d[sumVal] = 1
		return 0


class Solution:

	def subArrayExists(self, arr, n):
		dic = {0: 0}
		s = 0
		for i in arr:
			s += i
			try:
				dic[s] += 1
				return True
			except:
				dic[s] = 0
		return False


class Solution:

	def subArrayExists(self, arr, n):
		prefixSum = {}
		sum = 0
		for i in range(n):
			sum += arr[i]
			if sum == 0 or sum in prefixSum:
				return True
			prefixSum[sum] = i
		return False


class Solution:

	def subArrayExists(self, arr, n):
		sum = 0
		d = {}
		for i in arr:
			sum += i
			if sum in d:
				return True
			if sum == 0:
				return True
			d[sum] = 1
		return False


class Solution:

	def subArrayExists(self, arr, n):
		pre_sum = 0
		s = set()
		for i in arr:
			pre_sum += i
			if pre_sum == 0 or pre_sum in s:
				return True
			s.add(pre_sum)
		return False


from collections import *

class Solution:

	def subArrayExists(self, arr, n):
		d = defaultdict(int)
		d[0] = 1
		sumsofar = 0
		count = 0
		for i in range(n):
			sumsofar += arr[i]
			count += d[sumsofar]
			d[sumsofar] = 1
		if count >= 1:
			return True
		else:
			return False


class Solution:

	def subArrayExists(self, arr, n):
		m = {}
		sum = 0
		for i in range(n):
			sum += arr[i]
			if sum in m or sum == 0:
				return 1
			else:
				m[sum] = 1
		return 0


class Solution:

	def subArrayExists(self, arr, n):
		d = {0: -1}
		cumulative = 0
		for i in range(n):
			cumulative += arr[i]
			if cumulative in d:
				return True
			else:
				d[cumulative] = i
		return False


from collections import *

class Solution:

	def subArrayExists(self, nums, n):
		d = defaultdict(int)
		presum = 0
		ans = 0
		d[0] = 1
		for i in range(len(nums)):
			presum = presum + nums[i]
			if presum in d:
				ans += d[presum]
			d[presum] += 1
		return True if ans > 0 else False


class Solution:

	def subArrayExists(self, arr, n):
		s = 0
		l = []
		for i in arr:
			s = s + i
			l.append(s)
		d = {}
		for i in l:
			if i in d:
				d[i] += 1
			else:
				d[i] = 1
		flag = 0
		for i in d:
			if d[i] >= 2 or i == 0:
				flag = 1
				break
		if flag == 1:
			return True
		else:
			return False


class Solution:

	def subArrayExists(self, arr, n):
		prefixArr = []
		prefixArr.append(arr[0])
		dict1 = {}
		dict1[arr[0]] = 0
		for i in range(1, n):
			prefixArr.append(prefixArr[i - 1] + arr[i])
			if prefixArr[i] == 0:
				return True
			if prefixArr[i] not in dict1:
				dict1[prefixArr[i]] = i
			else:
				return True
		return False


class Solution:

	def subArrayExists(self, arr, n):
		dict = {}
		s = 0
		for i in arr:
			s += i
			if s == 0 or i == 0 or s in dict:
				return True
			else:
				dict[s] = 3
		return False


class Solution:

	def subArrayExists(self, arr, n):
		sum_set = set()
		sum_set.add(0)
		sum_so_far = 0
		for num in arr:
			sum_so_far += num
			if sum_so_far in sum_set:
				return True
				break
			sum_set.add(sum_so_far)


class Solution:

	def subArrayExists(self, arr, n):
		l = []
		sum_ = 0
		d = {}
		for i in range(n):
			sum_ += arr[i]
			if sum_ == 0 or sum_ in d:
				return True
			d[sum_] = 1
		return False


from collections import defaultdict

class Solution:

	def subArrayExists(self, arr, n):
		d = defaultdict(lambda : 0)
		total = 0
		for x in arr:
			total += x
			if total in d:
				return True
			if x == 0 or total == 0:
				return True
			d[total] += 1


class Solution:

	def subArrayExists(self, arr, n):
		dict = {}
		s = set()
		sum = 0
		for i in range(len(arr)):
			sum += arr[i]
			if sum == 0 or sum in dict:
				return True
			dict[sum] = 1
		return False


class Solution:

	def subArrayExists(self, arr, n):
		k = 0
		d = {0: 1}
		sum1 = 0
		for i in arr:
			sum1 = sum1 + i
			if sum1 - k in d:
				return 1
			if sum1 not in d:
				d[sum1] = 1
			if sum1 in d:
				d[sum1] = d[sum1] + 1
		return 0


class Solution:

	def subArrayExists(self, arr, n):
		si = 0
		s = 0
		dic = {}
		while si < n:
			s += arr[si]
			if s == 0:
				return True
			if s in dic:
				return True
			else:
				dic[s] = si
			si += 1
		return False


class Solution:

	def subArrayExists(self, arr, n):
		seen = {}
		sum_upto = 0
		for ele in arr:
			sum_upto += ele
			if sum_upto == 0:
				return True
			elif sum_upto in seen:
				return True
			else:
				seen[sum_upto] = 1
		return False


class Solution:

	def subArrayExists(self, nums, n):
		curr_sum = nums[0]
		prefix = [curr_sum]
		for i in range(1, len(nums)):
			curr_sum += nums[i]
			prefix.append(curr_sum)
		d = {}
		for i in range(len(prefix)):
			if prefix[i] == 0:
				return True
			if prefix[i] not in d.keys():
				d[prefix[i]] = [i]
			else:
				d[prefix[i]].append(i)
		for i in d.values():
			if len(i) > 1:
				return True
		return False


class Solution:

	def subArrayExists(self, arr, n):
		a = set()
		a.add(0)
		s = 0
		for i in arr:
			s += i
			if s in a:
				return True
			a.add(s)
		return s == 0


class Solution:

	def subArrayExists(self, arr, n):
		prefix_sum = 0
		prefix_sum_set = set()
		for element in arr:
			prefix_sum = prefix_sum + element
			if prefix_sum == 0:
				return True
			if prefix_sum in prefix_sum_set:
				return True
			else:
				prefix_sum_set.add(prefix_sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		s1 = set()
		cs = 0
		for i in range(n):
			cs = cs + arr[i]
			if cs in s1 or cs == 0:
				return True
			s1.add(cs)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		st = set()
		prefixsum = []
		sum = 0
		for i in arr:
			sum += i
			if sum == 0 or sum in st:
				return True
			else:
				st.add(sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		seen = set()
		sum1 = 0
		for i in range(n):
			seen.add(sum1)
			sum1 += arr[i]
			if sum1 in seen:
				return True
		return False


class Solution:

	def subArrayExists(self, arr, n):
		d = {}
		c = 0
		for i in range(n):
			c += arr[i]
			if c in d or c == 0:
				return 1
			else:
				d[c] = 1
		if c == 0:
			return 1
		else:
			return 0


class Solution:

	def subArrayExists(self, arr, n):
		s = 0
		h = {0}
		dik = {}
		for i in range(n):
			if arr[i] == 0:
				return True
			s += arr[i]
			if s == 0:
				return True
			if s in dik:
				return True
			dik[s] = s
		return False


class Solution:

	def subArrayExists(self, arr, n):
		prev_sum = set()
		curr_sum = 0
		for i in arr:
			curr_sum += i
			if curr_sum == 0 or curr_sum in prev_sum:
				return True
			prev_sum.add(curr_sum)
		return False


class Solution:

	def subArrayExists(self, arr, n):
		prefix_sum = {0: -1}
		sum = 0
		k = 0
		for i in range(len(arr)):
			sum += arr[i]
			if sum - k in prefix_sum:
				return True
			if sum not in prefix_sum:
				prefix_sum[sum] = i
		return False


class Solution:

	def subArrayExists(self, arr, n):
		_d = {}
		_csum = 0
		for i in range(n):
			_csum += arr[i]
			if _csum in _d.keys() or _csum == 0:
				return True
			else:
				_d[_csum] = -1
		if _csum == 0:
			return True
		return False


class Solution:

	def subArrayExists(self, arr, n):
		s = 0
		d = {}
		d[s] = True
		for i in range(len(arr)):
			s += arr[i]
			if s in d:
				return True
			d[s] = True
		return False