Given two arrays of integers nums1 and nums2, return the number of triplets formed (type 1 and type 2) under the following rules:
nums1[i]2 == nums2[j] * nums2[k] where 0 <= i < nums1.length and 0 <= j < k < nums2.length.nums2[i]2 == nums1[j] * nums1[k] where 0 <= i < nums2.length and 0 <= j < k < nums1.length.Example 1:
Input: nums1 = [7,4], nums2 = [5,2,8,9] Output: 1 Explanation: Type 1: (1, 1, 2), nums1[1]2 = nums2[1] * nums2[2]. (42 = 2 * 8).
Example 2:
Input: nums1 = [1,1], nums2 = [1,1,1] Output: 9 Explanation: All Triplets are valid, because 12 = 1 * 1. Type 1: (0,0,1), (0,0,2), (0,1,2), (1,0,1), (1,0,2), (1,1,2). nums1[i]2 = nums2[j] * nums2[k]. Type 2: (0,0,1), (1,0,1), (2,0,1). nums2[i]2 = nums1[j] * nums1[k].
Example 3:
Input: nums1 = [7,7,8,3], nums2 = [1,2,9,7] Output: 2 Explanation: There are 2 valid triplets. Type 1: (3,0,2). nums1[3]2 = nums2[0] * nums2[2]. Type 2: (3,0,1). nums2[3]2 = nums1[0] * nums1[1].
Constraints:
1 <= nums1.length, nums2.length <= 10001 <= nums1[i], nums2[i] <= 105In #1577 Number of Ways Where Square of Number Is Equal to Product of Two Numbers, the goal is to count triplets where the square of a number in one array equals the product of two numbers in the other array. The problem is symmetric, meaning we must evaluate both directions: squares from nums1 against pairs in nums2, and vice versa.
A common strategy uses a hash table to track frequencies while iterating through pairs. For each element x in one array, compute x * x. Then scan the other array and check if the current value can form a valid pair whose product equals this square. Using a frequency map allows efficient counting of complements.
Another practical approach is to sort the arrays and apply a two‑pointer technique to count pair products that match the square target. This avoids checking every combination explicitly.
These approaches significantly reduce redundant computations compared to brute force. The optimized solutions typically run in around O(n² + m²) time with O(n) auxiliary space depending on the implementation.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Hash Map Frequency Counting | O(n^2 + m^2) | O(n) |
| Sorting + Two Pointers | O(n log n + m log m + n^2 + m^2) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Precalculate the frequencies of all nums1[i]^2 and nums2[i]^2
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Yes, if the arrays are sorted, a two-pointer approach can be used to find pairs whose product matches a target square. This method works well when handling duplicates and can reduce unnecessary pair checks.
Yes, this type of problem is common in coding interviews because it tests understanding of hash maps, pair counting, and mathematical reasoning. Variations of pair-product and triplet-count problems appear frequently in technical interviews.
A hash table is the most useful data structure for this problem because it allows fast lookup of previously seen values. It helps count valid pairs whose product matches a squared value while iterating through the array.
A common optimal approach uses a hash map to count pair products efficiently. For each element, compute its square and then scan the other array while checking complements using the map. This avoids brute force triplet checks and significantly reduces redundant work.