Given an array arr[] of n integers. Check whether it contains a triplet that sums up to zero. 
Note: Return 1, if there is at least one triplet following the condition else return 0.
Example 1:
Input: n = 5, arr[] = {0, -1, 2, -3, 1}
Output: 1
Explanation: 0, -1 and 1 forms a triplet
with sum equal to 0.
Example 2:
Input: n = 3, arr[] = {1, 2, 3}
Output: 0
Explanation: No triplet with zero sum exists. 
Your Task:
You don't need to read input or print anything. Your task is to complete the boolean function findTriplets() which takes the array arr[] and the size of the array (n) as inputs and print 1 if the function returns true else print 0 if the function returns false. 
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(1)
Constrains:
1 <= n <= 10^{4}
-10^{6} <= A_{i} <= 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Sorting

Amortized analysis

Complete search

Data structures

Starter code: #User function Template for python3



class Solution:

    #Function to find triplets with zero sum.    

    def findTriplets(self, arr, n):

        #code here

Solutions:
class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(len(arr)):
			left = i + 1
			right = n - 1
			while left < right:
				sum = arr[i] + arr[left] + arr[right]
				if sum == 0:
					return True
				elif sum > 0:
					right -= 1
				else:
					left += 1
		return False


class Solution:

	def findTriplets(self, a, n):
		a.sort()
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				curr_sum = a[i] + a[l] + a[r]
				if curr_sum == 0:
					return 1
				elif curr_sum < 0:
					l += 1
				else:
					r -= 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n):
			left = i + 1
			right = n - 1
			while left < right:
				sum = arr[i] + arr[left] + arr[right]
				if sum == 0:
					return 1
				elif sum > 0:
					right = right - 1
				elif sum < 0:
					left = left + 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left < right:
				cur_sum = arr[i] + arr[left] + arr[right]
				if cur_sum == 0:
					return 1
				elif cur_sum < 0:
					left += 1
				else:
					right -= 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n):
			low = i + 1
			high = n - 1
			while low < high:
				sum = arr[i] + arr[low] + arr[high]
				if sum == 0:
					return True
				elif sum < 0:
					low += 1
				else:
					high -= 1


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n):
			l = i + 1
			r = n - 1
			while l < r:
				sum = arr[l] + arr[i] + arr[r]
				if sum == 0:
					return 1
				elif sum < 0:
					l += 1
				else:
					r -= 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n - 2):
			if arr[i] > 0:
				break
			l = i + 1
			r = n - 1
			while l < r:
				triplet_sum = arr[i] + arr[l] + arr[r]
				if triplet_sum == 0:
					return True
				if triplet_sum < 0:
					l += 1
				else:
					r -= 1
		return False


class Solution:

	def findTriplets(self, arr, n):
		s = set()
		for i in range(n - 1):
			for j in range(i + 1, n):
				x = -(arr[i] + arr[j])
				if x in s:
					return 1
				else:
					s.add(arr[j])
			s = set()
		return 0


class Solution:

	def findTriplets(self, arr, n):
		dic = dict()
		for i in range(n - 2):
			for j in range(i + 1, n):
				x = -(arr[i] + arr[j])
				if x in dic:
					return 1
				else:
					dic[arr[j]] = 1
			dic = dict()
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				curr = arr[i] + arr[j] + arr[k]
				if curr == 0:
					return True
				elif curr < 0:
					j = j + 1
				else:
					k = k - 1
		return False


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n - 2):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			left = i + 1
			right = n - 1
			while left < right:
				total = arr[i] + arr[left] + arr[right]
				if total == 0:
					return True
				elif total < 0:
					left += 1
				else:
					right -= 1
		return False


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		s = 0
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				sum = arr[i] + arr[l] + arr[r]
				if sum == 0:
					return True
				elif sum > 0:
					r -= 1
				else:
					l += 1
		return False


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		j = 1
		k = n - 1
		sum1 = 0
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j < k:
				sum1 = arr[i] + arr[j] + arr[k]
				if sum1 == 0:
					return 1
				elif sum1 < 0:
					j += 1
				else:
					k -= 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		if len(arr) < 3:
			return 0
		else:
			i = 0
			while i < len(arr) - 1:
				j = i + 1
				k = len(arr) - 1
				while j < k:
					summ = arr[i] + arr[j] + arr[k]
					if summ == 0:
						return 1
					elif summ > 0:
						k -= 1
					elif summ < 0:
						j += 1
				i += 1
			return 0


class Solution:

	def findTwoSum(self, arr, target, left, right):
		while left < right:
			i_sum = arr[left] + arr[right]
			if i_sum == target:
				return True
			elif i_sum > target:
				right -= 1
			else:
				left += 1
		return False

	def findTriplets(self, arr, n):
		result = 0
		if n < 4:
			return result
		arr.sort()
		for i in range(n):
			i_target = -arr[i]
			if self.findTwoSum(arr, i_target, i + 1, n - 1):
				return 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		for i in range(n - 2):
			if i == 0 or arr[i] != arr[i - 1]:
				seen = set()
				for j in range(i + 1, n):
					complement = -arr[i] - arr[j]
					if complement in seen:
						return True
					seen.add(arr[j])
		return False


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n - 3):
			j = i + 1
			k = n - 1
			while j < k:
				res = arr[i] + arr[j] + arr[k]
				if res == 0:
					return 1
				elif res < 0:
					j += 1
				else:
					k -= 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n):
			left = i + 1
			right = n - 1
			while left < right:
				curr_sum = arr[i] + arr[left] + arr[right]
				if curr_sum == 0:
					return True
				elif curr_sum < 0:
					left += 1
				else:
					right -= 1


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for x in range(len(arr) - 2):
			l = x + 1
			r = n - 1
			nm = arr[x]
			while l < r:
				if arr[l] + arr[r] + nm == 0:
					return 1
				elif nm + arr[l] + arr[r] > 0:
					r = r - 1
				else:
					l = l + 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		darr = sorted(arr)
		left = 0
		right = n - 1
		sum = 0
		for i in range(n):
			left = i + 1
			right = n - 1
			while left < right:
				sum = darr[i] + darr[left] + darr[right]
				if sum == 0:
					return 1
				elif sum < 0:
					left += 1
				else:
					right -= 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n - 2):
			if i > 0 and arr[i] == arr[i - 1]:
				continue
			j = i + 1
			k = n - 1
			while j < k:
				s = arr[i] + arr[j] + arr[k]
				if s == 0:
					return 1
				elif s < 0:
					j += 1
				else:
					k -= 1
			if arr[i] > 0:
				break
		return 0


class Solution:

	def findTriplets(self, a, n):
		a.sort()
		for i in range(0, n - 2):
			if i == 0 or (i > 0 and a[i] != a[i - 1]):
				l = i + 1
				h = n - 1
				while l < h:
					if a[l] + a[h] == -a[i]:
						return True
					elif l < h and a[l] + a[h] < -a[i]:
						l += 1
					else:
						h -= 1
		return False


class Solution:

	def findTriplets(self, arr, n):
		st = False
		for each in arr:
			if each < 0:
				st = True
		if st == False:
			return 0
		arr.sort()
		res = 0
		for i in range(n - 2):
			(j, k) = (i + 1, n - 1)
			req = -arr[i]
			while j < k:
				if arr[j] + arr[k] > req:
					k -= 1
				elif arr[j] + arr[k] < req:
					j += 1
				else:
					return 1
		return 0


class Solution:

	def findTriplets(self, arr, n):
		a = {}
		for i in range(0, n - 1):
			for j in range(i + 1, n):
				if -(arr[j] + arr[i]) in a:
					return 1
			a[arr[i]] = i
		return 0


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n):
			l1 = i + 1
			r1 = n - 1
			while l1 < r1:
				sum_arr = arr[i] + arr[l1] + arr[r1]
				if sum_arr == 0:
					return True
				elif sum_arr > 0:
					r1 -= 1
				else:
					l1 += 1
		return False


class Solution:

	def findTriplets(Self, arr, n):
		arr.sort()
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left < right:
				curr_sum = arr[i] + arr[left] + arr[right]
				if curr_sum == 0:
					return True
				elif curr_sum < 0:
					left += 1
				else:
					right -= 1
		return False


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		seen = set()
		for (i, num1) in enumerate(arr):
			if num1 in seen:
				continue
			seen.add(num1)
			left_index = i + 1
			right_index = n - 1
			while left_index < right_index:
				num2 = arr[left_index]
				num3 = arr[right_index]
				total = num1 + num2 + num3
				if total == 0:
					return True
				elif total < 0:
					left_index += 1
				else:
					right_index -= 1
		return False


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		target = 0
		for i in range(0, n):
			h = set()
			for j in range(i + 1, n):
				total = arr[i] + arr[j]
				if target - total in h:
					return True
				else:
					h.add(arr[j])
		return False


class Solution:

	def findTriplets(self, arr, n):
		arr.sort()
		for i in range(n - 2):
			s = set()
			for j in range(i + 1, n):
				x = -(arr[i] + arr[j])
				if x in s:
					return True
				s.add(arr[j])
		return False


class Solution:

	def findTriplets(self, arr, n):
		if len(arr) < 3:
			return False
		arr.sort()
		for i in range(0, n - 1):
			sum1 = 0 - arr[i]
			l = i + 1
			k = n - 1
			while l < k:
				if arr[l] + arr[k] == sum1:
					return 1
				elif arr[l] + arr[k] < sum1:
					l = l + 1
				else:
					k = k - 1
		return 0