Pythagorean Triplet in an Array

Pythagorean Triplets

According to Pythagoras' theorem, if we add the squares of the perpendicular and the base of any right-angled triangle, their sum will be equal to its hypotenuse. Any Triplet (i.e., a group of 3 numbers) satisfying the Pythagoras theorem is known as a Pythagorean Triplet.

In simple words, if three numbers p, q, and r satisfy the relation p² + q² = r², they are said to be Pythagorean Triplets.

Now let's come to our problem statement.

Problem Statement

You are given an input array that stores n integers (a1, a2,..., an), and you need to find if the array contains a Pythagorean Triplet.

A Pythagorean Triplet in an array is said to be found if it contains three integers, p, q, and r, such that p² + q² = r². 

Before moving on to its solution, let us understand the problem first.

Explanation with Example

We will get an array of integers as input. We are supposed to write a function that returns true if there is a Pythagorean Triplet in an array. If the Pythagorean Triplet is not present in the array, then it should return false. It means that our function should return true if adding the squares of any two numbers in our array equals the square of the third one.

Now that you know the task let us look at its solutions. There are many ways to find a Pythagorean Triplet in an array. We will begin with the brute-force approach.

Brute-Force Approach

The naive approach to solving this problem is to run three nested loops. In this method, we will try to pick every possible Triplet that is present in the input array and see if it satisfies the condition of Pythagorean Triplets in an array. 

Algorithm

To find Pythagorean Triplets in an array using a brute-force approach, we will follow the following algorithm:

1. Run three nested loops to pick three elements, p, q, and r, from the input array.
    
2. If for any value of p, q, r,  the condition p² = q² + r² is satisfied, our function will return true.
    
3. Else our function will return false.

Implementation in C++

#include <iostream>

// C++ program to find Pythagorean Triplet in an array.
using namespace std;
bool pyTriplet(int a[], int size) {

  /* Example =>
   A = { 5, 2, 3, 4, 1 }
            ^  ^  ^
            i   j   k
   Initial positions of looping variables i, j and k
   */
   
  int p = 0, q = 0, r = 0;
  for (int i = 0; i < size - 2; i++) {
     for (int j = i + 1; j < size - 1; j++) {
        for (int k = j + 1; k < size; k++) {
        
           // Storing squares of each element of a Triplet                 
           p = a[i] * a[i];
           q = a[j] * a[j];
           r = a[k] * a[k];
           
           // Check the Pythagorean Triplet in an array
           if (p == q + r || q == p + r || r == p + q) {
           
              // Returns true if Pythagorean Triplet is found
              return true;
           }
        }
     }
  }
  
  // Function returns false if Pythagorean Triplet is not found
  return false;
}

// Main code
int main() {
  int size;
  bool isPy;
  cout << "Enter the size of array" << endl;
  cin >> size;
  cout << "Enter array elements" << endl;
  int a[size];
  for (int i = 0; i < size; i++) {
  
     // Initializing array.
     cin >> a[i];
   }
  isPy = pyTriplet(a, size);
  if (isPy) {
  
     // If pyTriplet returns true.
     cout << "Pythagorean Triplet Present" << endl;
  } 
  
  else {
  
     // If pyTriplet returns false.
     cout << "Pythagorean Triplet is not Present" << endl;
  }
  return 0;
}

Input

Enter the size of array 5
Enter array elements 5 7 12 13 14

Output

Implementation in Java

// Java program to find Pythagorean Triplet in an array
import java.io.*;
import java.util.*;

class Main {
  public static boolean pyTriplet(int a[], int size) {
     int p = 0, q = 0, r = 0;

     for (int i = 0; i < size - 2; i++) {

        for (int j = i + 1; j < size - 1; j++) {

           for (int k = j + 1; k < size; k++) {
              p = a[i] * a[i];
              q = a[j] * a[j];
              r = a[k] * a[k];
              if (p == q + r || q == p + r || r == p + q) {
              
                 // If Pythagorean Triplet is found.
                 return true;
              }
           }
        }
     }
     
     // If Pythagorean Triplet is not found.
     return false;
  }
  
  // Main code
  public static void main(String args[]) {
     int size;
     boolean isPy;
     Scanner sc = new Scanner(System.in);
     System.out.println("Enter the size of the array");
     size = sc.nextInt();
     int a[] = new int[size];
     System.out.println("Enter the elements of the array");
     for (int i = 0; i < size; i++) {
     
        // Populating the array.
        a[i] = sc.nextInt();
     }
     
     // Function call   
     isPy = pyTriplet(a, size);

     if (isPy) {
     
        // If function returns true.
        System.out.println("Pythagorean Triplet present");
     } 
     else {
     
        // If function returns false.
        System.out.println("Pythagorean Triplet not present");
     }
  }
}

Input

Enter the size of array 5
Enter array elements 5 7 12 13 14

Output

Also see, Morris Traversal for Inorder and  Rabin Karp Algorithm

Implementation in Python

# Python program to find pythagorean triplet in an array
def pyTriplet(a, size):
   for i in range(0, size - 2):

       for j in range(i + 1, size - 1):

           for k in range(j + 1, size):
               p = a[i] * a[i]
               q = a[j] * a[j]
               r = a[k] * a[k]
               if p == q + r or q == p + r or r == p + q:
                   # Return 1(true) if Pythagorean Triplet is found.
                   return 1
   # Return 0(false) if Pythagorean Triplet is not found.
   return 0

# Main code
a = []
size = int(input("Enter size of array "))
print("enter the elements of the array")

# Populating the array
for i in range(0, size):
   a_element = int(input())
   a.append(a_element)
   
# Function call
isPy = pyTriplet(a, size)
if isPy == 1:

   # If function returns 1
   print("Pythagorean Triplet Present")
else:

   # If function returns 0
   print("Pythagorean Triplet not Present")

Input

Enter the size of array 5
Enter array elements 5 7 12 13 14

Output

Complexity

Time Complexity

O(N³), where N is the number of elements in the array.

Reason: We have used three nested loops in this method. Each loop is executed until the looping variable reaches the size of the input array. The time complexity is thus O(N³). Here, n is equal to the size of the input array.

Space Complexity

O(1) is the Space complexity.

Reason: The space complexity remains O(1) since we are not using any extra space. 

Use of Sorting

We can also solve this problem by sorting the array first. We can reduce the time complexity of this task by sorting. 

Algorithm

1. Square each element of the input array ( a[ ] ).
    
2. Sort the squared array in ascending order.
    
3. To find a Pythagorean Triplet (p, q, r) where p = q + r, do the following:
   1. Fix ‘p' as the last element of your sorted array.
       
   2. Initialize ‘q’ as the first element and r as the second last (p-1) element of the sorted array.
       
   3. A Triplet is found if a[q] + a[r] = a[p]. 
       
   4. Otherwise, if a[q] + a[r] < a[p], increment q (i.e., q ++).
       
   5. Otherwise, if a[q] + a[r] > a[p], decrement r (i.e., r --).
       
   6. If you can not find a pair of q and r that satisfy the given condition for the current value of p, then move p one position back.
       
   7. Repeat steps b through f  until a Pythagorean Triplet is found or p reaches the second index.

Implementation in C++

#include <algorithm>
#include <iostream>
using namespace std;
bool pyTriplet(int a[], int size) {

   // Square each element modifying original array.
   for (int i = 0; i < size; i++) {
       a[i] = a[i] * a[i];
   }

   // Sorting
   sort(a, a + size);
   for (int i = size - 1; i >= 2; i--) {
       int low = 0;
       int high = i - 1;
       while (low < high) {
       
           // If Pythagorean Triplet is found.
           if (a[low] + a[high] == a[i]) {
               return true;
           }
           
           // Otherwise move either high or low.
           if (a[low] + a[high] < a[i]) {
               low++;
           }
           else {
               high--;
           }
       }
   }
   
   // If Pythagorean Triplet is not.
   return false;
}

// Main code
int main() {
   int size;
   bool isPy;

   cout << "Enter the size of array" << endl;
   cin >> size;
   cout << "Enter array elements" << endl;
   int a[size];
   for (int i = 0; i < size; i++) {
   
       // Initializing array
       cin >> a[i];
   }
   isPy = pyTriplet(a, size);
   if (isPy) {
   
       // If pyTriplet returns true.
       cout << "Pythagorean Triplet Present" << endl;
   }
   else{
   
       // If pyTriplet returns false
       cout << "Pythagorean Triplet is not Present" << endl;
   }
   return 0;
}

Input

Enter the size of array 6
Enter array elements 1 5 21 23 29

Output

Implementation in Java

// Java code to find Pythagorean Triplet in an array.
import java.io.*;
import java.util.*;

class Main {
   public static boolean pyTriplet(int a[], int size) {
   
       // Square each element of the array and updating the given array.
       for (int i = 0; i < size; i++) {
           a[i] = a[i] * a[i];
       }
       
       // Sorting
       Arrays.sort(a);
       
       /* Fix one element and find remaining two.
       This loop will start from the end of the array.*/
       for (int i = size - 1; i >= 2; i--) {
           
           // Index of first element.
           int low = 0;
           
           // Index of last element
           int high = i - 1;
           while (low < high) {
           
               // Return true if Pythagorean Triplet is found
               if (a[low] + a[high] == a[i]) {
                   return true;
               }
               
               // Otherwise move either high or low
               if (a[low] + a[high] < a[i]) {
                   low++;
               }
               else {
                   high--;
               }
           }
       }
       
       // Return false if Pythagorean Triplet is not found
       return false;
   }
   
   // Main code
   public static void main(String args[]) {
       int size;
       boolean isPy;
       Scanner sc = new Scanner(System.in);
       
       System.out.println("Enter the size of the array");
       size = sc.nextInt();
       int a[] = new int[size];
       System.out.println("Enter the elements of the array");
       
       for (int i = 0; i < size; i++) {
       
           // Populating the array
           a[i] = sc.nextInt();
       }
       
       // Function call   
       isPy = pyTriplet(a, size);
       if (isPy) {
       
           // If function returns true
           System.out.println("Pythagorean Triplet present");
       }
       else {
       
           // If function returns false
           System.out.println("Pythagorean Triplet not present");
       }
   }
}

Input

Enter the size of array 6
Enter array elements 1 5 21 6 23 19

Output

Implementation in Python

# Python implementation to find Pythagorean Triplet in an array
def pyTriplet(a, size):

   # Square array elements
   for i in range(size):
       a[i] = a[i] * a[i]
       
   # Sorting
   a.sort()
   for i in range(size - 1, 1, -1):
       low = 0
       high = i - 1
       while (low < high):
       
           # Pythagorean Triplet present
           if (a[low] + a[high] == a[i]):
               return 1
           else:
               if (a[low] + a[high] < a[i]):
                   low = low + 1
               else:
                   high = high - 1
                   
   # Pythagorean Triplet not found
   return 0
   
# Main code
a = []
size = int(input("Enter size of array "))
print("enter the elements of the array")

# Populating the array
for i in range(0, size):

   a_element = int(input())
   a.append(a_element)
   
# Function call
isPy = pyTriplet(a, size)
if isPy == 1:

   # If function returns 1.
   print("Pythagorean Triplet Present")
else:

   # If function returns 0.
   print("Pythagorean Triplet not Present")

Input

Enter the size of array 6
Enter array elements 1 5 21 6 23 29

Output

Complexity

Time complexity

O(N²), where N is the size of the array.

Reason: This method has an O(N²) time complexity. It is because we are using two nested loops.

Space Complexity

O(1) is the space complexity.

Reason: The space complexity remains O(1) since we are not using any extra space. 

Use of Hashing

One more solution to this problem is to use hashing. However, it will have little effect on the time complexity.

Algorithm

• Store each element in the hash array.
   
• We want to find three values p, q, and r such that p² + q² = r²
   
• Run a nested loop to test all possible p and q combinations, then check our hash array to see if the corresponding value of r is present or not.
   
• If r is found, there exists a Pythagorean Triplet in an array. Hence, return true. If r is not found, return false.

Implementation in C++

// C++ implementation to find Pythagorean Triplet in an array
#include <bits/stdc++.h>

using namespace std;

bool pyTriplet(int a[], int size) {
    int maxi = 0;

    for (int i = 0; i < size; i++) {
        maxi = max(maxi, a[i]);
    }

    int hash_array[maxi + 1] = {0};

    /* 
    	Increment the value of hash array where index = input array element
     */
    for (int i = 0; i < size; i++) {
        hash_array[a[i]]++;
    }
    
    // Looping for all p
    for (int i = 1; i < maxi + 1; i++) {

        if (hash_array[i] == 0) {
            continue;
        }
        
        // Looping for all possible q
        for (int j = 1; j < maxi + 1; j++) {

            if ((i == j && hash_array[i] == 1) || hash_array[j] == 0) {
                continue;
            }
            
            int r = sqrt(i * i + j * j);

            if ((r * r) != (i * i + j * j)) {
                continue;
            }
            
            if (r > maxi) {
                continue;
            }

            /* 
            	If r is present in original array, Pythagorean Triplet is found
            */
            if (hash_array[r]) {
                return true;
            }
        }
    }

    // Pythagorean Triplet not found
    return false;
}


// Main code
int main() {
    int size;
    bool isPy;
    cout << "Enter the size of array" << endl;
    cin >> size;
    cout << "Enter array elements" << endl;
    int a[size];


    for (int i = 0; i < size; i++) {

        // Initializing array
        cin >> a[i];
    }
    
    isPy = pyTriplet(a, size);

    if (isPy) {

        // If pyTriplet returns true
        cout << "Pythagorean Triplet Present" << endl;
    }
    else {

        // If pyTriplet returns false
        cout << "Pythagorean Triplet is not Present" << endl;
    }
    return 0;
}

Input

Enter the size of array 7
Enter array elements 1 3 5 7 4 7 19

Output

Implementation in Java

import java.util.*;
class Main {
   public static boolean pyTriplet(int a[], int size) {
       
       // Finding maximum element
       int maxi = 0;
       for (int i = 0; i < size; i++) {
           maxi = Math.max(maxi, a[i]);
       }
       
       // Hashing_array
       int hash_array[] = new int[maxi + 1];
       /* Increment the value of hash array
       Where index = input array element*/
       for (int i = 0; i < size; i++) {
           hash_array[a[i]]++;
       }
       
       // Looping for all p
       for (int i = 1; i < maxi + 1; i++) {
           if (hash_array[i] == 0) {
               continue;
           }
           
           // Looping for all q
           for (int j = 1; j < maxi + 1; j++) {
               if ((i == j && hash_array[i] == 1) || hash_array[j] == 0) {
                   continue;
               }
               
               // Finding r
               int r = (int) Math.sqrt(i * i + j * j);
               if ((r * r) != (i * i + j * j)) {
                   continue;
               }
               if (r > maxi) {
                   continue;
               }
               /* If r is present in original array, 
               Pythagorean Triplet is found*/
               if (hash_array[r] == 1) {
                   return true;
               }
           }
       }
      
        // Pythagorean Triplet not found
       return false;
   }
  
    // Main code
   public static void main(String args[]) {
       int size;
       boolean isPy;
       Scanner sc = new Scanner(System.in);
       
       System.out.println("Enter the size of the array");
       size = sc.nextInt();
       int a[] = new int[size];
       System.out.println("Enter the elements of the array");
       for (int i = 0; i < size; i++) {
          
            // Populating the array
           a[i] = sc.nextInt();
       }
       
       // Function call   
       isPy = pyTriplet(a, size);
       if (isPy) {
           
           // If function returns true
           System.out.println("Pythagorean Triplet present");
       }
       else {
          
            // If function returns false
           System.out.println("Pythagorean Triplet not present");
       }
   }
}

Input

Enter the size of the array 7
Enter array elements 1 3 5 7 4 7 19

Output

Implementation in Python

# Python code to find Pythagorean Triplet in an array
import math

def pyTriplet(a, size):
    maxi = 0

    # Maximum element from the array
    maxi = max(a)

    # Creating Hash array
    hash = [0] * (maxi + 1)

    for i in range(size):
        hash[a[i]] += 1

        # Looping for all p
    for i in range(1, maxi + 1):

        # If p is not present
        if hash[i] == 0:
            continue

        # Looping for all q
        for j in range(1, maxi + 1):

            if i == j and hash[i] == 1:

                # If p and q are equal and there exists only one p.
                continue
            if hash[j] == 0:

                # Or if q does not exist in the input array.
                continue

            # Finding r
            r = int(math.sqrt(i * i + j * j))

            # If r^2 isn't perfect square.
            if (r * r) != (i * i + j * j):
                continue

            # If r is more than maximum value.
            if r > maxi:
                continue

            # If r is in the original array, Triplet is found.
            if hash[r]:
                return True
    return False

# Main code
a = []
size = int(input("Enter size of array "))

print("enter the elements of the array")

# Populating the array
for i in range(0, size):
    a_element = int(input())
    a.append(a_element)

# Function call
isPy = pyTriplet(a, size)

if isPy == 1:

    # If function returns 1
    print("Pythagorean Triplet Present")
else:

    # If function returns 0
    print("Pythagorean Triplet not Present")

Input

Enter the size of array 7
Enter array elements 1 3 5 7 4 7 19

Output

Complexity

Time Complexity

O(maxi*maxi), where, the maxi is the maximum element of the array. 

Reason: This approach has a time complexity of O(maxi*maxi).  It is because we are using two nested loops.

Space Complexity

O(maxi),  where the maxi is the maximum element of the array.

Reason: Since we are using extra space equal to the maximum element, the space complexity becomes O(maxi).

Frequently Asked Questions

What is Hashing?

Hashing is a technique or process that uses a hash function to map pairs of keys and values into a hash table.

What is a Pythagorean Triplet?

Any three numbers that satisfy the Pythagoras theorem are called Pythagorean Triplets. If three numbers p, q, and r satisfy the relation p² + q² = r², they are said to be Pythagorean Triplets.

What is an array?

An array is a group of elements of a similar data type that are referenced by a common name.

What is time complexity?

The amount of time an algorithm or code takes to execute each instruction is known as its time complexity.

What is space complexity?

The total memory space used by an algorithm or a code, including the space of input values, is referred to as "space complexity."

Conclusion

We understood the problem of finding Pythagorean Triplets in an array. We also implemented the code in different languages.

We hope this article helps you on your journey. You can look at these array-related questions. It will help you understand arrays better!

• Best time to buy and sell stocks.
   
• Kth largest element in an array.
   
• Sum Of Two Arrays.
   
• Median of two sorted arrays.
   

Recommended problems -

• Maximum sum subarray of size k
• Max circular subarray sum
• Subarray sums divisible by k
• Shortest subarray with sum at least k

 

You can refer to our Guided Path on Coding Ninjas Studio to upskill yourself in Data Structures and Algorithms, Competitive Programming, System Design, and many more!

Head to our practice platform, Coding Ninjas Studio, to practice top problems, attempt mock tests, read interview experiences and interview bundles, follow guided paths for placement preparations, and much more!

Happy coding, Ninja!