[Python] Variation of finding Kth value in 2D Ascending Array
1) We split each sorted arrays into positive and negative parts pos1,neg1, pos2, neg2. \n2) We can compute how many multiplied numbers are positive, negative or
1) We split each sorted arrays into positive and negative parts pos1,neg1, pos2, neg2. \n2) We can compute how many multiplied numbers are positive, negative or zeros. Return 0 if k falls between.\n3) If k<=number of negatives, we need to check multiplied numbers from (pos1, neg2) and (pos2, neg1). Else we need to check multiplied numbers from (pos1,pos2) and (neg1, neg2). \n4) If k<= number of negatives, just make negative parts positive and reverse the arrays neg1 and neg2. It does not matter, we can make the result negative. But in this case, kth smallest number would be actually the (number_of_negatives-k+1)th smallest number when we reverse the negaive parts with their absoulte values. \n5) Now the problem is same as finding kth smallest number in a two dimensional array where numbers in each row/column is increasing since the 2D matrix can be thought of as `Val[row][col]= pair1[row]*pair2[col]`. We can compute the rank of an arbitrary value in each pairs in `O(m+n)` time. We just need to compute rank from the two pairs `O(logV)` time. \n```\nimport bisect\nclass Solution:\n    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:\n        n1,n2 = len(nums1), len(nums2)\n        l1, r1 = bisect.bisect_left(nums1, 0),bisect.bisect_right(nums1, 0)\n        l2, r2 = bisect.bisect_left(nums2, 0),bisect.bisect_right(nums2, 0)\n        num_of_negatives = l1*(n2-r2)+ l2*(n1-r1)\n        num_of_positives = l1*l2+ (n1-r1)*(n2-r2)\n        num_of_zeros = (r1-l1)*n2 + (r2-l2)*n1- (r1-l1)*(r2-l2)\n        nums1_n, nums1_p = nums1[:l1], nums1[r1:]\n        nums2_n, nums2_p = nums2[:l2], nums2[r2:]\n        nums1_n, nums2_n = [-d for d in nums1_n], [-d for d in nums2_n]\n        nums1_n.reverse(), nums2_n.reverse()\n        if k<= num_of_negatives:\n            return -self.compute(nums1_n, nums2_p, nums2_n, nums1_p, num_of_negatives-k+1)\n        elif k<=num_of_negatives+num_of_zeros:\n            return 0\n        else:\n            return self.compute(nums1_n, nums2_n, nums1_p, nums2_p, k-num_of_negatives-num_of_zeros)\n    \n    def compute(self, pair_1r,pair_1c, pair_2r, pair_2c, k):\n        start,end = float(\'inf\'), float(\'-inf\')\n        if pair_1r and pair_1c:\n            start = min(pair_1r[0]*pair_1c[0], start)\n            end = max(pair_1r[-1]*pair_1c[-1], end)\n        if pair_2r and pair_2c:\n            start = min(pair_2r[0]*pair_2c[0], start)\n            end = max(pair_2r[-1]*pair_2c[-1], end)\n        while start<end:\n            mid = (start+end)//2\n            k1, low1, high1 = self.get_rank(pair_1r,pair_1c, mid)\n            k2, low2, high2 = self.get_rank(pair_2r,pair_2c, mid)\n            if k1+k2==k:\n                return max(low1,low2)\n            elif k1+k2<k:\n                start = min(high1, high2)\n            else:\n                end = max(low1, low2)\n        return start\n    def get_rank(self,pair_r, pair_c,mid):\n        m, n = len(pair_r), len(pair_c)\n        if m==0 or n==0:\n            return 0, float(\'-inf\'), float(\'inf\')\n        row, col = m-1, 0\n        low, high = float(\'-inf\'), float(\'inf\')\n        ans = 0\n        while row>=0:\n            while col<n and pair_r[row]*pair_c[col]<=mid:\n                low = max(low, pair_r[row]*pair_c[col])\n                col +=1\n            if col<n: \n                high = min(high, pair_r[row]*pair_c[col])\n            ans += col\n            row -= 1\n        return ans, low, high\n```
['Binary Tree']