Find a pythagorean triplet from an array

Problem Statement:
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 a² + b² = c². this formula is derived from Pythagoras theorem: “For every right angle triangle with side lengths a, b, and c=> a² + b² = c²“.

Solution:

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).

Facebook Comments