# Find pythagorean triplets in an array faster than O(N^2)?

• Input : int[] array = {3,7, 2,24,12,1,5,6,4,9,13,10,25}

Expected Output with java toString :
[[3, 4, 5], [5, 12, 13], [7, 24, 25]]

``````List<List<Integer>> findPythagoreanTriplets(int[] array)  {
//implement function here
}``````

• I guess it's pretty hard to get the complexity better than O(n^2), take a look at geeksforgeeks and stackoverflow.

• Here is a algorithm I think in most case is better than O(n^2) algorithm, I write it in C++ as follow:

``````vector<vector<int> > pythagorean_triplets(vector<int> A) {
int n = A.size();
vector<vector<int> > ret;
if( n<=2 ) {
return ret;
}
sort(A.begin(), A.end());
unordered_map<int, bool> hash;
for(int i = 0; i < n; ++i) {
A[i] *= A[i]; // calculate square value for elements in A
hash[A[i]] = true; // hash to mark elements in A
}

int maxA = A[n-1];
int i = 0, j = n-1, k = 0;
while(i<=j) {
for(k=i+1; k<=j && A[k]+A[i]<=maxA; ++k ) {
if(hash[A[k]+A[i]]) {
vector<int> tmp(3,0);
tmp[0] = (int)sqrt(A[i]);
tmp[1] = (int)sqrt(A[k]);
tmp[2] = (int)sqrt(A[i]+A[k]);
ret.push_back(tmp);
}
}
++i;
j=k-1;
}
return ret;}
``````

the idea behind this is that: after you sort the array, say you get A' from A, if A[i] + A[j] > maxL, where i < j, then there is no necessary for you to do further check started from j for range i to j, which means:

firstly: for current loop, no need to check elements behind j

secondly: for loop i+1, no need to check elements behind j

so, just update new j in second loop, you will get a more tighter j.

I cannot prove this, but I believe this algorithm is faster than O(n^2) in average case, but for worst case, it will be O(n^2), worst case happens when maxL > square second largest element + square third largest element.

Moreover, the space complexity of algorithm could be improved from O(n)->O(1).

• Yes, there is another way to find pythagorean triples maybe less than O(N^2), which use O(K) where K is the total number of triples with c less than the maximum value of in the given array. While c = sqrt(a^2+b^2).
The solution is a modification of the code from here.
The key is to generate the triples in the order of sqrt(a^2+b^2).

``````public static List<int[]> findTriplets(int[] nums){
List<int[]> ret = new ArrayList<int[]>();
if (nums == null || nums.length <=2 ) return ret;
Set<Integer> set = new HashSet<>();
Set<Long> AB = new HashSet<Long>();
int max = Integer.MIN_VALUE;
for (int num: nums){
max = Math.max(max,num);
}
int a, b, c=0;
int a1, b1, c1;
int m = 2;
while (c < max){
for (int n=1; n<m; n++){
a = m*m - n*n;
b = 2*m*n;
c = m*m + n*n;
if (c > max) break;
if (a > b) {
int temp = a;
a= b;
b= temp;
}
long code = (long)a<<32 + (long)b;
if (! AB.contains(code) ) {
if (set.contains(a) && set.contains(b) && set.contains(c)) {
System.out.println(""+a+","+b+","+c);
}
for (int i=2; i*c <=max; i++) {
a1=a*i;
b1=b*i;
c1=c*i;
long code1 = (long)a1<<32 + (long)b1;
if (! AB.contains(code1) ) {
if (set.contains(a1) && set.contains(b1) && set.contains(c1)) {
System.out.println(""+a1+","+b1+","+c1);
}
} else break;
}
}
}
m++;
}
return ret;
}
``````

• Putting out a no-brainer python, if you don't care about O(n):

``````from itertools import combinations

sq_map = dict((num ** 2, num) for num in nums)
return [(sq_map[x], sq_map[y], sq_map[x+y]) for x,y in combinations(sq_map, 2) if x+y in sq_map.keys()]
``````

Now I should go look into an optimum solution...

• I would argue that we cannot do better than O(n^2) as this problem has a lower bound Big-Omega(n^2) so to do better we need more information about the data. Otherwise, we can build a case which where the algorithm will fail.

• int[] array = {3,7, 2,24,12,1,5,6,4,9,13,10,25}

It return duplicate List but can be fixed using Set.

``````List<List<Integer>> findPythagoreanTriplets(int[] input)  {

// Sort the Numbers

if(input == null){
return null;
}

Map<Integer,Integer> store = new HashMap<>();

List<List<Integer>> tripletsSuperList = new ArrayList<>();
//O(n)
for(int i=0; i< input.length ; i++) {
int temp = (int)Math.pow(input[i],2);
System.out.println(temp);
store.put(input[i], temp);
}

//O(n)
for(int i=0; i< input.length ; i++) {
Integer firstNumber = input[i];
Integer secondSqrt = null;
if(store.keySet().contains(firstNumber+1)) {
secondSqrt = store.get(firstNumber+1);
}

if(store.keySet().contains(firstNumber-1)) {
secondSqrt = store.get(firstNumber-1);
}

if(secondSqrt != null) {

Integer thirdNumberSqRt = Math.abs(store.get(firstNumber) - secondSqrt);
if(Math.sqrt(thirdNumberSqRt) == (int)Math.sqrt(thirdNumberSqRt) && store.get((int)Math.sqrt(thirdNumberSqRt)) != null){
List<Integer> tripletsSubList = new ArrayList<>();
}

}

}
return tripletsSuperList;
}``````

• From 3SUM

the current best known algorithm for 3SUM runs in O( n^2 / (log(n)/ log(log(n)) ) time