Pythagorean Triplet

JavaView on GFG

Time: O(n^2)

Space: O(1)

Intuition

Check if array contains a Pythagorean triplet (a^2 + b^2 = c^2). Square elements, sort, two-pointer.

Algorithm

1Square all elements and sort. For each c (largest), two pointers a=0, b=c-1.
2If a^2 + b^2 == c^2: true. If <: a++. If >: b--.

Common Pitfalls

•After squaring, problem reduces to: find triplet where largest = sum of other two. Standard two-pointer.

Pythagorean Triplet.java

Java

// Approach: Sort array, square all elements. For each largest element use two pointers to find a^2 + b^2 = c^2.
// Time: O(n^2) Space: O(1)
import java.util.*;

class Solution {
    boolean pythagoreanTriplet(int[] arr) {
        int n = arr.length;

        Set<Integer> set = new HashSet<>();

        for (int val : arr)
            set.add(val);

        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int a = arr[i];
                int b = arr[j];
                int c = (int) Math.sqrt(a * a + b * b);

                if (c * c == a * a + b * b && set.contains(c))
                    return true;
            }
        }

        return false;
    }
}

Was this solution helpful?