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

Question

Can someone suggest an algorithm that finds all Pythagorean triplets among numbers in a given array? If it's possible, please, suggest an algorithm faster than O(n²).

Pythagorean triplet is a set {a,b,c} such that a² = b² + c². Example: for array [9, 2, 3, 4, 8, 5, 6, 10] the output of the algorithm should be {3, 4, 5} and {6, 8, 10}.

Answer 1

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.

Answer 2

No one knows how to do significantly better than quadratic for the closely related 3SUM problem ( http://en.wikipedia.org/wiki/3SUM ). I'd rate the possibility of a fast solution to your problem as unlikely.

---

The 3SUM problem is finding a + b + c = 0. Let PYTHTRIP be the problem of finding a^2 + b^2 = c^2 when the inputs are real algebraic numbers. Here is the O(n log n)-time reduction from 3SUM to PYTHTRIP. As ShreevatsaR points out, this doesn't exclude the possibility of a number-theoretic trick (or a solution to 3SUM!).

First we reduce 3SUM to a problem I'll call 3SUM-ALT. In 3SUM-ALT, we want to find a + b = c where all array entries are nonnegative. The finishing reduction from 3SUM-ALT to PYTHTRIP is just taking square roots.

To solve 3SUM using 3SUM-ALT, first eliminate the possibility of triples where one of a, b, c is zero (O(n log n)). Now, any satisfying triple has two positive numbers and one negative, or two negative and one positive. Let w be a number greater than three times the absolute value of any input number. Solve two instances of 3SUM-ALT: one where all negative x are mapped to w - x and all positive x are mapped to 2w + x; one where all negative x are mapped to 2w - x and all positive x are mapped to w + x. The rest of the proof is straightforward.