Pythagorean Triplet in an array

Back to home

𝑻𝒂𝒃𝒍𝒆 𝒐𝒇 𝑪𝒐𝒏𝒕𝒆𝒏𝒕

Problem Statement: Pythagorean Triplet in an array
Approach: Using Hashing

Logicmojo - Updated Aug 28, 2021

Problem Statement: Pythagorean Triplet in an array

Given an array of integers, write a function that returns true if there is a triplet (a, b, c) that satisfies a² + b² = c².

Example: arr = [3, 1, 4, 6, 5]

Output: True, There is a Pythagorean triplet (3, 4, 5).

Approach 1: Brute Force

A simple solution is to run three loops, three loops pick three array elements, and check if the current three elements form a Pythagorean Triplet. Time complexity will be O(n³) i.e. not the optimal one so we need to optimise it.

Efficient: Using Hashing

The problem can also be solved using hashing. We can use a hash map to mark all the values of the given array. Using two loops, we can iterate for all the possible combinations of a and b, and then check if there exists the third value c. If there exists any such value , then there is a Pythagorean triplet.

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

bool checkTriplet(int arr[], int n)
{
	int maximum = 0;

	
	for (int i = 0; i < n; i++) {
		maximum = max(maximum, arr[i]);
	}

	
	int hash[maximum + 1] = { 0 };

	
	for (int i = 0; i < n; i++)
		hash[arr[i]]++;

	
	for (int i = 1; i < maximum + 1; i++) {

		
		if (hash[i] == 0)
			continue;

		
		for (int j = 1; j < maximum + 1; j++) {

			
			if ((i == j && hash[i] == 1) || hash[j] == 0)
				continue;

			
			int val = sqrt(i * i + j * j);

			// If c^2 is not a perfect square
			if ((val * val) != (i * i + j * j))
				continue;

			
			if (val > maximum)
				continue;

			
			
			if (hash[val]) {
				return true;
			}
		}
	}
	return false;
}
// Driver Code
int main()
{
	int arr[] = { 3, 2, 4, 6, 5 };
	int n = sizeof(arr) / sizeof(arr[0]);
	if (checkTriplet(arr, n))
		cout << "Yes";
	else
		cout << "No";
}

Python Implementation:

# Pythagorean triplet exists or not
import math

def checkTriplet(arr, n):
	maximum = 0

	# Find the maximum element
	maximum = max(arr)

		# Hashing array
	hash = [0]*(maximum+1)

	# Increase the count of array elements
	# in hash table
	for i in range(n):
		hash[arr[i]] += 1

		# Iterate for all possible a
	for i in range(1, maximum+1):
		# If a is not there
		if (hash[i] == 0):
			continue

		# Iterate for all possible b
		for j in range(1, maximum+1):
			# If a and b are same and there is only one a
			# or if there is no b in original array
			if ((i == j and hash[i] == 1) or hash[j] == 0):
				continue

			# Find c
			val = int(math.sqrt(i * i + j * j))

			# If c^2 is not a perfect square
			if ((val * val) != (i * i + j * j)):
				continue

			# If c exceeds the maximum value
			if (val > maximum):
				continue

			# If there exists c in the original array,
			# we have the triplet
			if (hash[val]):
				return True
	return False


# Driver Code
arr = [3, 2, 4, 6, 5]
n = len(arr)
if (checkTriplet(arr, n)):
	print("Yes")
else:
	print("No")

Time complexity: O( max * max ), where max is the maximum most element in the array.

Space complexity: O(n) for storing values

With this article at Logicmojo, you must have the complete idea of solving Pythagorean Triplet in an array problem.