binary search w/ case analysis by signs
Intuition & Approach\n Describe your first thoughts on how to solve this problem. \n\nThe question constraint specifies that each element in both input arrays i
# Intuition & Approach\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nThe question constraint specifies that each element in both input arrays is in the range of $[-10^5, 10^5]$. This implies that the entirety of the possible numerical search space is in the range of $[-10^{10}, 10^{10}]$, therefore binary search is an appropriate method for solving this problem.\n\nThe predicate function we want to construct will return `True` if there are at least `k` products that can be generated from pairwise elements of `nums1` & `nums2` that are less than or equal to some candidate product, and `False` otherwise.\n\nThe tricky part of this problem is handling all the cases for when the candidate is either negative (-ve) or positive (+ve), and when the pairwise factors are (-ve, -ve), (-ve, +ve), (+ve, -ve) & (+ve, +ve), and counting the number of viable products efficiently. See the comments in the code below for explanations of each case.\n\n# Code\n```python3 []\nclass Solution:\n    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n        m, n = len(nums1), len(nums2)\n        if m > n: nums1, nums2 = nums2, nums1   # swap num arrays, if latter is shorter than former\n\n        idx_0 = bisect.bisect_left(nums2, 0)\n        nums2_neg, nums2_pos = nums2[:idx_0], nums2[idx_0:]     # split `nums2` into -ve & +ve (non-negative more accurately) halves\n        N, P = len(nums2_neg), len(nums2_pos)                   # sizes of the negative & positive splits above\n        def has_at_least_k_prods_le_(candidate):\n            le_cnt = 0          # tracks the count of all pairwise products that are less than or equal (<=) to the candidate\n            if candidate < 0:\n                for x in nums1:\n                    if x < 0:   # prods <= a -ve candidate can be made from a -ve x and +ve nums w/ sufficiently large abs-vals\n                        le_cnt += P - bisect.bisect_left(nums2_pos, candidate/x)\n                    elif x > 0: # prods <= a -ve candidate can be made from a +ve x and -ve nums w/ sufficiently large abs-vals\n                        le_cnt += bisect.bisect_right(nums2_neg, candidate/x)\n            else:   # candidate >= 0\n                for x in nums1:\n                    if x == 0:  # prods <= a +ve candidate can be made from 0 and all numbers, since 0 * n = 0\n                        le_cnt += N + P\n                    elif x < 0: # prods <= a +ve candidate can be made from a -ve x, and all +ve nums & -ve nums w/ sufficiently small abs-vals\n                        le_cnt += P + int(candidate > 0) * (N - bisect.bisect_left(nums2_neg, candidate/x))\n                    else:       # prods <= a +ve candidate can be made from a +ve x, and all -ve nums & +ve nums w/ sufficiently small abs-vals\n                        le_cnt += N + bisect.bisect_right(nums2_pos, candidate/x)\n            return le_cnt >= k\n\n        left, right = -10**10, 10**10\n        while left < right:\n            mid = left + (right - left) // 2\n            if has_at_least_k_prods_le_(mid):\n                right = mid\n            else:\n                left = mid + 1\n\n        return left\n```\n\n# Complexity\n- Time complexity: $$O(min(m,n)\u22C5log(max(m,n))\u22C5log(2\xD710^{10}))$$ - linear iteration on the smaller of `nums1` & `nums2`, where each iteration performs a binary search on the larger of `nums1` & `nums2`, with a constant factor of $log_2(2\xD710^{10})$ which is the size constraint of the numerical search space\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(max(m,n))$$ - as we\'re splitting the larger of `nums1` & `nums2` into 2 halves for more convenient counting\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->
['Binary Search', 'Python3']