Find Pythagorean Triplets from array

August 8, 2025

Find Pythagorean Triplets in C++

Find pythagorean Triplets from Array – Pythagorean triplets are set of three values which satisfy the pythagoras theorem of a right angled triangle. Pythagoras theorem states that the square of hypotenuse is equal to the sum of square of base and square of perpendicular. The values which satisfy the above condition are considered to be as pythagorean triplets.

In this blog, we’ll learn how to find Pythagorean triplets in a given array. These are special sets of numbers that satisfy the famous Pythagoras Theorem from geometry.

Introduction to stl

Find Pythagorean Triplets in C++

Find pythagorean Triplets from Array – Pythagorean triplets are set of three values which satisfy the pythagoras theorem of a right angled triangle. Pythagoras theorem states that the square of hypotenuse is equal to the sum of square of base and square of perpendicular. The values which satisfy the above condition are considered to be as pythagorean triplets.

In this blog, we’ll learn how to find Pythagorean triplets in a given array. These are special sets of numbers that satisfy the famous Pythagoras Theorem from geometry.

Introduction to stl

What is a Pythagorean Triplet?

A Pythagorean triplet consists of three numbers a, b, and c such that:

For example, (3, 4, 5) is a Pythagorean triplet because:

Segregate 0’s 1’s and 2’s in array

Sort elements in array by frequency

Reorder array using given indexes

Merging two sorted arrays

Minimum number of Merge Operations to make an Array Palindrome

Problem Statement and Methods used

Given an array of positive integers, check whether the array contains any Pythagorean triplet.

Method 1: Brute Force (Triple Nested Loop)

Approach:

  • Run three nested loops.
  • Check if for any triplet a, b, c, the condition a² + b² = c² holds.
#include<iostream>
using namespace std;

bool isTripletBrute(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        int a = arr[i] * arr[i];
        for (int j = i + 1; j < n; j++) {
            int b = arr[j] * arr[j];
            for (int k = j + 1; k < n; k++) {
                int c = arr[k] * arr[k];
                if (a + b == c || a + c == b || b + c == a)
                    return true;
            }
        }
    }
    return false;
}

int main() {
    int arr[] = {3, 1, 4, 6, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << (isTripletBrute(arr, n) ? "Yes" : "No") << endl;
    return 0;
}

Output:

Yes
  • Time Complexity: O(n³)
  • Space Complexity: O(1)

Method 2: Sorting + Two Pointer

Approach:

  1. Square all elements.
  2. Sort the array.
  3. Fix the largest element (as c²) and use two pointers to find if a pair exists with sum equal to c².

C++ Code:

#include<iostream>
#include<algorithm>
using namespace std;

bool isTripletEfficient(int arr[], int n) {
    for (int i = 0; i < n; i++) arr[i] = arr[i] * arr[i]; sort(arr, arr + n); for (int i = n - 1; i >= 2; i--) {
        int c = arr[i];
        int left = 0, right = i - 1;

        while (left < right) {
            if (arr[left] + arr[right] == c)
                return true;
            else if (arr[left] + arr[right] < c)
                left++;
            else
                right--;
        }
    }
    return false;
}

int main() {
    int arr[] = {10, 4, 6, 12, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << (isTripletEfficient(arr, n) ? "Yes" : "No") << endl;
    return 0;
}

Output:

Yes
  • Time Complexity: O(n²)
  • Space Complexity: O(1) (in-place sorting)

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get Prime

Method 3: Using Hashing

Approach:

  • Square all numbers and store in a hash set.
  • For every pair (a, b) in the array, check if (a² + b²) exists in the set.

C++ Code:

#include<iostream>
#include<unordered_set>
using namespace std;

bool isTripletHashing(int arr[], int n) {
    unordered_set squares;
    for (int i = 0; i < n; i++)
        squares.insert(arr[i] * arr[i]);

    for (int i = 0; i < n; i++) {
        int a = arr[i];
        for (int j = i + 1; j < n; j++) {
            int b = arr[j];
            int sum = a * a + b * b;
            if (squares.find(sum) != squares.end())
                return true;
        }
    }
    return false;
}

int main() {
    int arr[] = {8, 15, 17, 3, 4};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << (isTripletHashing(arr, n) ? "Yes" : "No") << endl;
    return 0;
}

Output:

Yes
  • Time Complexity: O(n²)
  • Space Complexity: O(n)

Conclusion:

Pythagorean triplet problems are a great mix of math and logic. While brute force gives you a starting point, sorting and hashing techniques help you optimize the solution and improve efficiency.

Learning different methods and understanding their trade-offs is key to cracking such DSA questions in interviews.

FAQs - Find Pythagorean Triplets from Array

To find all unique triplets, modify the Two Pointer or Hashing method:

  • Sort the array to avoid duplicates.
  • Store triplets in a set of tuples or a custom comparator.
  • Instead of returning true on the first match, collect all valid (a, b, c) triplets where a² + b² = c².

Squaring before sorting is valid because the relative order of squared values still allows us to apply the two-pointer technique. Since we’re only comparing sums of squares, actual a or b values are not required – just their squared forms.

Yes. One approach is to avoid storing all squared values up front. Instead:

  • Use a hash map to store frequency of values.
  • For each pair (a, b), check if sqrt(a² + b²) exists in the original array, taking care to avoid precision errors by verifying (int)√x * (int)√x == x.

Negative values can be ignored because only positive integers form valid Pythagorean triplets under classic definition. However, if asked:

  • Square all numbers (positive or negative) since squaring removes sign.
  • Then follow the regular two-pointer or hashing logic.

No, not for the general case. Since we must examine at least pairs of numbers to satisfy a² + b² = c², the problem has an inherent lower bound of O(n²) due to the pairwise comparisons. Any claim of linear time would either:

  • Impose unrealistic constraints, or
  • Only work for specialized inputs (like already sorted arrays with known patterns).

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Get Prime
Course List
Course List

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout list of all the video courses in PrepInsta Prime Subscription

Checkout
Checkout

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion : C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++ | Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
  • Find size of the Binary tree – C | C++ | Java
  • Find the height of binary tree – C | C++ | Java
  • Find maximum in binary tree – C | C++ | Java
  • Check whether two tree are identical- C| C++| Java
  • Spiral Order traversal of Tree- C | C++| Java
  • Level Order Traversal Line by Line – C | C++| Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- C| C++| Java
  • check whether tree is Symmetric – C| C++| Java.
  • Check for Children-Sum in Binary Tree- C|C++| Java
  • Sum of all nodes in Binary Tree- C | C++ | Java
  • Lowest Common Ancestor in Binary Tree- C | C++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

Traversals

  • Traversal in Trees
  • Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
  • Tree Traversals: Depth First Search (DFS) : C | C++ | Java
  • Construct a Binary Tree from Postorder and Inorder

B – Trees

AVL Trees

  • AVL Trees
    • AVL Trees: Introduction
    • AVL Tree Insertion :  C | C++ | Java
    • AVL Tree Deletion : C | C++ | Java
    • Insertion in a Binary Tree (Level Order) – C | C++ | Java
    • Searching in Binary Tree – C | C++ | Java
    • Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

  • Depth First Traversals – C | C++ | Java
  • Level Order Traversal – C | C++ | Java
  • Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
  • Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
  • Find size of the Binary tree – C | C++ | Java
  • Find the height of binary tree – C | C++ | Java
  • Find maximum in binary tree – C | C++ | Java
  • Check whether two tree are identical- C| C++| Java
  • Spiral Order traversal of Tree- C | C++| Java
  • Level Order Traversal LIne by Line – C | C++| Java
  • Hand shaking lemma and some Impotant Tree Properties.
  • Check If binary tree if Foldable or not.- C| C++| Java
  • check whether tree is Symmetric  C| C++| Java.
  • Check for Children-Sum in Binary Tree- C|C++| Java
  • Sum of all nodes in Binary Tree- C | C++ | Java
  • Lowest Common Ancestor in Binary Tree. C | C++ | Java