Problem statement

https://binarysearch.com/problems/Kth-Largest-Pair-Product/

Solution 1

Equal to Leetcode 2040. Kth Smallest Product of Two Sorted Arrays.

Complexity

Time complexity is O(n*log m* log N), where n = len(nums1), m = len(nums2) and N = 10**10 + 10 is the maximum value of product. Space complexity is O(1).

Code

class Solution:
    def solve(self, nums1, nums2, k):
        nums1, nums2 = sorted(nums1), sorted(nums2)
        k = len(nums1) * len(nums2) - k
        def check(x):
            total = 0
            for n1 in nums1:
                if n1 > 0: total += bisect.bisect(nums2, x//n1)
                if n1 < 0: total += len(nums2) - bisect.bisect_left(nums2, ceil(x/n1))
                if n1 == 0 and x >= 0: total += len(nums2)
            return total

        beg, end = -10**10 - 1, 10**10 + 1

        while beg + 1 < end:
            mid = (beg + end)//2
            if check(mid) >= k:
                end = mid
            else:
                beg = mid

        return beg + 1

Solution 2

There is better solution, with two pointers technique used for check.

Complexity

It is O((n + m)*log N) for time and O(1) for space.

Code

#### Code by lee215
class Solution:
    def solve(self, A, B, k):
        A, B = sorted(A), sorted(B)
        n, m = len(A), len(B)
        k = n * m - k
        A1, A2 = [-a for a in A if a < 0][::-1], [a for a in A if a >= 0]
        B1, B2 = [-a for a in B if a < 0][::-1], [a for a in B if a >= 0]

        neg = len(A1) * len(B2) + len(A2) * len(B1)
        if k > neg:
            k -= neg
            s = 1
        else:
            k = neg - k + 1
            B1, B2 = B2,B1
            s = -1

        def count(A, B, x):
            res = 0
            j = len(B) - 1
            for i in range(len(A)):
                while j >= 0 and A[i] * B[j] > x:
                    j -= 1
                res += j + 1
            return res

        beg, end = -1, 10**10
        while beg + 1 < end:
            mid = (beg + end) // 2
            if count(A1, B1, mid) + count(A2, B2, mid) >= k:
                end = mid
            else:
                beg = mid
        return end * s