Given an array arr of N integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a^{2} + b^{2} = c^{2}, otherwise false.
Example 1:
Input:
N = 5
Arr[] = {3, 2, 4, 6, 5}
Output: Yes
Explanation: a=3, b=4, and c=5 forms a
pythagorean triplet.
Example 2:
Input:
N = 3
Arr[] = {3, 8, 5}
Output: No
Explanation: No such triplet possible.
Your Task:
Complete the function checkTriplet() which takes an array arr, single integer n, as input parameters and returns boolean denoting answer to the problem. You don't to print answer or take inputs. 
Note: The driver will print "Yes" or "No" instead of boolean.
Expected Time Complexity: O(max(Arr[i])^{2})
Expected Auxiliary Space: O(max(Arr[i]))
Constraints:
1 <= N <= 10^{7}
1 <= Arr[i] <= 1000

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Data structures

Starter code: #User function Template for python3

class Solution:



	def checkTriplet(self,arr, n):

    	# code here

Solutions:
class Solution:

	def checkTriplet(self, arr, n):
		arr.sort()
		A = [i ** 2 for i in arr]
		for i in A:
			for j in A:
				sm = i + j
				if sm < A[n - 1]:
					if sm in A:
						return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		for i in range(n - 1):
			for j in range(i + 1, n):
				temp = arr[i] ** 2 + arr[j] ** 2
				temp = temp ** 0.5
				if temp - temp // 1 == 0:
					temp = int(temp)
					if temp in arr:
						return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		square = list([x ** 2 for x in set(arr)])
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] ** 2 + arr[j] ** 2 in square:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		squares = [x ** 2 for x in set(arr)]
		values = dict()
		for v in squares:
			values[v] = True
		for i in range(len(squares)):
			for j in range(i + 1, len(squares)):
				if squares[i] + squares[j] in values:
					return True
		return False


from math import sqrt

class Solution:

	def checkTriplet(self, arr, n):
		arr.sort()
		for i in range(n - 2):
			for j in range(i + 1, n - 1):
				if sqrt(arr[i] * arr[i] + arr[j] * arr[j]) in arr[j + 1:]:
					return 'True'
		return False


class Solution:

	def checkTriplet(self, arr, n):
		sqarr = []
		for i in range(0, n):
			sqarr.append(arr[i] * arr[i])
		sqarr.sort()
		for i in range(n - 1, -1, -1):
			j = 0
			k = i - 1
			while j < k:
				if sqarr[i] == sqarr[j] + sqarr[k]:
					return 1
				elif sqarr[i] > sqarr[j] + sqarr[k]:
					j = j + 1
				else:
					k = k - 1
		return 0


class Solution:

	def checkTriplet(self, a, n):
		a.sort()
		flag = False
		for i in range(0, len(a) - 2):
			for j in range(i + 1, len(a) - 1):
				if (a[i] * a[i] + a[j] * a[j]) ** 0.5 in a:
					flag = True
					break
			if flag == True:
				break
		return flag


class Solution:

	def checkTriplet(self, arr, n):
		k1 = {}
		k2 = {}
		for i in arr:
			k1[i] = 1
			k2[i * i] = 1
		for i in k2:
			for j in k2:
				if j != i:
					if j + i in k2:
						return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		sq = [i * i for i in arr]
		s = set(sq)
		for i in range(n):
			for j in range(i + 1, n):
				if sq[i] + sq[j] in s:
					return True
		return False


class Solution:

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


class Solution:

	def checkTriplet(self, arr, n):
		dict_set = set()
		for i in arr:
			dict_set.add(i * i)
		for i in range(len(arr)):
			for j in range(i + 1, len(arr)):
				if arr[i] * arr[i] + arr[j] * arr[j] in dict_set:
					return 1
		return 0


class Solution:

	def checkTriplet(self, arr, n):
		new_arr = set(map(lambda x: x * x, arr))
		for i in range(n - 1):
			for j in range(i + 1, n):
				x = arr[i] * arr[i] + arr[j] * arr[j]
				if x in new_arr:
					return True


class Solution:

	def checkTriplet(self, arr, n):
		for i in range(n):
			arr[i] = arr[i] * arr[i]
		arr.sort()
		for i in range(n - 1, 1, -1):
			a = 0
			b = i - 1
			while a < b:
				if arr[a] + arr[b] == arr[i]:
					return True
				elif arr[a] + arr[b] < arr[i]:
					a += 1
				else:
					b -= 1
		return False


class Solution:

	def checkTriplet(self, arr, n):
		for i in range(n):
			arr[i] = arr[i] ** 2
		freq = {}
		for i in range(n):
			freq[arr[i]] = True
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] + arr[j] in freq:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		se = set(map(lambda x: x * x, arr))
		for i in range(n - 1):
			for j in range(i + 1, n):
				x = arr[i] * arr[i] + arr[j] * arr[j]
				if x in se:
					return 'Yes'


from collections import defaultdict

class Solution:

	def checkTriplet(self, arr, n):
		square_counts = defaultdict(int)
		for a in arr:
			square_counts[a * a] += 1
		squares = list(sorted(square_counts.keys()))
		for i in range(len(squares)):
			si = squares[i]
			for j in range(len(squares) - 1, i, -1):
				sj = squares[j]
				if square_counts[sj - si] > 0:
					if sj - si == si:
						if square_counts[sj - si] > 1:
							return True
					else:
						return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		import math
		h = {arr[i]: 1 for i in range(n)}
		for i in range(n - 1):
			for j in range(i + 1, n):
				q = math.sqrt(arr[i] * arr[i] + arr[j] * arr[j])
				if q == int(q) and int(q) in h:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		sqr = [x * x for x in arr]
		sqr.sort()
		for i in range(n - 1, -1, -1):
			j = 0
			k = i - 1
			while j < k:
				if sqr[i] == sqr[j] + sqr[k]:
					return 1
				elif sqr[i] > sqr[j] + sqr[k]:
					j = j + 1
				else:
					k = k - 1
		return 0


class Solution:

	def checkTriplet(self, arr, n):
		arr.sort()
		data = set()
		for each in arr:
			data.add(each * each)
		for i in range(n):
			for j in range(i + 1, n):
				res = arr[i] * arr[i] + arr[j] * arr[j]
				if res in data:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		if n < 3:
			return False
		mx = max(arr) + 1
		lis = [0] * mx
		for i in range(n):
			lis[arr[i]] += 1
		for i in range(n):
			arr[i] = arr[i] * arr[i]
		arr = set(tuple(arr))
		for i in range(len(lis)):
			if lis[i] > 0:
				for j in range(len(lis)):
					if lis[j] > 0:
						p = i * i + j * j
						if p in arr:
							return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		squares = []
		for i in arr:
			squares.append(i ** 2)
		new = set(squares)
		for i in range(n):
			for j in range(i + 1, n):
				ans = arr[i] ** 2 + arr[j] ** 2
				if ans in new:
					return True
		return False


import math

class Solution:

	def checkTriplet(self, arr, n):
		maximum = 0
		maximum = max(arr)
		hash = [0] * (maximum + 1)
		for i in range(n):
			hash[arr[i]] += 1
		for i in range(1, maximum + 1):
			if hash[i] == 0:
				continue
			for j in range(1, maximum + 1):
				if i == j and hash[i] == 1 or hash[j] == 0:
					continue
				val = int(math.sqrt(i * i + j * j))
				if val * val != i * i + j * j:
					continue
				if val > maximum:
					continue
				if hash[val]:
					return True
		return False


import math

class Solution:

	def checkTriplet(self, arr, n):
		dict1 = {}
		for i in arr:
			if i * i not in dict1:
				dict1[i * i] = 1
		for i in dict1.keys():
			for j in dict1.keys():
				if i != j:
					if i + j in dict1:
						return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		arr.sort()
		for i in range(n - 2):
			b = i + 1
			c = i + 2
			while c < n:
				if arr[i] * arr[i] + arr[b] * arr[b] == arr[c] * arr[c]:
					return True
				elif arr[i] * arr[i] + arr[b] * arr[b] > arr[c] * arr[c]:
					c = c + 1
				else:
					b = b + 1
		return False


class Solution:

	def checkTriplet(self, arr, n):
		d = {}
		for i in range(n):
			d[arr[i] * arr[i]] = i
		for i in range(1, 1001):
			for j in range(i + 1, 1001):
				x = d.get(i * i)
				y = d.get(j * j)
				z = d.get(i * i + j * j)
				if x is not None and y is not None and (z is not None):
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		arr1 = set()
		for i in range(n):
			arr1.add(arr[i] * arr[i])
		for i in range(n):
			for j in range(i + 1, n):
				if arr[i] * arr[i] + arr[j] * arr[j] in arr1:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		sqr = set([x * x for x in arr])
		for i in range(n - 1):
			for j in range(i + 1, n):
				if arr[i] != arr[j] and arr[i] * arr[i] + arr[j] * arr[j] in sqr:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		hmap = {}
		for i in range(n):
			temp = arr[i] * arr[i]
			if temp in hmap:
				hmap[temp] += 1
			else:
				hmap[temp] = 1
		for i in range(n):
			for j in range(i + 1, n):
				tot = arr[i] * arr[i] + arr[j] * arr[j]
				if tot in hmap.keys():
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		hash_map = {}
		val = 0
		for i in range(n):
			val = arr[i] * arr[i]
			if val in hash_map:
				hash_map[val] += 1
			else:
				hash_map[val] = i
		for i in range(n - 1):
			for j in range(i + 1, n):
				val = arr[i] * arr[i]
				val += arr[j] * arr[j]
				if val in hash_map:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		res = [i ** 2 for i in arr]
		res.sort()
		for k in range(n - 1):
			for j in range(k + 1, n):
				if res[k] + res[j] in res:
					return 1
		else:
			return 0


class Solution:

	def checkTriplet(self, arr, n):
		li = [x * x for x in arr]
		set1 = set(li)
		for i in range(n):
			for j in range(i + 1, n):
				summ = li[i] + li[j]
				if summ in set1:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		a = [x * x for x in arr]
		s = set(a)
		for i in range(n):
			for j in range(i + 1, n):
				d = a[i] + a[j]
				if d in s:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		abhi = [x * x for x in arr]
		s = set(abhi)
		for i in range(n):
			for j in range(i + 1, n):
				diff = abhi[i] + abhi[j]
				if diff in s:
					return True
		return False


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def checkTriplet(self, arr, n):
		arr.sort(reverse=True)
		for i in range(n):
			j = i + 1
			k = n - 1
			target = arr[i] ** 2
			while j < k:
				if arr[k] ** 2 + arr[j] ** 2 == target:
					return True
				elif arr[k] * arr[k] + arr[j] ** 2 < target:
					k -= 1
				else:
					j += 1
		return False


class Solution:

	def checkTriplet(self, arr, n):
		squares = {}
		flag = 0
		for num in arr:
			squares[num] = num ** 2
		for a in arr:
			for b in arr:
				if squares[a] + squares[b] in squares.values():
					flag = 1
					return True
		if flag == 0:
			return False


class Solution:

	def checkTriplet(self, arr, n):
		a = list(set(arr))
		a.sort()
		for i in range(2, len(a)):
			j = 0
			k = i - 1
			while j < k:
				t = a[j] * a[j] + a[k] * a[k]
				if t == a[i] * a[i]:
					return True
				elif t > a[i] * a[i]:
					k -= 1
				else:
					j += 1
		return False


class Solution:

	def checkTriplet(self, arr, n):
		a = []
		for p in arr:
			a.append(p ** 2)
		a.sort()
		i = 0
		j = 1
		k = 2
		while i < n - 2:
			j = i + 1
			while j < n - 1:
				k = j + 1
				while k < n:
					if a[i] + a[j] == a[k]:
						return a[i] + a[j] == a[k]
					k += 1
				j += 1
			i += 1
		return False


class Solution:

	def checkTriplet(self, arr, n):
		d = [x ** 2 for x in arr]
		d.sort()
		for i in range(n):
			for j in range(i + 1, n):
				for k in range(j + 1, n):
					if d[i] + d[j] == d[k]:
						return 1
						break
		return 0


class Solution:

	def checkTriplet(self, arr, n):
		arr.sort()
		for i in range(len(arr)):
			d = arr[i]
			dic = {}
			for j in range(i + 1):
				if d ** 2 - arr[j] ** 2 in dic:
					return True
				else:
					dic[arr[j] ** 2] = True


class Solution:

	def checkTriplet(self, arr, n):
		square = [i ** 2 for i in set(arr)]
		dict = {}
		for i in square:
			dict[i] = 1
		for i in range(len(square)):
			for j in range(i + 1, len(square)):
				if square[i] + square[j] in dict:
					return True
		return False


class Solution:

	def checkTriplet(self, arr, n):
		s = set((x * x for x in arr))
		for i in range(0, len(arr) - 1):
			for j in range(i + 1, n):
				if arr[i] ** 2 + arr[j] ** 2 in s:
					return True
		return False


import math

class Solution:

	def checkTriplet(self, nums, n):
		if len(nums) < 3:
			return 0
		for i in range(n):
			nums[i] = nums[i] * nums[i]
		nums.sort()
		for i in range(n - 1, 1, -1):
			s1 = 0
			s2 = i - 1
			while s1 < s2:
				if nums[i] == nums[s1] + nums[s2]:
					return True
				elif nums[i] > nums[s1] + nums[s2]:
					s1 += 1
				else:
					s2 -= 1
		return False


class Solution:

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


import math

class Solution:

	def checkTriplet(self, arr, n):
		for i in range(n):
			for j in range(i, n):
				sum = arr[i] * arr[i] + arr[j] * arr[j]
				if int(math.sqrt(sum)) * int(math.sqrt(sum)) == sum and math.sqrt(sum) in arr:
					return True
		return False