Problem

Given an array of integers, determine whether it contains a Pythagorean triplet. Recall that a Pythagorean triplet (a, b, c) is defined by the equation a^2 + b^2 = c^2.

Examples

Example 1

1
2
3

Input: [3, 4, 5, 6, 8]
Output: true
Explanation: The array contains the Pythagorean triplet (3, 4, 5) because 3^2 + 4^2 = 9 + 16 = 25 = 5^2.

Example 2

1
2
3

Input: [1, 2, 3]
Output: false
Explanation: No three numbers in the array satisfy the Pythagorean theorem. 1^2 + 2^2 = 5, which is not equal to 3^2 = 9.

Example 3

1
2
3

Input: [5, 3, 4, 6, 13, 12]
Output: true
Explanation: The array contains the Pythagorean triplet (5, 12, 13) because 5^2 + 12^2 = 25 + 144 = 169 = 13^2.

Example 4

1
2
3

Input: [1]
Output: false
Explanation: A single element cannot form a triplet.

Solution

Method 1 - Brute Force

Intuition

The simplest approach is to check all possible combinations of three numbers from the array and verify if they satisfy the Pythagorean theorem. For each triplet, we need to check if the sum of squares of two smaller numbers equals the square of the largest number.

Approach

  1. Iterate through all possible triplets using three nested loops
  2. For each triplet (a, b, c), sort them to identify the largest value
  3. Check if a^2 + b^2 = c^2 where c is the largest value
  4. Return true if any triplet satisfies the condition
  5. Return false if no valid triplet is found

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool hasPythagoreanTriplet(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return false;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    vector<int> triplet = {nums[i], nums[j], nums[k]};
                    sort(triplet.begin(), triplet.end());
                    
                    if (triplet[0] * triplet[0] + triplet[1] * triplet[1] == triplet[2] * triplet[2]) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

func hasPythagoreanTriplet(nums []int) bool {
    n := len(nums)
    if n < 3 {
        return false
    }
    
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            for k := j + 1; k < n; k++ {
                triplet := []int{nums[i], nums[j], nums[k]}
                sort.Ints(triplet)
                
                if triplet[0]*triplet[0] + triplet[1]*triplet[1] == triplet[2]*triplet[2] {
                    return true
                }
            }
        }
    }
    
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public boolean hasPythagoreanTriplet(int[] nums) {
        int n = nums.length;
        if (n < 3) return false;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    int[] triplet = {nums[i], nums[j], nums[k]};
                    Arrays.sort(triplet);
                    
                    if (triplet[0] * triplet[0] + triplet[1] * triplet[1] == triplet[2] * triplet[2]) {
                        return true;
                    }
                }
            }
        }
        
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution:
    def has_pythagorean_triplet(self, nums: List[int]) -> bool:
        n = len(nums)
        if n < 3:
            return False
        
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    triplet = sorted([nums[i], nums[j], nums[k]])
                    
                    if triplet[0]**2 + triplet[1]**2 == triplet[2]**2:
                        return True
        
        return False

Complexity

  • ⏰ Time complexity: O(n^3 log 3), where n is the length of the array. We check all possible triplets and sort each triplet of 3 elements
  • 🧺 Space complexity: O(1), only using constant extra space for temporary variables

Method 2 - Hash Set Optimization

Intuition

Instead of checking all triplets, we can optimize by fixing two numbers and checking if the third number (which would complete the Pythagorean triplet) exists in the array. We use a hash set for O(1) lookup.

Approach

  1. Store all numbers in a hash set for O(1) lookup
  2. Iterate through all pairs of numbers (a, b)
  3. Calculate what the third number c should be: c = sqrt(a^2 + b^2)
  4. Check if c is an integer and exists in the hash set
  5. Return true if such a triplet is found

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
public:
    bool hasPythagoreanTriplet(vector<int>& nums) {
        if (nums.size() < 3) return false;
        
        unordered_set<int> numSet(nums.begin(), nums.end());
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                int a = nums[i], b = nums[j];
                long long cSquared = (long long)a * a + (long long)b * b;
                int c = sqrt(cSquared);
                
                if ((long long)c * c == cSquared && numSet.count(c)) {
                    return true;
                }
            }
        }
        
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

func hasPythagoreanTriplet(nums []int) bool {
    if len(nums) < 3 {
        return false
    }
    
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }
    
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            a, b := nums[i], nums[j]
            cSquared := a*a + b*b
            c := int(math.Sqrt(float64(cSquared)))
            
            if c*c == cSquared && numSet[c] {
                return true
            }
        }
    }
    
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    public boolean hasPythagoreanTriplet(int[] nums) {
        if (nums.length < 3) return false;
        
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                int a = nums[i], b = nums[j];
                long cSquared = (long) a * a + (long) b * b;
                int c = (int) Math.sqrt(cSquared);
                
                if ((long) c * c == cSquared && numSet.contains(c)) {
                    return true;
                }
            }
        }
        
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def has_pythagorean_triplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        num_set = set(nums)
        
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                a, b = nums[i], nums[j]
                c_squared = a * a + b * b
                c = int(c_squared ** 0.5)
                
                if c * c == c_squared and c in num_set:
                    return True
        
        return False

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of the array. We check all pairs and do O(1) lookup in hash set
  • 🧺 Space complexity: O(n), for storing all numbers in the hash set

Method 3 - Sort and Two Pointers

Intuition

We can sort the array and for each potential hypotenuse (largest value), use two pointers to find if there exist two numbers whose squares sum to the hypotenuse’s square. This approach leverages the sorted order to efficiently search for the pair.

Approach

  1. Sort the array in ascending order
  2. Iterate from the largest element backwards (potential hypotenuse)
  3. For each hypotenuse candidate, use two pointers from the beginning to find a pair
  4. Use left and right pointers to check if left^2 + right^2 = hypotenuse^2
  5. Move pointers based on the comparison result

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    bool hasPythagoreanTriplet(vector<int>& nums) {
        if (nums.size() < 3) return false;
        
        sort(nums.begin(), nums.end());
        
        for (int i = nums.size() - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            long long target = (long long)nums[i] * nums[i];
            
            while (left < right) {
                long long sum = (long long)nums[left] * nums[left] + (long long)nums[right] * nums[right];
                
                if (sum == target) {
                    return true;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return false;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

func hasPythagoreanTriplet(nums []int) bool {
    if len(nums) < 3 {
        return false
    }
    
    sort.Ints(nums)
    
    for i := len(nums) - 1; i >= 2; i-- {
        left, right := 0, i-1
        target := nums[i] * nums[i]
        
        for left < right {
            sum := nums[left]*nums[left] + nums[right]*nums[right]
            
            if sum == target {
                return true
            } else if sum < target {
                left++
            } else {
                right--
            }
        }
    }
    
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public boolean hasPythagoreanTriplet(int[] nums) {
        if (nums.length < 3) return false;
        
        Arrays.sort(nums);
        
        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0, right = i - 1;
            long target = (long) nums[i] * nums[i];
            
            while (left < right) {
                long sum = (long) nums[left] * nums[left] + (long) nums[right] * nums[right];
                
                if (sum == target) {
                    return true;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def has_pythagorean_triplet(self, nums: List[int]) -> bool:
        if len(nums) < 3:
            return False
        
        nums.sort()
        
        for i in range(len(nums) - 1, 1, -1):
            left, right = 0, i - 1
            target = nums[i] * nums[i]
            
            while left < right:
                current_sum = nums[left] * nums[left] + nums[right] * nums[right]
                
                if current_sum == target:
                    return True
                elif current_sum < target:
                    left += 1
                else:
                    right -= 1
        
        return False

Complexity

  • ⏰ Time complexity: O(n^2), where n is the length of the array. Sorting takes O(n log n) and the two-pointer search takes O(n^2) in worst case
  • 🧺 Space complexity: O(1), only using constant extra space for pointers and variables