BinarySearch Counting Fully Explained Python
there can be |nums1| * |nums2| products, so finding every product and then couting k smallest is too slow.\n\nIf you knew what k was, can you count number of pr
there can be |nums1| * |nums2| products, so finding every product and then couting k smallest is too slow.\n\nIf you knew what k was, can you count number of products less than k?\nIf intgers were all positive heres how u would do it in O(n) time\nMaintatin two pointers (i, j), one points to beggining of arr1 and other to the end of arr2.\n```\nIf nums[i]*nums[j] <= k, count += (j + 1),\n```\nbecause all elements to the left of j also satisfy the inequality.\n```\nif nums[i]*nums[j] > k, j -= 1,\n```\nbecause all elements to the right of i will also not work with nums[j]\n\nBut elements can also be negative and in this case you just need to handle them separately.\n\nNow that you have an efficient way of counting, u still dont know k.\n**But you can guess k using binary search.**\n```\nif countOfProducts(guess) < k, guess is too small\nif countOfProducts(guess) > k, guess is too large\n```\n\n**Time: O(n * log(maxProduct - minProduct))**\nSpace: O(n) if you separate negaitve and positive nummbers into different arrays. But you can do it O(1). \n\n```\ndef kthSmallestProduct(self, nums1, nums2, k):\n    #elements can be negative, so max and min prod need to calculated properly\n    L = min(nums1[0]*nums2[0], nums1[0]*nums2[-1], nums2[0]*nums1[-1])\n    R = max(nums1[0]*nums2[0], nums1[-1]*nums2[-1], nums1[-1]*nums2[0], nums1[0]*nums2[-1])\n\n    neg1 = [i for i in nums1 if i < 0]; nums1 = nums1[len(neg1): ]\n    neg2 = [i for i in nums2 if i < 0]; nums2 = nums2[len(neg2): ]\n    def getCount(k):\n        #4 combinations to count\n        #(neg, neg), (neg, pos), (pos, neg), (pos, pos)\n        count = 0\n        #(neg, neg)\n        i = len(neg1) - 1; j = 0\n        while i >= 0 and j < len(neg2):\n            if neg1[i]*neg2[j] <= k:\n                count += (len(neg2) - j)\n                i -= 1\n            else:\n                j += 1\n        \n        #(neg, pos)\n        i = 0; j = 0\n        while i < len(neg1) and j < len(nums2):\n            if neg1[i]*nums2[j] <= k:\n                count += (len(nums2) - j)\n                i += 1\n            else:\n                j += 1\n        \n        #(pos, neg)\n        i = len(nums1) - 1; j = len(neg2) - 1\n        while i >= 0 and j >= 0:\n            if nums1[i]*neg2[j] <= k:\n                count += (j + 1)\n                i -= 1\n            else:\n                j -= 1\n        \n        #(pos, pos)\n        i = 0; j = len(nums2) - 1\n        while i < len(nums1) and j >= 0:\n            if nums1[i]*nums2[j] <= k:\n                count += (j + 1)\n                i += 1\n            else:\n                j -= 1\n        \n        return count\n    \n    while L < R:\n        M = (L+R)//2\n        if getCount(M) < k:\n            L = M+1\n        else:\n            R = M\n    \n    return L\n```
['Binary Search', 'Python']