Given an array arr of size n and an integer X. Find if there's a triplet in the array which sums up to the given integer X. 
Example 1:
Input:
n = 6, X = 13
arr[] = [1 4 45 6 10 8]
Output:
1
Explanation:
The triplet {1, 4, 8} in 
the array sums up to 13.
Example 2:
Input:
n = 5, X = 10
arr[] = [1 2 4 3 6]
Output:
1
Explanation:
The triplet {1, 3, 6} in 
the array sums up to 10.
Your Task:
You don't need to read input or print anything. Your task is to complete the function find3Numbers() which takes the array arr[], the size of the array (n) and the sum (X) as inputs and returns True if there exists a triplet in the array arr[] which sums up to X and False otherwise.
Expected Time Complexity: O(n^{2})
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{3}
1 ≤ A[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Sorting

Amortized analysis

Starter code: #User function Template for python3
class Solution:
     
    #Function to find if there exists a triplet in the 
    #array A[] which sums up to X.
    def find3Numbers(self,A, n, X):
        # Your Code Here

Solutions:
class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		j = 0
		k = n - 1
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				total = A[i] + A[j] + A[k]
				if total == X:
					return 1
				elif total > X:
					k -= 1
				else:
					j += 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(n - 1):
			temp_sum = X - A[i]
			s = set()
			for j in range(i + 1, n):
				if temp_sum - A[j] in s:
					return True
				s.add(A[j])
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		count = 0
		z = {}
		for i in A:
			z.setdefault(i, 0)
			z[i] += 1
		x = 0
		y = 0
		for i in range(n):
			for j in range(i + 1, n):
				x = 0
				y = 0
				if X - A[i] - A[j] == A[i]:
					x = 1
				if X - A[i] - A[j] == A[j]:
					y = 1
				if X - A[i] - A[j] in z:
					count += z[X - A[i] - A[j]] - x - y
		return count


class Solution:

	def find3Numbers(self, A, n, X):
		dic = dict()
		for i in range(0, n - 2):
			for j in range(i + 1, n):
				curr = X - (A[i] + A[j])
				if curr in dic:
					return 1
				else:
					dic[A[j]] = 1
			dic = dict()
		return 0


class Solution:

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


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for i in range(n):
			l = i + 1
			r = n - 1
			while l < r:
				if A[l] + A[r] + A[i] == X:
					return True
				if A[l] + A[r] + A[i] > X and r != 0:
					r -= 1
				else:
					l += 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for i in range(n):
			low = i + 1
			high = n - 1
			y = X - A[i]
			while low < high:
				if A[low] + A[high] == y:
					return 1
				elif A[low] + A[high] > y:
					high -= 1
				else:
					low += 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		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 == X:
					return True
				elif curr_sum < X:
					l += 1
				else:
					r -= 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		A = sorted(A)
		if n <= 3:
			return False
		for i in range(n):
			front = i + 1
			back = n - 1
			while front < n and back > i and (front < back):
				if A[front] + A[back] == X - A[i]:
					front += 1
					back -= 1
					return True
				elif A[front] + A[back] < X - A[i]:
					front += 1
				else:
					back -= 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left < right:
				current_sum = A[i] + A[left] + A[right]
				if current_sum == X:
					return True
				elif current_sum < X:
					left += 1
				else:
					right -= 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		import collections
		arr_f = [0] * 10 ** 6
		for i in A:
			arr_f[i] = arr_f[i] + 1
		for i in range(n):
			x_new = X - A[i]
			arr_f[A[i]] = arr_f[A[i]] - 1
			for j in range(i + 1, n):
				if arr_f[x_new - A[j]] > 0:
					if x_new - A[j] != A[j]:
						return True
					elif x_new - A[j] == A[j] and arr_f[A[j]] > 1:
						return True
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		cnt = 0
		for i in range(n - 2):
			requiredSum = X - A[i]
			(left, right) = (i + 1, n - 1)
			while left < right:
				currentSum = A[left] + A[right]
				if currentSum == requiredSum:
					cnt += 1
					left += 1
					right -= 1
				elif currentSum > requiredSum:
					right -= 1
				else:
					left += 1
		return cnt


class Solution:

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


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for i in range(n - 3):
			l = i + 1
			k = n - 1
			while l < k:
				sum = A[i] + A[l] + A[k]
				if sum == X:
					return 1
				elif sum < X:
					l += 1
				else:
					k -= 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		count = 0
		A.sort()
		for i in range(n):
			if i > 0 and A[i] == A[i - 1]:
				continue
			j = i + 1
			k = n - 1
			while j < k:
				sum = A[i] + A[j] + A[k]
				if sum < X:
					j += 1
				elif sum > X:
					k -= 1
				else:
					count += 1
					j += 1
					k -= 1
					while j < k and A[j] == A[j - 1]:
						j += 1
					while j < k and A[k] == A[k + 1]:
						k -= 1
		return count


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for i in range(n):
			j = i + 1
			k = n - 1
			while j < k:
				sum = A[i] + A[j] + A[k]
				if sum == X:
					return True
				elif sum < X:
					j = j + 1
				else:
					k = k - 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for i in range(n - 2):
			rem_sum = X - A[i]
			j = i + 1
			k = n - 1
			while j != k:
				s = A[j] + A[k]
				if s < rem_sum:
					j += 1
				else:
					k -= 1
				if s == rem_sum:
					return True
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(1, n):
			temp = A[i]
			curr = i
			while A[curr] < A[curr - 1] and curr >= 1:
				(A[curr], A[curr - 1]) = (A[curr - 1], A[curr])
				curr = curr - 1
		remain = 0
		ans = []
		for i in range(n):
			remain = X - A[i]
			if remain <= 0:
				continue
			else:
				st = i + 1
				en = n - 1
				while st < en and en < n:
					if A[st] + A[en] < remain:
						st += 1
					elif A[st] + A[en] > remain:
						en -= 1
					else:
						return True
		return False


class Solution:

	def find3Numbers(self, arr, n, X):
		dic = {}
		for i in range(n):
			dic[arr[i]] = dic.get(arr[i], []) + [i]
		count = 0
		for i in range(n):
			for j in range(i + 1, n):
				temp = X - arr[i] - arr[j]
				if temp in dic:
					if i not in dic[temp] and j not in dic[temp]:
						count += 1
		return count


class Solution:

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


class Solution:

	def find3Numbers(self, A, n, X):
		A = sorted(A)
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				tmp = A[i] + A[l] + A[r]
				if tmp == X:
					return 1
				elif tmp > X:
					r -= 1
				else:
					l += 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		A = sorted(A)
		for i in range(n - 2):
			j = i + 1
			k = n - 1
			while j < k:
				sum = X - A[i]
				if A[j] + A[k] == sum:
					return 1
				elif A[j] + A[k] > sum:
					k -= 1
				else:
					j += 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		dic = {}
		for i in A:
			if i not in dic:
				dic[i] = 1
				continue
			dic[i] += 1
		count = 0
		for a in range(n):
			for b in range(n):
				if a == b:
					continue
				key1 = A[a]
				key2 = A[b]
				dic[key1] -= 1
				dic[key2] -= 1
				if X - A[a] - A[b] in dic and dic[X - A[a] - A[b]] > 0:
					return True
				dic[key1] += 1
				dic[key2] += 1
		return count >= 1


class Solution:

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


class Solution:

	def find3Numbers(self, A, n, X):
		a = sorted(A)
		for i in range(n - 2):
			s = X - a[i]
			start = i + 1
			end = n - 1
			while start < end:
				if a[start] + a[end] == s:
					return True
				elif a[start] + a[end] < s:
					start += 1
				else:
					end -= 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(n):
			newTarget = X - A[i]
			hashtable = {}
			for j in range(i + 1, n):
				need = newTarget - A[j]
				if need in hashtable:
					return True
				hashtable[A[j]] = 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(n):
			A.sort()
			c = A[i]
			p1 = i + 1
			p2 = n - 1
			while p1 < p2:
				if A[p1] + A[p2] == X - c:
					return True
				elif A[p1] + A[p2] < X - c:
					p1 += 1
				else:
					p2 -= 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		count = 0
		for i in range(n):
			st = set()
			sm = X - A[i]
			for j in range(i + 1, n):
				if sm - A[j] in st:
					count += 1
				else:
					st.add(A[j])
		return count


class Solution:

	def find3Numbers(self, a, n, x):
		a.sort()
		for i in range(n - 2):
			l = i + 1
			h = n - 1
			while l < h:
				k = a[i] + a[l] + a[h]
				if k == x:
					return True
				elif k < x:
					l += 1
				elif k > x:
					h -= 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):

		def two_sum(a, arr, x):
			d = {}
			for i in range(len(arr)):
				if x - arr[i] in d:
					return True
				else:
					d[arr[i]] = i
			return False
		A.sort()
		for i in range(n):
			if two_sum(A[i], A[i + 1:], X - A[i]):
				return True
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		res = []
		for (i, v) in enumerate(A):
			if i > 0 and v == A[i - 1]:
				continue
			(left, right) = (i + 1, len(A) - 1)
			while left < right:
				currentSum = A[i] + A[left] + A[right]
				if currentSum > X:
					right -= 1
				elif currentSum < X:
					left += 1
				else:
					res.append(A[i] + A[left] + A[right])
					left += 1
					while A[left] == A[left - 1] and left < right:
						left += 1
		return res


class Solution:

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

	def find3Numbers(self, A, n, X):
		return self.f(A, n, X)


class Solution:

	def find3Numbers(self, arr, n, X):
		arr.sort()
		for i in range(n - 2):
			l = i + 1
			r = n - 1
			while l < r:
				total = arr[i] + arr[l] + arr[r]
				if total > X:
					r -= 1
				elif total < X:
					l += 1
				else:
					return True


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for i in range(n - 2):
			st = i + 1
			en = len(A) - 1
			while st < en:
				if A[i] + A[st] + A[en] == X:
					return True
				elif A[i] + A[st] + A[en] < X:
					st += 1
				else:
					en -= 1
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		dic = {}
		for i in A:
			if i in dic:
				dic[i] += 1
			else:
				dic[i] = 1
		for i in range(0, n):
			dic[A[i]] -= 1
			for j in range(i + 1, n):
				dic[A[j]] -= 1
				s = X - (A[i] + A[j])
				if s in dic and dic[s]:
					return 1
				dic[A[j]] += 1
			dic[A[i]] += 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		sum = X
		for i in range(0, n - 1):
			s = set()
			curr_sum = sum - A[i]
			for j in range(i + 1, n):
				if curr_sum - A[j] in s:
					return 1
				s.add(A[j])
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(n):
			h = {}
			t = X - A[i]
			for j in range(n):
				if i == j:
					continue
				if t - A[j] in h:
					return True
				else:
					h[A[j]] = 1


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(n):
			T = X - A[i]
			h2 = {}
			for j in range(n):
				if i == j:
					continue
				if T - A[j] in h2:
					return True
				else:
					h2[A[j]] = 1


class Solution:

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


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(n):
			d = [0 for _ in range(X + 1)]
			for j in range(i + 1, n):
				if X - A[i] - A[j] > 0 and d[X - A[i] - A[j]] == 1:
					return 1
				elif A[j] <= X:
					d[A[j]] = 1
				else:
					continue
		return 0


class Solution:

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


class Solution:

	def find3Numbers(self, arr, n, x):
		arr.sort()
		for i in range(n - 2):
			l = i + 1
			h = n - 1
			while l < h:
				if arr[h] > x:
					h = h - 1
				if arr[l] + arr[h] + arr[i] == x:
					return True
				elif arr[l] + arr[h] + arr[i] > x:
					h = h - 1
				else:
					l = l + 1
		return False


class Solution:

	def find3Numbers(self, A, arr_size, sum):
		for i in range(0, arr_size - 1):
			s = set()
			curr_sum = sum - A[i]
			for j in range(i + 1, arr_size):
				if curr_sum - A[j] in s:
					return True
				s.add(A[j])
		return False


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		for (i, a) in enumerate(A):
			if i > 0 and a == A[i - 1]:
				continue
			(l, r) = (i + 1, n - 1)
			while l < r:
				x = a + A[l] + A[r]
				if x > X:
					r -= 1
				elif x < X:
					l += 1
				else:
					return True
		return False


class Solution:

	def find3Numbers(self, nums, n, k):
		ans = set()
		nums.sort()
		for i in range(len(nums)):
			start = i + 1
			end = len(nums) - 1
			while start < end:
				sum_ = nums[start] + nums[end] + nums[i]
				if sum_ == k:
					ans.add((nums[i], nums[start], nums[end]))
					while start < end and nums[start] == nums[start + 1]:
						start += 1
					start += 1
					while start < end and nums[end] == nums[end - 1]:
						end -= 1
					end -= 1
				elif sum_ > k:
					end -= 1
				else:
					start += 1
		return len(ans)


class Solution:

	def find3Numbers(self, nums, n, X):
		res = []
		nums.sort()
		for (i, a) in enumerate(nums):
			if i > 0 and a == nums[i - 1]:
				continue
			(left, right) = (i + 1, len(nums) - 1)
			while left < right:
				s = a + nums[left] + nums[right]
				if s > X:
					right -= 1
				elif s < X:
					left += 1
				else:
					return True
		return False


class Solution:

	def twoSum(self, arr, target):
		hash_set = set()
		for num in arr:
			if num in hash_set:
				return True
			else:
				hash_set.add(target - num)
		return False

	def find3Numbers(self, A, n, X):
		target = X
		for i in range(n - 2):
			num = A[i]
			if self.twoSum(A[i + 1:], target - num):
				return True
		return False


class Solution:

	def find3Numbers(self, A, n, x):
		A.sort()
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left < right:
				sm = A[i] + A[left] + A[right]
				if sm == x:
					return 1
				elif sm > x:
					right -= 1
				else:
					left += 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		for i in range(n - 1):
			a = set()
			for j in range(i + 1, n):
				if X - (A[i] + A[j]) in a:
					return 1
				a.add(A[j])
		return 0


class Solution:

	def find3Numbers(self, a, n, x):
		a.sort()
		for i in range(n):
			num1 = a[i]
			low = i + 1
			high = n - 1
			reqsum = x - num1
			while low < high:
				if a[low] + a[high] == reqsum:
					return True
				elif a[low] + a[high] < reqsum:
					low += 1
				else:
					high -= 1
		return False


from collections import Counter

class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		c = 0
		for i in range(n):
			low = i + 1
			high = n - 1
			while low < high:
				if A[i] + A[low] + A[high] == X:
					return 1
				elif A[i] + A[low] + A[high] > X:
					high -= 1
				else:
					low += 1
		return 0


class Solution:

	def find3Numbers(self, A, n, X):
		A.sort()
		count = 0
		for i in range(n - 2):
			left = i + 1
			right = n - 1
			while left < right:
				s = A[i] + A[left] + A[right]
				if s == X:
					count += 1
					break
				elif s > X:
					right -= 1
				else:
					left += 1
		return count


class Solution:

	def find3Numbers(self, A, n, X):
		A = set(A)
		A = list(A)
		n = len(A)
		for i in range(n - 1):
			s = A[i]
			for j in range(i + 1, n):
				if X - (s + A[j]) in A[j + 1:n]:
					return True
		return False