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.
This approach involves iterating through each element in one array, computing its square, and then iterating through all possible product pairs in the other array to check for matches. Although simple to understand, this approach is not optimal due to its O(n^3) complexity.
The function count_triplets computes the number of valid triplets for one type, given two lists. It computes the square of each element in arr1 and then iterates through all pairs in arr2 to find matching products. The final count is the sum of Type 1 and Type 2 triplets.
The time complexity is O(n^3), due to the triple loop. The space complexity is O(1), aside from input storage.
This approach improves efficiency by using hash maps (or dictionaries) to precompute the frequency of products. For each square in the first array, it checks the hash map for potential matching products in the second array, offering a much faster solution with O(n^2) complexity.
The count_triplets_via_map function first precomputes the frequency of all unique products in the second array. It then iterates through the first array and checks how many of its squares are present in the product hashmap, summing the counts of valid products.
The time complexity is O(n^2) because of the double nested loop for generating products and using a hash map lookup. The space complexity is O(n^2) due to storing products in a hash map.
We use a hash table cnt1 to count the occurrences of each pair (nums[j], nums[k]) in nums1, where 0 leq j < k < m, and m is the length of the array nums1. Similarly, we use a hash table cnt2 to count the occurrences of each pair (nums[j], nums[k]) in nums2, where 0 leq j < k < n, and n is the length of the array nums2.
Next, we enumerate each number x in the array nums1 and calculate the value of cnt2[x^2], which is the number of pairs (nums[j], nums[k]) in nums2 that satisfy nums[j] times nums[k] = x^2. Similarly, we enumerate each number x in the array nums2 and calculate the value of cnt1[x^2], which is the number of pairs (nums[j], nums[k]) in nums1 that satisfy nums[j] times nums[k] = x^2. Finally, we return the sum of the two results.
The time complexity is O(m^2 + n^2 + m + n), and the space complexity is O(m^2 + n^2). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.
Python
Java
C++
Go
TypeScript
We use a hash table cnt1 to count the occurrences of each number in nums1, and a hash table cnt2 to count the occurrences of each number in nums2.
Next, we enumerate each number x in the array nums1, and then enumerate each pair (y, v1) in cnt2, where y is the key of cnt2 and v1 is the value of cnt2. We calculate z = x^2 / y. If y times z = x^2, and if y = z, it means y and z are the same number, then the number of ways to choose two numbers from v1 is v1 times (v1 - 1) = v1 times (v2 - 1). If y neq z, then the number of ways to choose two numbers from v1 is v1 times v2. Finally, we sum all the ways and divide by 2. The division by 2 is because we count the number of ways for the pair (j, k), but (j, k) and (k, j) are the same way.
The time complexity is O(m times n), and the space complexity is O(m + n). Here, m and n are the lengths of the arrays nums1 and nums2, respectively.
Python
Java
Go
TypeScript
| Approach | Complexity |
|---|---|
| Brute Force Approach | The time complexity is O(n^3), due to the triple loop. The space complexity is O(1), aside from input storage. |
| Optimized Hash Map Approach | The time complexity is O(n^2) because of the double nested loop for generating products and using a hash map lookup. The space complexity is O(n^2) due to storing products in a hash map. |
| Hash Table + Enumeration | — |
| Hash Table + Enumeration Optimization | — |
| 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 |
Leetcode 1577. Number of Ways Where Square of Number Is Equal to Product of Two Numbers • Fraz • 1,497 views views
Watch 7 more video solutions →Practice Number of Ways Where Square of Number Is Equal to Product of Two Numbers with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor