Finding Pythagorean Triples

Given a set 'S' of 'N' numbers, find all x, y and z such that x^2 + y^2 = z^2.

One method:

1. I can store the z^2's in a hashmap (put every number squared ^2 into a hashmap). I can do this in time=N with additional space (the hashmap) of N elements.

2. I can then create a nested loop and multiple every number 'i' by every other number 'j' - looking for the result in the hashmap. That'd be N^2 time.

Am I overlooking a "better" way to do this?

And one more question, what particular class or category of algorithms does this problem fall into?

I can leverage HashMap properties to lookup answers but looking for other structures that would help improve this case.

Thanks in advance

In this specific case you can't do better than N^2, because at the least you need to sum N^2 different pairs:

Code:

---

Number of different pairs out of N numbers = N over 2 =  N!/(2!*(N-2)!)  =  (N-1)*N/2 = O(N^2)

---

But it is possible to dismiss the hash table and remain with O(N^2).

Regards,
Zachm

Ah - I see. Indeed, this is a Combination. The math helps. No better than N^2.

So, if I were to sort the array first, I'd add n lg n but that would still be < O(N^2). That means that on average, I would only have to look at value larger than the largest value I multiplied - but it doesn't seem right to me. Although it'd be shrinking as I moved up the indexes, I'm still walking some variable steps to the right on every iteration .... which, while it may likely avg out to be n/2 steps on each iteration which ... would still bring us to O(N^3)

The hashmap gives me O(1) lookup ... I'm not sure how else I can get that. I must be thinking of it wrong. I'm thinking that I must find a needle in a haystack and either I read all the needles first and save them into a hashmap or I iterate "over the rest of the needles" to find the correct value on each iteration.

Without actually giving it away, can you nudge me with an analogy or something? A hint at some property I am ignoring maybe? What other kind of problem is this like?

Thanks.

Try to keep it simple.
- Can you iterate over the pair sums in increasing order ?
- Can you iterate over the original number squares in increasing order ?
- Can you "combine" both iterations described above ?

Regards,
Zachm

Ok - I think I've got it now.

Sort the integers into an array A and then initialize indexes i, j and k with the notion that A[i]^2 + A[j]^2 = A[k]^2.

Furthermore, i represents the outer loop while j represents the inner loop. For each outer loop increment, the inner loop starts j over at i+1 and k over at j+1.

As I multiple A[i] and A[j], I search for the hypotenuse with A[k]. It should be noted that k never moves backward. The integers at i and j get progressively larger such that, at a minimum, k will move forward one position for each inner loop iteration. In the slowest case, k always ends up at j+1 where A[j+1]^2 > A[i]^2 + A[j]^2.

Another way to say this ... since the array is sorted, A[i]^2 + A[j]^2 are only getting larger and so A[k] is either on the correct integer or must move forward some number of steps until it finds the integer or steps one position greater than it.

I believe that the cost of actually moving 'k' the max of N-j steps on each round averages out to a constant with respect to N.

So, search = O(nlgn) and then iterate with nested loops O(n^2) including incrementing i, j and k indexes that all move forward only (except for when the outer loop increments in which case they start over at just above the ith index). Indeed, it turns out to be O(n^2).

This was actually my very very first idea - but I didn't appreciate that k didn't have to keep starting over at j+1 on each check for hypotenuse. I originally posited a third nested loop to walk through all of the integers looking for the value at k and since said approach is O(n^3) ... I just went the opposite way looking for a better solution - thus, the HashMap.

Hopefully ... this is what you were thinking. If not ... I need to continue searching. Many many thanks for your assistance.