Find a Pythagorean triplet in an unsorted array
Filed under Goldman Sachs
Free read 1 of 3Confirm if elements can be negative and if squaring them handles negative inputs correctly.
The question
Given an unsorted array of integers, determine if there exist three elements a, b, and c such that a^2 + b^2 = c^2.
Constraints
- Array length is between 3 and 5000.
- Elements can be positive or negative integers.
- Return true if such a triplet exists, false otherwise.
Examples
- Input
- nums = [3, 1, 4, 6, 5]
- Output
- true
- Why
- 3^2 + 4^2 = 5^2, so a Pythagorean triplet exists.
Approach
Confirm if elements can be negative and if squaring them handles negative inputs correctly.
Check every possible combination of three elements using three nested loops, running in O(n^3) time.
Square all elements, sort the array in O(n log n) time, then use a two-pointer approach similar to 3Sum to find if a[i] + a[j] == a[k] in O(n^2) total time.
Array with fewer than 3 elements, all zeros, or large numbers leading to overflow in languages without arbitrary-precision integers.
Solution
O(N^2) time, O(N) space
def checkPythagoreanTriplet(nums):
squared = [x * x for x in nums]
squared.sort()
n = len(squared)
for k in range(n - 1, 1, -1):
i, j = 0, k - 1
while i < j:
current_sum = squared[i] + squared[j]
if current_sum == squared[k]:
return True
elif current_sum < squared[k]:
i += 1
else:
j -= 1
return False
Tips
- What they are testing: Test with arrays lacking triplets, arrays with negative numbers, and arrays with duplicate values.
- Common mistake: Using a naive O(n^3) nested loop approach without squaring and sorting first.
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.