Watch 8 video solutions for Number of Ways Where Square of Number Is Equal to Product of Two Numbers, a medium level problem involving Array, Hash Table, Math. This walkthrough by Fraz has 1,497 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 105Problem Overview: You are given two arrays nums1 and nums2. Count triplets where the square of a number from one array equals the product of two numbers from the other array. Both directions count: nums1[i]^2 = nums2[j] * nums2[k] and nums2[i]^2 = nums1[j] * nums1[k] with j < k.
Approach 1: Brute Force Enumeration (O(n * m^2) time, O(1) space)
For every element in one array, compute its square and check all pairs in the other array. Use two nested loops to generate every pair (j, k) and compare their product with the square. Repeat the same process with arrays swapped to capture the second condition. This approach directly follows the problem definition and is useful for validating correctness on small inputs. However, triple nested iteration quickly becomes expensive when array sizes grow.
Approach 2: Optimized Hash Map Pair Counting (O(n^2) time, O(n) space)
The key observation: instead of recomputing all pair products repeatedly, track factors using a frequency map. For each element x in one array, compute target = x * x. Then iterate through the other array and check whether a previously seen number forms a valid pair: if target % num == 0, look up target / num in a hash map. This counts how many earlier numbers complete the product. After processing each number, store it in the map for future matches. Repeat the process with the arrays swapped to capture both triplet types. Hash lookups make pair detection constant time.
This technique is a common pattern in hash table problems where you convert pair comparisons into complement lookups. The arrays themselves are processed sequentially using standard array iteration, while arithmetic checks come from basic math reasoning about factors.
Recommended for interviews: The optimized hash map approach. The brute force method shows you understand the triplet condition, but the O(n^2) hash-based counting demonstrates awareness of factor matching and frequency tracking. Interviewers usually expect the optimized version once constraints suggest that cubic enumeration is too slow.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n * m^2) | O(1) | Useful for understanding the condition or when input sizes are very small |
| Hash Map Pair Counting | O(n^2) | O(n) | General case; reduces repeated pair checks using constant-time hash lookups |