โ† Goldman Sachs questions

Find a Pythagorean triplet in an unsorted array

Filed under Goldman Sachs

Free read 1 of 3

Confirm 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

  1. Confirm if elements can be negative and if squaring them handles negative inputs correctly.

Solution

O(N^2) time, O(N) space

Python
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.