A **Pythagorean triplet** is a set {a, b, c} such that $a^2 = b^2+ c^2$. The user is provided with an array of integers and has to identify all the possible sets of Pythagorean triplets.

# Algorithm

The naive approach here would be to run three nested `for` loops to try all possible triplets in an array. However, the complexity of such a solution would be $O(n^3)$.

Instead, we can solve the problem in $O(n^2)$ by sorting the array in ascending order, first.

The steps involved would be:

- Square every element in the input array and then sort it in ascending order.
- Since the array now contains squares, the new equation for triplet becomes $a = b + c$. Fix `a` to be the last element of this sorted array, since `a` will always have the largest value of the three numbers.
- Fix `b` as the first element of the sorted array and `c` as the element right before element `a`. Since numbers are positive and the array is sorted, $b < a$ and $c < a$. To find triplets, run a loop that increases `b` from $1$  to $n$, and decreases `c` from $n$ to $1$ at the same time until they meet. 
  1. Increase the position of `b` if $b + c < a$. 
  2. Decrease the position of `c` if $b + c > a$ . 
  3. If the sum is equal to `a`, then print the square root of the three numbers, increment `b`, and decrement `c`. 
  4. Repeat the last step for each element `a` in the array.

The following slides help us to visualize this algorithm:​

#include <algorithm> 
#include <iostream>   
#include <math.h> 
using namespace std; 

void findTriplet(int arr[], int n) 
{ 
  // Step 1
  for (int i = 0; i < n; i++) 
    arr[i] = arr[i] * arr[i]; 

  // Sort array elements 
  sort(arr, arr + n); 

  // Step 2 and Step 3 
  for (int i = n - 1; i >= 2; i--) {  // Fixing a
    int b = 0;    // Fixing b
    int c = i - 1;    // Fixing c
    while (b < c) { 
      // A triplet found 
      if (arr[b] + arr[c] == arr[i]){
        cout << "Triplet: "<< sqrt(arr[b]) <<", "<< sqrt(arr[c]) <<", "<< sqrt(arr[i])<<"\n"; 
        b++;
        c--;
      }

      // Else either move 'b' or 'c' 
      else if (arr[b] + arr[c] < arr[i]) {
        b++;
      }
      else { 
        c--; 
      }
    } 
  } 
} 
  
// Driver code
int main() 
{ 
  int arr[] = { 3, 1, 4, 6, 5 }; 
  int n = sizeof(arr) / sizeof(arr[0]); 
  findTriplet(arr, n);
  return 0; 
} 

import math  

def findTriplet(arr, n): 
  # Step1
  for i in range(n): 
    arr[i] = arr[i] * arr[i] 
  arr.sort() 

  # Step 2 and Step 3
  for i in range(n-1, 1, -1):   # fix a
    b = 0                       # fix b
    c = i - 1                   # fix c
    while (b < c): 
      if (arr[b] + arr[c] == arr[i]): 
        print("Triplet: ", math.sqrt(arr[b]),", ",math.sqrt(arr[c]),", ", math.sqrt(arr[i]))
        b+=1
        c-=1
      else: 
        if (arr[b] + arr[c] < arr[i]): 
          b = b + 1
        else: 
          c = c - 1

# Driver program to test above function */ 
arr = [3, 1, 4, 6, 5] 
n = len(arr) 
findTriplet(arr, n)

Python

import java.io.*; 
import java.util.*; 
import java.lang.Math; 
 
class PythagoreanTriplet { 
  static void findTriplet(int arr[], int n) 
  { 
    // Step1
    for (int i = 0; i < n; i++) 
      arr[i] = arr[i] * arr[i]; 
    Arrays.sort(arr); 

    // Step2 and Step 3
    for (int i = n - 1; i >= 2; i--) {  // Fix a
      int b = 0; // Fix b
      int c = i - 1; // Fix c
      while (b < c) { 
        // A triplet found 
        if (arr[b] + arr[c] == arr[i]) {
          System.out.printf("Triplets: %f, %f, %f\n", new Object[] {Math.sqrt(arr[b]), Math.sqrt(arr[c]), Math.sqrt(arr[i])});
          b++;
          c--;
        }
        if (arr[b] + arr[c] < arr[i]) 
          b++; 
        else
          c--; 
      } 
    } 
  } 

  // Driver code 
  public static void main(String[] args) 
  { 
    int arr[] = { 3, 1, 4, 6, 5 }; 
    int arr_size = arr.length; 
    findTriplet(arr, arr_size);
  } 
} 

Java

How to find Pythagorean triplets in an array

Identify Pythagorean triplets in an array by sorting, squaring elements, and using a two-pointer technique.

How to find Pythagorean triplets in an array

Algorithm

Code