Python3 Two Pointer Solution | O(1) Space, O(n*m) Time with Indepth Explanation
Intuition\n Describe your first thoughts on how to solve this problem. \nThere are two types of triples we\'re looking for: \n\n    Type 1: Triplet (i, j, k) if
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThere are two types of triples we\'re looking for: \n\n    Type 1: Triplet (i, j, k) if nums1[i]^2 == nums2[j] * nums2[k] \n    Type 2: Triplet (i, j, k) if nums2[i]^2 == nums1[j] * nums1[k]\n\nNotice the symmetry. It\'s saying we must look for triplets across both arrays. The best way to do this is by running the algorithm twice: once with nums1 as the target (the outer-loop) and again with nums2 as the target.\n\nTo do this without using any space (this can be done using a hashmap to count the instances where the conditions are true for both types), we can use two pointers like a 3Sum problem. In 3Sum, we investigate 1 number and then iterate our pointers over the remainder of a single array, squeezing the Left and Right pointers together. Then, iterate to the next number, shortening the remaining subarray. \n\nThis has a similar approach, except instead of a singular array, we use each number in Array1 `(a1)` and then search for a multiplicative pair in Array2 `(a2)` that would equal to the target of `a1[i]^2`. This works if `a2` is sorted. The time complexity for a sort is `O(nlogn)`, but this pales in comparison to the `O(mn)` runtime of the overall algorithm, so it\'s beneficial to do this. \n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe ```helper``` function will be used twice, once searching the `nums1` array against `nums2`, and then vice versa. \n\nIn the general case (with `a1 and a2`), sort `a2`, then go through each number in `a1`; our target number will be `a1[i]^2`. To optimally search for the pair in `a2`, we use 2 pointers, starting from the beginning and at the end: `l, r = 0, len(a2) - 1`. Then we iterate over them while `l < r`. \n\nThere are three conditions:\n* `a2[l] * a2[r] > target`: The pair is too large in comparison to our target. To mitigate this, we decrement `r`. This will move our pointer to a smaller number in the leftside (this is why we sorted), lowering our multiplicative result\n* `a2[l] * a2[r] < target`: Our pair isn\'t big enough, so we move our left pointer to the right where larger numbers are sorted, thus growing our multiplicative pair\n* `else: # we found our target`: This has 2 subconditions, when the left and right pointer are equal (i.e, `a2[l] == a2[r]`), and the other when they\'re not. \n    * If they\'re equal, that means we shouldn\'t iterate over them to avoid recounting. So, we use the formula for counting pairs:`((n * (n - 1)) // 2)`. This is based on a combination formula, but for only 2 items. Get the size of the window, `n`, and use the formula. We `break` afterward because the numbers are equal, so there are no other pairs to consider between the two numbers.\n    *  Otherwise, they\'re not equal (but the pair is successful), so we count how many of each number there are and multiply the two together, `res += rightCount * leftCount`. \n\n\nRun this twice on both arrays. This would result in `O(2nm)` runtime, which reduces to `O(nm)`.\n\n# Complexity\n- Time complexity: `O(nm), where n == len(nums1) and m == len(nums2)`\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: `O(1)`\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution:\n    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int: \n        def helper(a1, a2): # a1, a2: array1, array2; symmetry\n            # sort the searchable array, a2, to make conditions possible\n            a2.sort()\n            res = 0\n            for n in a1:\n                target = n ** 2\n                l, r = 0, len(a2) - 1\n                while l < r: \n                    if a2[l] * a2[r] > target:\n                        r -= 1\n                    elif a2[l] * a2[r] < target:\n                        l += 1\n                    else:\n                        # if l, r are the same, use combination form and break\n                        if a2[l] == a2[r]:\n                            n = (r - l + 1)\n                            res += ((n * (n - 1))//2)\n                            break\n                        # count all the numbers at l and r\n                        # that are successful pairs\n                        left, right = a2[l], a2[r]\n                        leftCount, rightCount = 0, 0\n                        while l < len(a2) and a2[l] == left:\n                            leftCount += 1\n                            l += 1\n                        while r >= 0 and a2[r] == right:\n                            rightCount += 1\n                            r -= 1\n                        res += rightCount * leftCount\n                    \n            return res\n        \n        # run it twice for the symmetry between type1/type2\n        return helper(nums1, nums2) + helper(nums2, nums1)\n\n```
['Two Pointers', 'Python3']