Searching: Get the Pythagorean Triplet in an array

Problem Statement:

You are given an array, you need to find Pythagorean triplet.

Pythagorean triplet = a^2 +b^2 = c^2

Example:

Input: arr[] = {3, 1, 4, 6, 5} 
Output: True

3^2 + 4^2 = 5^2

Solution 1: Brute force approach

Create a nested for loop and find the triplets.

Time Complexity: O(n^3)
Space Complexity: O(1)

Solution 2: Two pointers approach

Square each element in the array and sort it.

Now fix the largest element as the triplet c^2

THen use two pointers approach to find the other 2 elements.

Below are the conditions:

if sum = c^2 we got the solution

if sum < c^2 Move the left towards right

if sum > c^2 Move the right towards left

Time Complexity: O(n^2)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <math.h>

using namespace std;

bool solution_1 (vector<int> &arr) 
{

    int n = arr.size();

    for (int i = 0; i < n; i++) 
    {
        for (int j = i + 1; j < n; j++) 
        {
            for (int k = j + 1; k < n; k++) 
            {

                int x = arr[i] * arr[i];
                int y = arr[j] * arr[j];
                int z = arr[k] * arr[k];

                if (x == y + z || y == x + z || z == x + y)
                    return true;
            }
        }
    }

    return false;
}

bool solution_2 (vector<int> &arr) 
{
  	int n = arr.size();
  
    for (int i = 0; i < n; i++)
        arr[i] = arr[i] * arr[i];

    sort(arr.begin(), arr.end());

    for (int i = n - 1; i > 1; i--) 
    {

        int l = 0;
        int r = i - 1;
        while (l < r) 
        {

            if (arr[l] + arr[r] == arr[i])
                return true;

            if (arr[l] + arr[r] < arr[i])
                l++;
           	else 
             	r--;
        }
    }

    return false;
}



int main() 
{
    vector<int> arr = {3, 1, 4, 6, 5};
  	
  	if (solution_1(arr))
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	cout << endl;
  	if (solution_2(arr))
		cout << "Yes" << endl;
	else
		cout << "No" << endl;


    return 0;
}

Output

Yes
Yes