Given an array of integers, find Pythagorean triplets. i.e. find a,b and c which satisfies a^2 + b^2 = c^2. Integers could be positive or negative.

Problem:

 Given an array of integers, find Pythagorean triplets. i.e. find a,b and c which satisfies a^2 + b^2 = c^2. Integers could be positive or negative.

Solution:

To solve this problem in naive approach, we can simply run O(n^3) solution by iterating over all triplets and then checking if Pythagorean property is indeed satisfied.

Can we optimize the solution? Answer is yes!! If we make use of sorting technique then we can make it O(n^2 * log(n)). 

If we square all the elements (all storing actual elements along side and storing all duplicates as well) and then sort the array of squares of the elements. Then for each pair (O(n^2)) we just need to find if sum of the square of these values exist in sorted array. Here come our life saving handy technique Binary Search into play which will can find if element exists in array in O(log n) so overall complexity becomes

 O(n^2 * log(n)).

Can we still do better???? Answer is again YES!! We can!!

We can maintain hash map for squares of elements therefore searching part of above can be done in O(1) making overall complexity O(n^2). But this would depend on choice of very good hash function and also may not be allowed in most of problems.

Then what next??? We will still use same sorting technique but with different flavor. We will sort the elements in such a way that a[i] will be before a[j] if a[i]*a[i] is less than a[j]*a[j].

Something similar to -1, 1, 2, 3 ,-5, 5 ....

Note that this array is actually sorted in terms of squares of values.

For each element of this array, we can find pair such that a[i]*a[i] + a[j]*a[j] = a[k]*a[k], where K is current element. 

Finding a pair can be done in O(n). This is similar to problem of finding X + Y = K in any sorted array in O(n).

Complexity:

Sorting step: O(nlogn)

Finding triplet : O(n^2)

Overall complexity O(n^2)

Working Code for O(n^2) solution

 import java.util.Arrays;  
 import java.util.Comparator;  
 import java.util.Scanner;  
 public class FindTriplet {  
      public static void main(String[] args) {  
           Scanner s = new Scanner(System.in);  
           int n = s.nextInt();  
           Integer[] a = new Integer[n];  
           for (int i = 0; i < n; i++) {  
                a[i] = s.nextInt();  
           }  
           Arrays.sort(a, new SquareSorter());  
           for (int i = 0; i < n; i++) {  
                for (int j = 0, k = n - 1; j < k;) {  
                     if (j == i) {  
                          j++;  
                     } else if (k == i) {  
                          k--;  
                     } else {  
                          int lhs = a[j] * a[j] + a[k] * a[k];  
                          int rhs = a[i] * a[i];  
                          if (lhs == rhs) {  
                               System.out.println("[" + a[j] + "(" + j + ")," + a[k]  
                                         + "(" + k + ")," + a[i] + "(" + i + ")," + "]");  
                               j++;  
                               k--;  
                          } else if (lhs > rhs){  
                               k--;  
                          } else {  
                               j++;  
                          }  
                     }  
                }  
           }  
      }  
 }  
 class SquareSorter implements Comparator<Integer> {  
      @Override  
      public int compare(Integer o1, Integer o2) {  
           return o1 * o1 - o2 * o2;  
      }  
 }  

Test case

Input:

8

-3 6 7 3 4 -5 4 5

Output:

[-3(0),4(3),-5(4),]

[3(1),4(2),-5(4),]

[-3(0),4(3),5(5),]

[3(1),4(2),5(5),]