Array Triplets with Pythagorean Property - Coding Interview
Interview Experience
Problem
Given an unsorted array of positive integers, count the number of triplets (a, b, c) (by index, i < j < k) such that a^2 + b^2 == c^2 (or any permutation: any of the three values can be the hypotenuse).
python
def count_pythagorean_triplets(nums: list[int]) -> int:
...
Example:
**Input**: [3, 4, 5, 6, 8, 10]
**Output**: 4
Explanation:
(3,4,5): 9+16=25 ✓
(3,5,4) same indices different order -- counted once per index triple.
(6,8,10): 36+64=100 ✓
(4,?,8)? 4^2=16, 8^2=64, 64-16=48, sqrt(48) not integer.
Work through to get exact count.
Constraints: 3 <= len(nums) <= 1000, values in [1, 1000].
Follow-ups
- A brute-force O(n^3)
solution works for n<=1000. How do you improve to O(n^2) using a hash set?
- How does your counting change if the problem asks for distinct value triplets (not index triplets)?
- What pre-processing step makes the O(n^2)
approach cleaner?
Full Details
Problem
Given an unsorted array of positive integers, count the number of triplets (a, b, c) (by index, i < j < k) such that a^2 + b^2 == c^2 (or any permutation: any of the three values can be the hypotenuse).
python
def count_pythagorean_triplets(nums: list[int]) -> int:
...
Example:
**Input**: [3, 4, 5, 6, 8, 10]
**Output**: 4
Explanation:
(3,4,5): 9+16=25 ✓
(3,5,4) same indices different order -- counted once per index triple.
(6,8,10): 36+64=100 ✓
(4,?,8)? 4^2=16, 8^2=64, 64-16=48, sqrt(48) not integer.
Work through to get exact count.
Constraints: 3 <= len(nums) <= 1000, values in [1, 1000].
Follow-ups
- A brute-force O(n^3)
solution works for n<=1000. How do you improve to O(n^2) using a hash set?
- How does your counting change if the problem asks for distinct value triplets (not index triplets)?
- What pre-processing step makes the O(n^2)
approach cleaner?
About This Question
This is a candidate experience report from a codesignal interview.
It covers the following topics: Q2, General Coding Assessment, Backtracking, Coding, Hash Table, Arrays .