08. Pythagorean Triplet

✅ GFG solution to the Pythagorean Triplet problem: determine whether three numbers in an array satisfy a² + b² = c² using hashing and mathematical observation. 🚀

The problem can be found at the following link: 🔗 Question Link

🧩 Problem Description

Given an array arr[], return true if there exists a triplet (a, b, c) from the array (where a, b, and c are at different indexes) that satisfies a² + b² = c², otherwise return false.

📘 Examples

Example 1

Input: arr[] = [3, 2, 4, 6, 5]
Output: true
Explanation: a=3, b=4, and c=5 forms a Pythagorean triplet.

Example 2

Input: arr[] = [3, 8, 5]
Output: false
Explanation: No such triplet possible.

Example 3

Input: arr[] = [1, 1, 1]
Output: false
Explanation: 1² + 1² = 2 ≠ 1², so no valid triplet exists.

🔒 Constraints

• $1 \le \text{arr.size()} \le 10^5$

• $1 \le \text{arr}[i] \le 10^3$

✅ My Approach

The optimal approach uses a Hash Set of Squares for O(1) existence lookup combined with a double-loop over all pairs:

Hash Set of Squares

1. Precompute Squares:

   • Insert the square of every element (x * x) into an unordered_set.

   • This enables O(1) average-case lookup for any target value.

2. Enumerate All Pairs:

   • Iterate over every pair (i, j) with i < j.

   • For each pair, compute the sum of squares: arr[i]² + arr[j]².

3. Check Existence:

   • If the computed sum exists in the set, then there is some element c in the array such that c² = arr[i]² + arr[j]², which means a valid Pythagorean triplet exists — return true.

4. Return Result:

   • If no such pair is found after checking all combinations, return false.

Key Insight: By storing squares (not values), we directly check the Pythagorean condition a² + b² = c² without needing to compute square roots, avoiding any floating-point precision issues.

📝 Time and Auxiliary Space Complexity

• Expected Time Complexity: O(n²), as we iterate over all pairs (i, j) with i < j, which results in approximately n*(n-1)/2 iterations, and each lookup in the hash set takes O(1) average time.

• Expected Auxiliary Space Complexity: O(n), as we store the square of each element in an unordered set of size at most n.

🧑‍💻 Code (C++)

class Solution {
  public:
    bool pythagoreanTriplet(vector<int>& arr) {
        unordered_set<int> s;
        for (int& x : arr) s.insert(x * x);
        for (int i = 0; i < arr.size(); ++i)
            for (int j = i + 1; j < arr.size(); ++j)
                if (s.count(arr[i]*arr[i] + arr[j]*arr[j])) return true;
        return false;
    }
};

⚡ View Alternative Approaches with Code and Analysis

📊 2️⃣ Frequency Array & Math (O(k²))

💡 Algorithm Steps:

1. Build a freq[1001] array to store the count of each value present in arr.

2. Collect all unique values (where freq[x] > 0) into a sorted list unique_nums.

3. For every pair (a, b) from unique_nums (with a ≤ b):

   • Compute c2 = a² + b² and c = round(√c2).

   • If c ≤ 1000, c² == c2, and freq[c] > 0:

     • Validate element distinctness using frequency counts (e.g., if a == b, need freq[a] ≥ 2; if all three are equal, need freq[a] ≥ 3).

     • Return true if valid.

4. Return false if no valid triplet is found.

class Solution {
  public:
    bool pythagoreanTriplet(vector<int>& arr) {
        int freq[1001] = {0};
        for (int x : arr) freq[x]++;
        vector<int> u;
        for (int i = 1; i <= 1000; ++i) if (freq[i]) u.push_back(i);
        int m = u.size();
        for (int i = 0; i < m; ++i) for (int j = i; j < m; ++j) {
            int a = u[i], b = u[j], c2 = a*a + b*b;
            int c = int(round(sqrt(c2)));
            if (c > 1000 || c*c != c2 || freq[c] == 0) continue;
            if (a == b && b == c && freq[a] >= 3) return true;
            if (a == b && freq[a] >= 2 && freq[c] >= 1 && c != a) return true;
            if (a == c && freq[a] >= 2 && freq[b] >= 1 && b != a) return true;
            if (b == c && freq[b] >= 2 && freq[a] >= 1 && a != b) return true;
            if (a != b && b != c && a != c) return true;
        }
        return false;
    }
};

📝 Complexity Analysis:

• Time: O(k²), where k ≤ 1000 unique values, giving at most ~10⁶ operations in the worst case.

• Auxiliary Space: O(1), as only a fixed-size array of 1001 elements is used regardless of input size.

✅ Why This Approach?

• Exploits the small value constraint (arr[i] ≤ 1000) for bounded iteration.

• Uses O(1) extra space — no dynamic data structures needed.

• Handles duplicate element edge cases precisely through frequency validation.

🆚 Comparison of Approaches

Approach	⏱️ Time	🗂️ Space	✅ Pros	⚠️ Cons
🔢 Hash Set of Squares	🟡 O(n²)	🟡 O(n)	Simple logic, clean code, O(1) lookups	Extra hash memory, n can be large
⚙️ Frequency Array & Math	🟢 O(k²)	🟢 O(1)	Constant extra space, leverages constraints	Only works when max(arr[i]) is small

✅ Best Choice by Scenario

Scenario	Recommended Approach
🏆 General input, straightforward implementation	🥇 Hash Set of Squares
🔧 Optimized for small value ranges with O(1) space	🥈 Frequency Array & Math

🧑‍💻 Code (Java)

class Solution {
    public boolean pythagoreanTriplet(int[] arr) {
        HashSet<Integer> squares = new HashSet<>();
        for (int x : arr) squares.add(x * x);
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            for (int j = i + 1; j < n; ++j)
                if (squares.contains(arr[i]*arr[i] + arr[j]*arr[j])) return true;
        return false;
    }
}

🐍 Code (Python)

class Solution:
    def pythagoreanTriplet(self, arr):
        s = set(x * x for x in arr)
        n = len(arr)
        for i in range(n):
            for j in range(i + 1, n):
                if arr[i]**2 + arr[j]**2 in s:
                    return True
        return False

🧠 Contribution and Support

For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!

⭐ If you find this helpful, please give this repository a star! ⭐

---

📍Visitor Count

Visitor counter