# Find the Pythagorean triplets in an array

## Problem

You are given an integer array. Find all the Pythagorean triplets in this array. Pythagorean triplets are 3 numbers a, b, c such that a^2+b^2=c^2.

## Solution

First we store all the squares of the numbers in a hash set. Then in O(n^2) we try with all the combinations (a,b) and search a^2+b^2 in the hash set. If it exists then we have found a pythagorean triplet. The complexity is O(n^2) as compared to brute force of O(n^3).

## Code

package com.dsalgo; import java.util.HashSet; public class PythagoreanTriplet { public static void main(String[] args) { int[] arr = { 2, 3, 4, 6, 7, 12, 13, 15, 5, 17, 14, 22 }; findPythagoreanTriplets(arr); } private static void findPythagoreanTriplets(int[] arr) { HashSetsquares = new HashSet (); for (int num : arr) squares.add((long) num * num); for (int i = 0; i < arr.length - 1; ++i) for (int j = i + 1; j < arr.length; ++j) { long square = (long) arr[i] * arr[i] + (long) arr[j] * arr[j]; if (squares.contains(square)) { System.out.println(arr[i] + "," + arr[j] + "," + (long) Math.sqrt(square)); } } } }