Python 3: FT 100%, LMT 90%: TC O(N1 log(N1) + N2 log(N2) + S1 + S2): Count and Sort Uniques
Intuition\n\nWelcome to my ~6th FT 100% algorithm!\n\nAnd asymptotically it could be even faster on large inputs, see below about iterating over divisors and th
# Intuition\n\nWelcome to my ~6th FT 100% algorithm!\n\nAnd asymptotically it could be even faster on large inputs, see below about iterating over divisors and the excellent average case complexity.\n\nSuper brute force is to do a three-pointer algorithm, checking all triplets and counting up the number of matches. But we don\'t have time for that; `1000^3` is `1e9` which will give TLE. (LC usually allows for order ~1e7 ops at the most).\n\nFortunately we can see from the input that the only restriction on `i, j, k` besides the values is that `j < k`. The product of two numbers doesn\'t depend on their order - multiplication commutes. So really the restriction is\n* for `nums[j] != nums[k]: j != k`\n* for `nums[j] == nums[k]: count(nums[k]) choose 2`\n\n## Combinatorics\n\nOnce we realize order doesn\'t matter, we realize that when `vi**2 == vj * vk` and `vj != vk`, then the count is\n* the count of `vi`\n* times the count of `vj`\n* times the count of `vk`\n\nBecause every copy of `vj` can be multiplied with any copy of `vk` to get `vi**2`, and we\'ll know they have different indices.\n\nIf `vj == vk`, then we can\'t do `count[vj]*count[vj]` because that will include pairs where `k==j` and also where we count both `j < k` and `j > k`. Fortunately we can solve that with combinatorics: we know every distinct *pair* of indices will give us an answer. So it\'s `count[vj] choose 2` for the `j < k` pairs.\n\n## Efficient Iteration\n\nWe could check every single triple in `O(N1 * N2)` time, the product of array sizes.\n\nWe can do better in the worst case though. Instead, get the unique values in each array and sort.\n\nThen to form `nums1[i]**2`, we need `nums2[j]*nums2[k]` to be the same. Since we determined earlier the answer only needs us to get counts, let\'s say `nums2[j]` is the smaller number.\n\nThen we only need to iterate over the unique values in `nums2` that are at most `nums1`.\n\n# Approach\n\nThe `nums1[i]**2 = ...` and `nums2[i]**2 = ...` are mirror images of each other.\n\nSo I wrote a helper function that takes "left" and "right" counts and uniques to get the answer. Then I called it with `left` referring to `nums1`, then again with `left` referring to `nums2`.\n\n# Complexity\n- Time complexity: `O(N1 log(N1) + N2 log(N2) + S1 + S2)`\n  - `N1, N2` are the lengths of the arrays\n  - `S1, S2` are the sums of the arrays\n  - the `N log(N)` terms come from sorting the unique factors\n  - the sum terms come from the loop. For each value `vi` in `nums2`, we check all numbers in `nums2` up to `vi`. That\'s `O(vi)` worst case, if nums2 has *all* of `1..vi`. Summed across all `O(N)` uniques, that\'s asymptotically `O(S)` where `S` is the sum\n\n- Space complexity: `O(N1 + N2)`\n\nSo as is sometimes common, ye olde normal comparison sorting is the slowest part of the algorithm.\n\n# Possible Optimization: Iterate over Divisors\n\nIn `sqrt(max)` time we can get all prime divisors.\n\nSketch of why that works\n1. all numbers are the product of primes `2, 3, ..`, just one for prime numbers and obviously 2+ for composite numbers\n1. any composite number `n`, if it has a prime factor larger than `sqrt(n)`, only has one such factor. Proof: suppose it had two, `p1` and `p2`. Then `p1*p2 > sqrt(n)^2 == n`. Which is obviously not possible. So it can\'t have 2+\n\nSo that implies the following algorithm:\n* start with `n`\n* trial divide by all primes at most `sqrt(n)` until the remainder is 1\n* if the remainder after all the divisions is not 1, then it\'s that single prime factor greater than sqrt(n)\n\nAnyway, then we could iterate over just the divisors of each number by\n* first getting the prime factors\n* then using BFS to iterate over them\n\n## Worst Case for Iterating\n\nIn this way we\'d iterate over all factors of `n**2`, which turns out to be `O(e^(log(n)/log(log(n))))`. `log(log(n))` grows very slowly so it\'s not a big deal, but it is technically an asymptotic improvement.\n\nMoreover, most numbers that aren\'t e.g. 360 have few factors. For example, if the prime factors are `7` and `11`, then divisors are separated by gaps of `7`. As a further limit, we wouldn\'t be iterating over all powers of `7` - just up to the number of factors of `7` that `n` has... which is just `O(log(n))` of them at most.\n\nWith this optimization, the complexity of iterating over all possible divisors of `vi` would be reduced from `O(vi)` (guess and check all)` to `O(exp(log(vi)/log(log(vi))))`. Neat.\n\n## Typical Case For Iterating\n\nThat complexity is the absolute worst case though. There are a few numbers that have a *huge* number of prime factors, those that look like `p1**k1 * p2**k2` for small `p1` and p2`.\n\nFor most numbers though there are *many* fewer factors. In fact, the sum of the number of proper divisors for `1..n` only scales as `O(n log(n))`. **So on average, a number `n` only has `log(n)` divisors.**\n\nTherefore the typical time complexity with this algorithm would be\n* iterate over each number `vi`\n* look for the average `O(log(n))` divisors in the other list instead of all `O(vi)` numbers\n* so the complexity would drop from the sum of unique values to the sum of *logarithms* of the unique values\n\nThis is a huge savings!\n\n# Code\n```\nclass Solution:\n    def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:\n        # return number of t1 and t2 triplets\n\n        # t1: nums1[i] = nums2[j]*nums2[k] for j < k\n        # t2: nums2[i] =     1        1 \n\n        # all numbers positive\n        # order doesn\'t matter so sorting would probably help\n\n        # for nums1[i] = 125, we could use a two-pointer for nj*nk... but not contig. so it would be O(N^2)\n\n        # better: get counts of each element in nums1 and nums2\n        # for v1, f1 in nums1 counts:\n        #     iterate over vj in nums2 < sqrt(v1), if divis then get vk and there are v1*vj*vk\n        #     then try sqrt(v1) itself if it\'s a perfect square, it would be f2*(f2-1) // 2 (f2 choose 2)\n\n        # that costs O(n1*n2*sqrt(max))\n\n        # faster?\n\n        c1 = Counter(nums1)\n        c2 = Counter(nums2)\n\n        vs1 = list(c1.keys())\n        vs2 = list(c2.keys())\n        vs1.sort()\n        vs2.sort()\n\n        def count(left, lvals, right, rvals):\n            ans = 0\n\n            for vi, fi in left.items():\n                for vj in rvals:\n                    if vj >= vi: break\n                    if vi**2 % vj == 0:\n                        fj = right[vj]\n                        fk = right.get(vi**2//vj, 0)\n                        ans += fi*fj*fk\n                \n                if vj == vi:\n                    fj = right[vj]\n                    ans += fi*(fj*(fj-1))//2\n\n            return ans\n\n        return count(c1, vs1, c2, vs2) + count(c2, vs2, c1, vs1)\n\n        # TC O(N1 log(N1) + N2 log(N2) + (N1+N2)*sqrt(max))\n```
['Python3']