How to find pythagorean triplets in an array faster than O(N^2)?

I understand this question as

Given an array, find all such triplets i,j and k, such that a[i]² = a[j]²+a[k]²

The key idea of the solution is:

• Square each element. (This takes O(n) time). This will reduce the original task to "find three numbers in array, one of which is the sum of other two".

Now it you know how to solve such task in less than O(n²) time, use such algorithm. Out of my mind comes only the following O(n²) solution:

1. Sort the array in ascending order. This takes O(n log n).

2. Now consider each element a[i]. If a[i]=a[j]+a[k], then, since numbers are positive and array is now sorted, k<i and j<i.

   To find such indexes, run a loop that increases j from 1 to i, and decreases k from i to 0 at the same time, until they meet. Increase j if a[j]+a[k] < a[i], and decrease k if the sum is greater than a[i]. If the sum is equal, that's one of the answers, print it, and shift both indexes.

   This takes O(i) operations.

3. Repeat step 2 for each index i. This way you'll need totally O(n²) operations, which will be the final estimate.

Not sure if this is any better but you can compute them in time proportional to the maximum value in the list by just computing all possible triples less than or equal to it. The following Perl code does. The time complexity of the algorithm is proportional to the maximum value since the sum of inverse squares 1 + 1/2^2 + 1/3^3 .... is equal to Pi^2/6, a constant.

I just used the formula from the Wikipedia page for generating none unique triples.

my $list = [9, 2, 3, 4, 8, 5, 6, 10];
pythagoreanTriplets ($list);

sub pythagoreanTriplets
{
  my $list = $_[0];
  my %hash;
  my $max = 0;
  foreach my $value (@$list)
  {
    $hash{$value} = 1;
    $max = $value if ($value > $max);
  }
  my $sqrtMax = 1 + int sqrt $max;

  for (my $n = 1; $n <= $sqrtMax; $n++)
  {
    my $n2 = $n * $n;
    for (my $m = $n + 1; $m <= $sqrtMax; $m++)
    {
      my $m2 = $m * $m;
      my $maxK = 1 + int ($max / ($m2 + $n2));
      for (my $k = 1; $k <= $maxK; $k++)
      {
        my $a = $k * ($m2 - $n2);
        my $b = $k * (2 * $m * $n);
        my $c = $k * ($m2 + $n2);
        print "$a $b $c\n" if (exists ($hash{$a}) && exists ($hash{$b}) && exists ($hash{$c}));
      }
    }
  }
}

If (a, b, c) is a Pythagorean triple, then so is (ka, kb, kc) for any positive integer.

so simply find one value for a, b, and c and then you can calculate as many new ones as you want.

Pseudo code:

a = 3
b = 4
c = 5
for k in 1..N:
  P[k] = (ka, kb, kc)

Let me know if this is not exactly what you're looking for.

Take a look at the following code that I wrote.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

bool existTriplet(vector<ll> &vec)
{
    for(auto i = 0; i < vec.size(); i++)
    {
        vec[i] =  vec[i] * vec[i]; //Square all the array elements
    }

    sort(vec.begin(), vec.end()); //Sort it
    for(auto i = vec.size() - 1; i >= 2; i--)
    {
        ll l = 0;
        ll r = i - 1;
        while(l < r)
        {
            if(vec[l] + vec[r] == vec[i])
                return true;

            vec[l] + vec[r] < vec[i] ? l++ : r--;
        }
    }
    return false;
}
int main() {
    int T;
    cin >> T;
    while(T--)
    {
        ll n;
        cin >> n;
        vector<ll> vec(n);
        for(auto i = 0; i < n; i++)
        {
            cin >> vec[i];
        }
        if(existTriplet(vec))
            cout << "Yes";
        else
            cout << "No";
        cout << endl;
    }
    return 0;
}

Plato's formula for Pythagorean Triples: Plato, a Greek Philosopher, came up with a great formula for finding Pythagorean triples.

(2m)^2 + (m^2 - 1)^2 = (m^2 + 1)^2

bool checkperfectSquare(int num){
    int sq=(int)round(sqrt(num));
    if(sq==num/sq){
        return true;
    }
    else{
        return false;
    }
}

void solve(){
    int i,j,k,n;

    // lenth of array
    cin>>n;
    int ar[n];
    // reading all the number in array
    for(i=0;i<n;i++){
        cin>>ar[i];
     }
    // sort the array
    sort(ar,ar+n);
    for(i=0;i<n;i++){
        if(ar[i]<=2){
            continue;
        }
        else{
            int tmp1=ar[i]+1;
            int m;
            if(checkperfectSquare(tmp1)){
                m=(ll)round(sqrt(tmp1));
                int b=2*m,c=(m*m)+1;
                if(binary_search(ar,ar+n,b)&&binary_search(ar,ar+n,c)){
                    cout<<ar[i]<<" "<<b<<" "<<c<<endl;
                    break;
                }
            }
            if(ar[i]%2==0){
                m=ar[i]/2;
                int b=(m*m-1),c=(m*m+1);
                if(binary_search(ar,ar+n,b)&&binary_search(ar,ar+n,c)){
                    cout<<ar[i]<<" "<<b<<" "<<c<<endl;
                    break;
                }
            }
        }
    }
}