Katkat
Back

Detect a Pythagorean Triple in an Integer Array

ByteDanceSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests the ability to optimize a brute-force approach into an efficient search using sorting and the two-pointer technique to satisfy a geometric condition.

Problem Statement

Given an integer array nums, determine if there exist three distinct indices i, j, and k such that the squares of the values at these indices form a Pythagorean triple. Specifically, if we let a = nums[i]^2, b = nums[j]^2, and c = nums[k]^2, you must return true if a + b = c, a + c = b, or b + c = a holds true.

Function Signature

def has_pythagorean_triple(nums: List[int]) -> bool:

Constraints

  • 3 <= len(nums) <= 1000
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1: Input: nums = [3, 1, 4, 6, 5] Output: true Explanation: 3^2 + 4^2 = 9 + 16 = 25 = 5^2. Indices (0, 2, 4) satisfy the condition.

Example 2: Input: nums = [0, 0, 0] Output: true Explanation: 0^2 + 0^2 = 0^2.

Edge Cases

  • The array may contain zeros, negative numbers, or duplicates.
  • Since the condition is based on squares, nums[i] and -nums[i] are treated as having the same magnitude.
  • The indices must be distinct, but the values squared do not necessarily need to be unique.

Hints

Hint 1

Transform the problem by squaring every element in the input array first.

Hint 2

Sort the transformed array of squared values to simplify the search for `a + b = c`.

Hint 3

For each element at index `k` in the sorted array, treat it as the potential largest value `c` and use a two-pointer approach to find if any two smaller elements sum to it.

Follow-up questions

  • How does your algorithm change if the input array size increases to 10^6?
  • What is the time and space complexity of your solution, and can you optimize the space complexity to O(1) beyond sorting?
  • How would you handle the requirement if the values were extremely large integers, potentially causing overflow when squared?