Question: Find Pythagorean triples in an unsorted array

Or

Find triplets in an integer array A[] which satisfy following condition:

a[i]^2 + a[j]^2 = a[k]^2

1) No need to compute square again and again (need extra space of order N)
2) start for last index of square array.
3) Find 2 elements in square array form beginning to that element, which adds up to it. For doing it in O(n), use solution given in last post.

Pseudo Code:

//Find triplets in an integer array which satisfy a[i]^2 + a[j]^2 = a[k]^2

A[] = 2 1 9 4 8 7 6 3 5 //input

Sort(A); // Sort the input array

//Finally A[] = 1 2 3 4 5 6 7 8 9

//Make an array of squares to avoid compute them again and again
for (i=0; i < n; i++)
{
Sq[i] = A[i]*A[i];
}
//Finally Sq[] =1 4 9 16 25 49 64 81

n = length;
for (i=n; i > 0; i--)
{
res = false;
//Search for 2 numbers in Sq array from 0 to i-1 which
//adds to Sq[i] like we have discussed in last post.
//This will give u a search result in O(n) time.
//Make res as true if we are able to find any triplet.

if (res)
{
process(triplet);
}
}

Efficiency: Efficiency is
(i) O(nlogn) : for sorting
(ii) O(n^2) : for finding pairs adding equal to A[i]
So total efficeincy is O(n^2)