Pythagorean Triplets

PROBLEM STATEMENT

You are given an array of n integers (a1, a2,....,an), you need to find if the array contains a pythagorean triplet or not.

An array is said to have a pythagorean triplet if there exists three integers x,y and z in the array such that x^2 + y^2 = z^2.

Note

1. The integers x,y and z might not be distinct , but they should be present at different locations in the array i.e if a[i] = x, a[j] = y and a[k] = z, then i,j and k should be pairwise distinct.
2. The integers a,b and c can be present in any order in the given array.

Input Format:

The first line contains a single integer t -  the number of test cases. Each test case consists of 2 lines as follows:
The first  line of each test case will contain the integer n, denoting the total number of elements in the array.
The second line of each test case will contain n space-separated integers a1,a2,....,an ,  where ai is the ith element of the array..

Output Format:

For each test case, print “yes”, if the array contains a pythagorean triplet,”no” otherwise.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <=  T <= 10
3 <=  N <= 10^3
1 <= a[i] <= 10^4 

Time Limit: 1sec

Approach 1

One simple naive solution is to try every possible triplet present in the array as a candidate for the pythagorean triplet.
So, we simply run three nested loops, and pick three integers and check if they follow the property given in the problem statement( i.e for three integers a,b and c a^2 b^2 = c^2).
If we find any required triplet, we return true. Otherwise, if we can't find any valid triplet, we return false.

Try Problem

Approach 2

Let us assume that the maximum element in the array is ‘mx’, now we know that if there is a valid pythagorean triplet (a,b,c) in the array , then a<=mx, b<=mx, and c<=mx.
Thus, we can iterate over all possible combinations of ‘a’ and ‘b’ using two loops, which will run from 1 to ‘’mx’, and check that if there exists a valid ‘c’ in the array for the current ‘a’ and ‘b’.
To check for valid ‘c’, we can store the frequency of all the elements of the array, in a hashmap, and while checking compute the square root of a^2 + b^2, and check if this square root is an integer and it is present in the hashmap or not. If yes , return true.

Try Problem

Approach 3

Before jumping into the actual solution , let us observe few things:

Given two integers a1 and a2 such that a1<a2, then a1^2 < a2^2.
According to the property: a^2 + b^2 = c^2, it is obvious that a^2 < c^2 , b^2 < c^2 , a<c and b<c.
Given three integers a1, a2 and b, such that a1<a2 , then a1^2+ b^2 < a2^2 + b^2.
Given three integers a1, a2 and b, such that a1>a2 , then a1^2+ b^2 > a2^2 + b^2.

Let us assume that there are three integers a, b and c in the array such that a^2 + b^2 = c^2.
Now by using the above four observations, let us assume that in the given array the integers are in non-descending order. If we fix the rhs(right hand side) of the property i.e c^2, then by observation 2 , it is clear that if the integer c is present at ith index in the array, then both integers a and b will be present before c, that is their indices will be less than ‘i’.
So let us first sort the array in non-decreasing order. Now in every iteration, fix the current element as a possible candidate for ‘c’. Let c be present at ith index of the array , such that there are at least two elements before c. Now we just need to find two elements a and b such that a<c and b<c and a^2 + b^2 = c^2.
So we will use two pointers, one will start from the beginning and the other will start from (i-1)th index as all elements less than c are in this range.
Let the two pointers be ‘j’ and ‘k’ , such that j is starting from the beginning. Now while j is less than k, let us assume that x= a[j] and y = a[k]. Now there are three possibilities:

If x^2 + y^2 = c^2, then we have found a valid triplet and we simply return true.
Else if x^2 + y^2 <c^2, then we need to increase the sum on the lhs and for that we will increment the pointer ‘j’, (as in a sorted array a[j] < a[j+1]) and thus increase x(observation 3).
Else x^2 + y^2 > c^2, then to decrease the sum on the lhs, we will decrement the pointer ‘k’ ( as a[k] > a[k-1]) and thus decrease y(observation 4).