Teaching Kids Programming – Finding Pythagorean Triplets in Array using Two Pointer or Hash Set

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given a list of positive integers nums, return whether there exist integers a, b, and c such that a**2 + b**2 = c**2.

Constraints
0 ≤ n ≤ 1,000 where n is the length of nums
Example 1
Input
nums = [5, 1, 7, 4, 3]
Output
True
Explanation
3, 4, 5 are in the array and 3^2 + 4^2 = 5^2.

We can bruteforce with triplets (i, j, k) that will cost us O(N^3).

Sort and Two Pointer Algorithm to Find Pythagorean Triplets

If we sort the numbers (Pythagorean Numbers), that is going to take O(NLogN) time. We then can apply the two pointer algorithm after we pick the number c (largest side). As the array is sorted, we will be able to move a pointer depending on the comparison between a^2+b^2 and c^2. The overall complexity is dominated by O(N^2).

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def pythagoreanTriplets(self, nums):
        nums.sort(reverse=True)
        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            while j < k:
                if nums[j]**2+nums[k]**2==nums[i]**2:
                    return True
                elif nums[j]**2+nums[k]**2>nums[i]**2:
                    j += 1
                else:
                    k -= 1
        return False

class Solution:
    def pythagoreanTriplets(self, nums):
        nums.sort(reverse=True)
        for i in range(len(nums)):
            j, k = i + 1, len(nums) - 1
            while j < k:
                if nums[j]**2+nums[k]**2==nums[i]**2:
                    return True
                elif nums[j]**2+nums[k]**2>nums[i]**2:
                    j += 1
                else:
                    k -= 1
        return False

The space complexity is O(1) constant.

Using Hash Set to Find Pythagoreean Triplets in Array

If we store the c^2 in a hash set, and bruteforce for all pairs of (a and b), we then can quickly check if c^2 is in the hash set. This takes O(N^2) time and O(N) space.

1
2
3
4
5
6
7
8
9
10

class Solution:
    def pythagoreanTriplets(self, nums):
        d = set()
        for i in nums:
            d.add(i * i)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]**2+nums[j]**2 in d:
                    return True
        return False

class Solution:
    def pythagoreanTriplets(self, nums):
        d = set()
        for i in nums:
            d.add(i * i)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i]**2+nums[j]**2 in d:
                    return True
        return False

–EOF (The Ultimate Computing & Technology Blog) —