# Number of Ways Where Square of Number Is Equal to Product of Two Numbers
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-where-square-of-number-is-equal-to-product-of-two-numbers
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** Array, Hash Table
---
## Problem
Given two arrays of integers `nums1` and `nums2`, return the number of triplets formed (type 1 and type 2) under the following rules:

* Type 1: Triplet (i, j, k) if `nums1[i]2 == nums2[j] * nums2[k]` where `0 <= i < nums1.length` and `0 <= j < k < nums2.length`.
* Type 2: Triplet (i, j, k) if `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 <= 1000`
* `1 <= nums1[i], nums2[i] <= 105`

# Approaches
## Brute Force Iteration
This approach involves iterating through all possible triplets `(i, j, k)` for both Type 1 and Type 2, checking if the condition `num^2 = product` holds for each triplet. This is the most straightforward but also the slowest method.
**Time:** O(N * M^2 + M * N^2), where N is the length of `nums1` and M is the length of `nums2`. The helper function `count(arr1, arr2)` takes `O(N * M^2)`. The total time is the sum for both types of triplets. This is too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store counts and intermediate values.
**Pros:** Simple to understand and implement.
**Cons:** Very inefficient and will likely result in a "Time Limit Exceeded" error for the given constraints.
### Explanation
The core idea is to check every single combination of indices `(i, j, k)` that satisfy the problem's constraints. We can implement a helper function that takes two arrays, `arr1` and `arr2`, and counts the number of triplets where the square of an element from `arr1` equals the product of two distinct elements from `arr2`. By calling this helper function twice with the arguments swapped (`count(nums1, nums2)` and `count(nums2, nums1)`), we can find the total number of valid triplets.

```java
class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
    }

    private int countTriplets(int[] arr1, int[] arr2) {
        int count = 0;
        int n = arr1.length;
        int m = arr2.length;
        if (m < 2) {
            return 0;
        }
        for (int i = 0; i < n; i++) {
            long square = (long) arr1[i] * arr1[i];
            for (int j = 0; j < m; j++) {
                for (int k = j + 1; k < m; k++) {
                    if (square == (long) arr2[j] * arr2[k]) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   The problem can be broken down into two symmetric subproblems: counting Type 1 triplets and counting Type 2 triplets. The total count is the sum of these two.
*   We can create a helper function, say `count(arr1, arr2)`, which counts triplets where a square of a number from `arr1` equals the product of two numbers from `arr2`. The final answer would be `count(nums1, nums2) + count(nums2, nums1)`.
*   The `count` function iterates through every element `arr1[i]`. For each `arr1[i]`, it then iterates through all possible pairs `(arr2[j], arr2[k])` with `j < k`.
*   Inside the innermost loop, it checks if `(long)arr1[i] * arr1[i] == (long)arr2[j] * arr2[k]`. If the condition is true, a counter is incremented.
*   Using `long` for calculations is crucial to prevent integer overflow, as numbers can be up to 10^5, and their square can be up to 10^10.

## Two Pointers with Sorting
This approach improves upon the brute-force method by optimizing the search for pairs. For each number from the first array, we find pairs in the second array whose product equals the square of the number. By sorting the second array, we can use a two-pointer technique to find these pairs efficiently in linear time relative to the size of the second array.
**Time:** O(N * M + M * log M + M * N + N * log N). Sorting takes `O(M log M)` and `O(N log N)`. The nested loops take `O(N * M)` and `O(M * N)`. This simplifies to `O(N*M)`. · **Space:** O(log N + log M) or O(N + M) depending on the space used by the sorting algorithm.
**Pros:** Significantly more efficient than the brute-force approach.; It's an in-place approach if the sorting algorithm used is in-place (modifying the input array).
**Cons:** The logic for handling duplicates in the two-pointer scan can be complex to implement correctly.; Its worst-case time complexity is similar to the hash map approach but it doesn't benefit from a small number of unique elements.
### Explanation
We can reframe the problem for a fixed `num1` from the first array as a 'Two Sum'-like problem on the second array. We need to find pairs `(num2_j, num2_k)` such that their product is `num1^2`. If the second array is sorted, this can be solved efficiently using two pointers.

The overall strategy is to have a helper function that first sorts the second array (`arr2`). Then, for each element in the first array (`arr1`), it uses a two-pointer scan (`left` and `right`) on `arr2` to find pairs whose product matches the target square. A key part of this approach is correctly handling duplicate numbers to ensure every valid pair is counted exactly once.

```java
import java.util.Arrays;

class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        return countTriplets(nums1, nums2) + countTriplets(nums2, nums1);
    }

    private int countTriplets(int[] arr1, int[] arr2) {
        Arrays.sort(arr2);
        int count = 0;
        int n = arr1.length;
        int m = arr2.length;
        if (m < 2) {
            return 0;
        }

        for (int i = 0; i < n; i++) {
            long target = (long) arr1[i] * arr1[i];
            int left = 0, right = m - 1;
            while (left < right) {
                long product = (long) arr2[left] * arr2[right];
                if (product < target) {
                    left++;
                } else if (product > target) {
                    right--;
                } else { // product == target
                    if (arr2[left] == arr2[right]) {
                        int numElements = right - left + 1;
                        count += numElements * (numElements - 1) / 2;
                        break; // All elements in between are the same
                    }
                    int leftCount = 1;
                    while (left + 1 < right && arr2[left] == arr2[left + 1]) {
                        leftCount++;
                        left++;
                    }
                    int rightCount = 1;
                    while (right - 1 > left && arr2[right] == arr2[right - 1]) {
                        rightCount++;
                        right--;
                    }
                    count += leftCount * rightCount;
                    left++;
                    right--;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Define a helper function `count(arr1, arr2)`.
*   Sort `arr2`.
*   Initialize `total_triplets = 0`.
*   For each `num1` in `arr1`:
    *   Calculate `target = (long)num1 * num1`.
    *   Initialize two pointers on `arr2`: `left = 0`, `right = arr2.length - 1`.
    *   While `left < right`:
        *   Calculate `product = (long)arr2[left] * arr2[right]`.
        *   If `product < target`, increment `left`.
        *   Else if `product > target`, decrement `right`.
        *   Else (`product == target`):
            *   If `arr2[left] == arr2[right]`, all elements between them are the same. The number of pairs is `k * (k-1) / 2` where `k` is `right - left + 1`. Add this to the count and break the inner loop.
            *   If `arr2[left] != arr2[right]`, count the number of duplicates for `arr2[left]` and `arr2[right]`, multiply these counts, add to the total, and move the pointers past the duplicates.
*   Return `total_triplets`.
*   The main function returns `count(nums1, nums2) + count(nums2, nums1)`.

## Using a Hash Map for Frequencies
This is the most efficient approach. Instead of repeatedly scanning the second array to find pairs, we can pre-process it and store the frequency of each number in a hash map. This allows for a constant-time lookup to find the required number to form a product, significantly speeding up the process.
**Time:** O(N * U2 + M * U1), where N and M are the lengths of the arrays, and U1 and U2 are the number of unique elements in `nums1` and `nums2` respectively. Building the map takes `O(M)`. The nested loops take `O(N * U2)`. The total complexity is the sum for both types. In the worst case (`U1=N, U2=M`), it's `O(N*M)`, but it's much faster if there are many duplicate numbers. · **Space:** O(U1 + U2) to store the frequency maps for both arrays, where U1 and U2 are the number of unique elements in `nums1` and `nums2`.
**Pros:** Most efficient approach, especially when the input arrays contain many duplicate values.; The logic is relatively straightforward compared to the two-pointer duplicate handling.
**Cons:** Requires extra space for the hash maps, proportional to the number of unique elements.
### Explanation
The key optimization here is to avoid re-computing information. For a given `target` square, we need to find pairs in the second array. Instead of a linear scan or a two-pointer scan for every target, we can count the occurrences of each number in the second array and store them in a hash map. 

Then, for each number `num1` in the first array, we iterate through the unique numbers `num2` in the hash map. For each `num2`, we can calculate the `required` number that would satisfy `num2 * required = num1^2`. We can then check the hash map for the existence and frequency of this `required` number. Special care is taken to handle cases where `num2` is equal to `required` (we need to choose two from the same group of numbers) and to avoid double-counting pairs like `(a, b)` and `(b, a)`.

```java
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numTriplets(int[] nums1, int[] nums2) {
        return (int) (countTriplets(nums1, nums2) + countTriplets(nums2, nums1));
    }

    private long countTriplets(int[] arr1, int[] arr2) {
        Map<Integer, Integer> freq2 = new HashMap<>();
        for (int num : arr2) {
            freq2.put(num, freq2.getOrDefault(num, 0) + 1);
        }

        long count = 0;
        for (int num1 : arr1) {
            long target = (long) num1 * num1;
            for (Map.Entry<Integer, Integer> entry : freq2.entrySet()) {
                long num2 = entry.getKey();
                long count2 = entry.getValue();

                if (target % num2 != 0) {
                    continue;
                }
                long requiredNum = target / num2;
                
                if (freq2.containsKey((int)requiredNum)) {
                    if (num2 == requiredNum) {
                        count += count2 * (count2 - 1) / 2;
                    } else if (num2 < requiredNum) {
                        count += count2 * freq2.get((int)requiredNum);
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Define a helper function `count(arr1, arr2)`.
*   Create a frequency map `freq2` for all numbers in `arr2`.
*   Initialize `total_triplets = 0`.
*   For each `num1` in `arr1`:
    *   Calculate `target = (long)num1 * num1`.
    *   For each unique number `num2` and its `count2` in `freq2`:
        *   If `target` is divisible by `num2`:
            *   Calculate `required = target / num2`.
            *   If `required` exists in `freq2`:
                *   If `num2 == required`, add `count2 * (count2 - 1) / 2` to `total_triplets`.
                *   If `num2 < required`, add `count2 * freq2.get(required)` to `total_triplets` to avoid double counting.
*   Return `total_triplets`.
*   The main function returns `count(nums1, nums2) + count(nums2, nums1)`.

# Solutions
### Java

```java
class Solution {
public
  int numTriplets(int[] nums1, int[] nums2) {
    Map<Integer, Integer> cnt1 = new HashMap<>();
    Map<Integer, Integer> cnt2 = new HashMap<>();
    for (int v : nums1) {
      cnt1.put(v, cnt1.getOrDefault(v, 0) + 1);
    }
    for (int v : nums2) {
      cnt2.put(v, cnt2.getOrDefault(v, 0) + 1);
    }
    long ans = 0;
    for (var e1 : cnt1.entrySet()) {
      long a = e1.getKey(), x = e1.getValue();
      for (var e2 : cnt2.entrySet()) {
        long b = e2.getKey(), y = e2.getValue();
        if ((a * a) % b == 0) {
          long c = a * a / b;
          if (b == c) {
            ans += x * y * (y - 1);
          } else {
            ans += x * y * cnt2.getOrDefault((int)c, 0);
          }
        }
        if ((b * b) % a == 0) {
          long c = b * b / a;
          if (a == c) {
            ans += x * (x - 1) * y;
          } else {
            ans += x * y * cnt1.getOrDefault((int)c, 0);
          }
        }
      }
    }
    return (int)(ans >> 1);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numTriplets(vector<int> &nums1, vector<int> &nums2) {
    auto cnt1 = count(nums1);
    auto cnt2 = count(nums2);
    return cal(cnt1, nums2) + cal(cnt2, nums1);
  }
  unordered_map<long long, int> count(vector<int> &nums) {
    unordered_map<long long, int> cnt;
    for (int i = 0; i < nums.size(); i++) {
      for (int j = i + 1; j < nums.size(); j++) {
        cnt[(long long)nums[i] * nums[j]]++;
      }
    }
    return cnt;
  }
  int cal(unordered_map<long long, int> &cnt, vector<int> &nums) {
    int ans = 0;
    for (int x : nums) {
      ans += cnt[(long long)x * x];
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int: cnt1 = Counter(nums1) cnt2 = Counter(nums2) ans = 0 for a, x in cnt1 . items(): for b, y in cnt2 . items(): if a * a % b == 0: c = a * a // b if b == c: ans += x * y * (y - 1) else: ans += x * y * cnt2[c] if b * b % a == 0: c = b * b // a if a == c: ans += x * (x - 1) * y else: ans += x * y * cnt1[c] return ans >> 1

```