POTD Solutions | 3 Nov’ 23 | Pythagorean Triplet

POTD 3 November: Pythagorean Triplet

Given an array arr of n integers, write a function that returns true if there is a triplet (a, b, c) from the array (where a, b, and c are on different indexes) that satisfies a² + b² = c², otherwise return false.

Input: arr[] = {3, 1, 4, 6, 5} 
Output: True 
There is a Pythagorean triplet (3, 4, 5).

Input: arr[] = {10, 4, 6, 12, 5} 
Output: False 
There is no Pythagorean triplet. 

Pythagorean Triplet using Sorting:

A Pythagorean triplet is a set of three integers (a, b, c) such that a^2 + b^2 = c^2.

The idea is to squares the elements of the input array, sorts them, and then iterates through the array to find if there are three elements (i, l, r) such that i^2 = l^2 + r^2, where ‘i’ is the largest element and ‘l’ and ‘r’ are two other elements in the array. If such a triplet is found, the function returns true; otherwise, it returns false.

Step-by-step approach:

• Square each element of the input array.
• Sort the squared array in non-decreasing order.
• Iterate through the sorted array from the largest element to the smallest (starting from the end).
• For each current largest element ‘i‘, set two pointers, ‘l’ to the beginning of the array and ‘r’ to the end.
• While ‘l’ is less than ‘r’, check if the sum of the squared elements at ‘l’ and ‘r’ equals the squared element at ‘i’. If it does, return true because a Pythagorean triplet is found.
• If the sum is less than the squared element at ‘i’, increment ‘l’; otherwise, decrement ‘r’.
• If the loop completes without finding a Pythagorean triplet, return false because none was found in the array.

Illustration:

Below is the implementation of the above approach: 

C++

class Solution{
public:
    // Function to check if the
    // Pythagorean triplet exists or not
    bool checkTriplet(int arr[], int n) {
        // Square array elements
    for (int i = 0; i < n; i++)
        arr[i] = arr[i] * arr[i];
 
    // Sort array elements
    sort(arr, arr + n);
 
    // Now fix one element one by one and find the other two
    // elements
    for (int i = n - 1; i >= 2; i--) {
        // To find the other two elements, start two index
        // variables from two corners of the array and move
        // them toward each other
        int l = 0; // index of the first element in arr[0..i-1]
        int r = i - 1; // index of the last element in arr[0..i-1]
        while (l < r) {
            // A triplet found
            if (arr[l] + arr[r] == arr[i])
                return true;
 
            // Else either move 'l' or 'r'
            (arr[l] + arr[r] < arr[i]) ? l++ : r--;
        }
    }
 
    // If we reach here, then no triplet found
    return false;
    }
};

Java

class Solution {
    boolean checkTriplet(int[] arr, int n) {
         // Square array elements
        for (int i = 0; i < n; i++)
            arr[i] = arr[i] * arr[i];
 
        // Sort array elements
        Arrays.sort(arr);
 
        // Now fix one element one by one and find the other two
        // elements
        for (int i = n - 1; i >= 2; i--) {
            // To find the other two elements, start two index
            // variables from two corners of the array and move
            // them toward each other
            int l = 0; // index of the first element in arr[0..i-1]
            int r = i - 1; // index of the last element in arr[0..i-1]
            while (l < r) {
                // A triplet found
                if (arr[l] + arr[r] == arr[i])
                    return true;
 
                // Else either move 'l' or 'r'
                if (arr[l] + arr[r] < arr[i])
                    l++;
                else
                    r--;
            }
        }
 
        // If we reach here, then no triplet found
        return false;
    }
}

Python3

class Solution:

    def checkTriplet(self,arr, n):
       # Create a dictionary to store the square of each element as keys
        # and the corresponding original element as values.
        square_map = {i * i: i for i in arr}

        # Iterate through the square_map to find triplets with the sum of squares.
        for square1 in square_map:
            for square2 in square_map:
                # Calculate the sum of two squared values.
                sum_of_squares = square1 + square2

                # Check if the sum exists in the square_map, indicating the presence of a triplet.
                if sum_of_squares in square_map:
                    return True

        # If no triplet is found, return False.
        return False