Python 3: TC O((M+N)*log(range), SC O(1): Guess-And-Check, Heinous 2-Pointer
Intuition\n\nUsually the answer to finding the kth highest value in these cases is to find the smallest p where there are at least k items smaller than p.\n\nTh
# Intuition\n\nUsually the answer to finding the `kth` highest value in these cases is to find the smallest `p` where there are at least `k` items smaller than `p`.\n\nThen you can use binary search and/or clever math to find that value of `p`.\n\n## Guess And Check\n\nHere we use binary search to find that smallest product `p` with at least `k` products `<= p`.\n\n## Counting Products Less than `p`\n\nThis is the tricky part.\n\nA brute force answer would to be enumerate over all the products of `x` from `nums1` and `y` from `nums2`.\n\n**But we can do better than brute force.**\n\n**For these examples let the product `p` be positive.**\n\nSuppose `x > 0`. We know that as values in `y` increase in `nums2`, the value of `x*y` is increasing. Therefore if we can find the last `y` where `x*y <= p`, then all prior values of `y` will work too. **This implies a binary search algorithm.**\n\nBinary search is fine and it will work, you\'ll probably get FT 30% or better.\n\n**But there\'s another pattern: as `x > 0` increases, our limit on `y` decreases.** This is the tricky part and why I called the 2-pointer heinous, because it depends on the sign of x, AND the sign of the product, ugh.\n\nIf we "flip things around" then the largest `x` means we have the lowest limit on `y`. When we find that lowest `y`, every prior value works too.\n\n**Then the next largest `x` allows for a slightly higher `y`. Therefore as we iterate backwards in `nums1` with `x > 0`, we iterate forwards in `nums2`. We have a 2-pointer algorithm!**\n\n## `p >= 0`\n\nFor `x > 0`, as x decreases, the max `y` we can use increases. So iterate over `x > 0` descending, and increment a pointer `j` in `nums2`.\n\nFor `x < 0`, as `x < 0` increases toward zero, the more negative the `y` values we can use get. Any `y > 0` also works. So start with `j = N-1` and decrement for each `x`.\n\n## `p < 0`\n\nSame general idea as `p >= 0`, but the details are different.\n\nFor `x > 0` we require negative `y`. As `x` increases the required `y` is less negative. Therefore we iterate over `x` ascending and increment the `j` pointer into `nums2`.\n\nFor `x < 0` we need positive `y`. As `x` decreases toward `-inf` we need less negative `y` values. So we can start with the least negative `x` and iterate descending, then decrement `j`.\n\n**I got to the answer after a lot of wrangling with the orders and edge cases so the code may not match this exactly... but the ideas are the same.**\n\n# Final Binary Search\n\nOnce we can compute the number of pairs, then we do binary search over the range `[smallestProduct, greatestProduct]`.\n\nThe smallest and greatest products involve the endpoints of the arrays. Intead of having complicated logic for what to do if the endpoints are positive versus negative, I just brute-force iterated over all 4 combinations and took the min and max.\n\n# Complexity\n- Time complexity: `O((M+N)*log(range))`, we do binary search over the range of products, `log(range)` steps, and the 2-pointer lets us count products in `O(M+N)`\n\n- Space complexity: constant, just iteration and pointers and such\n\n# Code\n```python3 []\nclass Solution:\n    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n        # nums1 and nums2 are sorted, can have negatives\n        # return 1-based kth smallest product\n\n\n        # if nums1[i] < 0 then products grow in reverse order for nums2\n        # if nums1[i] > 0 then products grow in forward order for nums2\n\n        # for a guess-and-check solution we can ask how many products are below P\n        # using this (binary search)\n\n        # cost would be O(log(range) * m * log(n))\n        #                  binsearch  foreach  binsearch, index math\n\n        # that\'s acceptable time\n\n        # or we can brute-force iterate, e.g. for each next product in O(range) time\n        #      update all O(m) pointers in O(m*n) time\n        #      ouch, not good\n\n        # so m-pointer doesn\'t seem to be a good plan at all\n\n        if len(nums1) > len(nums2): nums1, nums2 = nums2, nums1\n        M = len(nums1)\n        N = len(nums2)\n\n        lastNegative = bisect_right(nums1, -1) - 1\n        firstPositive = bisect_left(nums1, 1)\n        z1 = firstPositive - lastNegative - 1\n\n        def atLeastK(p: int) -> bool:\n            # TODO: skip over positive/negative y values in O(1)\n\n            total = 0\n\n            if p >= 0:\n                total += z1*N\n                \n                # x*y <= p\n                #    as x gets smaller (toward zero) y can get farther from zero\n                j = N-1\n                for i in range(0, lastNegative+1):\n                    while j >= 0 and nums1[i]*nums2[j] <= p: j -= 1\n                    total += N-j-1\n                    if total >= k: return True\n\n                j = 0\n                for i in range(M-1, firstPositive-1, -1):\n                    while j < N and nums1[i]*nums2[j] <= p: j += 1\n                    total += j\n                    if total >= k: return True\n            else:\n\n                # for small x < 0 we need a large positive y to get under the threshold\n                # as x decreases away from zero then the y threshold gets smaller, so for descending x we have j descending too from N-1\n                j = N-1\n                for i in range(lastNegative, -1, -1):\n                    while j >= 0 and nums1[i]*nums2[j] <= p: j -= 1\n                    total += N-j-1\n                    if total >= k: return True\n\n                # for small x > 0 we need large negative y to get under p < 0\n                #  as x increases we can use less negative y\n                #   so increasing x --> increasing j\n                j = 0\n                for i in range(firstPositive, M):\n                    while j < N and nums1[i]*nums2[j] <= p: j += 1\n                    total += j\n                    if total >= k: return True\n\n            return False\n\n        # max values come from the ends (?)\n        lo = math.inf\n        hi = -math.inf\n        for e1 in [0, -1]:\n            for e2 in [0, -1]:\n                p = nums1[e1]*nums2[e2]\n                lo = min(lo, p)\n                hi = max(hi, p)\n\n        while lo < hi:\n            p = (hi-lo)//2 + lo # not (hi+lo)//2 to avoid round-down for negative numbers -> inf loop shennanigans\n            if atLeastK(p):\n                hi = p\n            else:\n                lo = p+1\n\n        return lo\n```
['Python3']