Given an array a of n integers find all possible Pythagorean triplets from the array.
What is Pythagorean triplet?
A Pythagorean triple consists of three positive integers a, b, and c, such that a2 + b2 = c2. this formula is derived from Pythagoras theorem: “For every right angle triangle with side lengths a, b, and c=> a2 + b2 = c2“.
Conceptually it is similar to Find Non duplicate pairs that sum to S and 3 SUM problem
First sort the array, then square each number, now for every element a[i] in the array find if a pair exist with sum as a[i], this can be done in O(n) and we have to do it for every i, so the complexity will be O(n^2).
Sort the array in O(N)