2040. Kth Smallest Product of Two Sorted Arrays

Description

Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return the k^th (1-based) smallest product of nums1[i] * nums2[j] where 0 <= i < nums1.length and 0 <= j < nums2.length.

Example 1:

Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8
Explanation: The 2 smallest products are:
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
The 2^nd smallest product is 8.

Example 2:

Input: nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
Output: 0
Explanation: The 6 smallest products are:
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
The 6^th smallest product is 0.

Example 3:

Input: nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
Output: -6
Explanation: The 3 smallest products are:
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
The 3^rd smallest product is -6.

Constraints:

1 <= nums1.length, nums2.length <= 5 * 10⁴
-10⁵ <= nums1[i], nums2[j] <= 10⁵
1 <= k <= nums1.length * nums2.length
nums1 and nums2 are sorted.

Solutions

Solution 1: Binary Search

Thinking

There are up to \(2.5 \times 10^9\) products, so they cannot be listed. The \(k\)-th is monotone in a threshold \(p\): the count of products \(\le p\) never decreases.

Binary-search \(p\) on \([-M,M]\). For each \(x\) in \(nums1\), positives use \(nums2[i] \le p/x\), negatives reverse the inequality, and zeros contribute the whole array when \(p \ge 0\). Sortedness lets each count be a binary search.

bisect_left returns the smallest \(p\) whose count is at least \(k\).

We can use binary search to enumerate the value of the product \(p\), defining the binary search interval as \([l, r]\), where \(l = -\textit{max}(|\textit{nums1}[0]|, |\textit{nums1}[n - 1]|) \times \textit{max}(|\textit{nums2}[0]|, |\textit{nums2}[n - 1]|)\), \(r = -l\).

For each \(p\), we calculate the number of products less than or equal to \(p\). If this number is greater than or equal to \(k\), it means the \(k\)-th smallest product must be less than or equal to \(p\), so we can reduce the right endpoint of the interval to \(p\). Otherwise, we increase the left endpoint of the interval to \(p + 1\).

The key to the problem is how to calculate the number of products less than or equal to \(p\). We can enumerate each number \(x\) in \(\textit{nums1}\) and discuss in cases:

If \(x > 0\), then \(x \times \textit{nums2}[i]\) is monotonically increasing as \(i\) increases. We can use binary search to find the smallest \(i\) such that \(x \times \textit{nums2}[i] > p\). Then, \(i\) is the number of products less than or equal to \(p\), which is accumulated into the count \(\textit{cnt}\);
If \(x < 0\), then \(x \times \textit{nums2}[i]\) is monotonically decreasing as \(i\) increases. We can use binary search to find the smallest \(i\) such that \(x \times \textit{nums2}[i] \leq p\). Then, \(n - i\) is the number of products less than or equal to \(p\), which is accumulated into the count \(\textit{cnt}\);
If \(x = 0\), then \(x \times \textit{nums2}[i] = 0\). If \(p \geq 0\), then \(n\) is the number of products less than or equal to \(p\), which is accumulated into the count \(\textit{cnt}\).

This way, we can find the \(k\)-th smallest product through binary search.

The time complexity is \(O(m \times \log n \times \log M)\), where \(m\) and \(n\) are the lengths of \(\textit{nums1}\) and \(\textit{nums2}\), respectively, and \(M\) is the maximum absolute value in \(\textit{nums1}\) and \(\textit{nums2}\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        def count(p: int) -> int:
            cnt = 0
            n = len(nums2)
            for x in nums1:
                if x > 0:
                    cnt += bisect_right(nums2, p / x)
                elif x < 0:
                    cnt += n - bisect_left(nums2, p / x)
                else:
                    cnt += n * int(p >= 0)
            return cnt

        mx = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))
        return bisect_left(range(-mx, mx + 1), k, key=count) - mx

class Solution {
    private int[] nums1;
    private int[] nums2;

    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        this.nums1 = nums1;
        this.nums2 = nums2;
        int m = nums1.length;
        int n = nums2.length;
        int a = Math.max(Math.abs(nums1[0]), Math.abs(nums1[m - 1]));
        int b = Math.max(Math.abs(nums2[0]), Math.abs(nums2[n - 1]));
        long r = (long) a * b;
        long l = (long) -a * b;
        while (l < r) {
            long mid = (l + r) >> 1;
            if (count(mid) >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private long count(long p) {
        long cnt = 0;
        int n = nums2.length;
        for (int x : nums1) {
            if (x > 0) {
                int l = 0, r = n;
                while (l < r) {
                    int mid = (l + r) >> 1;
                    if ((long) x * nums2[mid] > p) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                cnt += l;
            } else if (x < 0) {
                int l = 0, r = n;
                while (l < r) {
                    int mid = (l + r) >> 1;
                    if ((long) x * nums2[mid] <= p) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                cnt += n - l;
            } else if (p >= 0) {
                cnt += n;
            }
        }
        return cnt;
    }
}

class Solution {
public:
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        int m = nums1.size(), n = nums2.size();
        int a = max(abs(nums1[0]), abs(nums1[m - 1]));
        int b = max(abs(nums2[0]), abs(nums2[n - 1]));
        long long r = 1LL * a * b;
        long long l = -r;
        auto count = [&](long long p) {
            long long cnt = 0;
            for (int x : nums1) {
                if (x > 0) {
                    int l = 0, r = n;
                    while (l < r) {
                        int mid = (l + r) >> 1;
                        if (1LL * x * nums2[mid] > p) {
                            r = mid;
                        } else {
                            l = mid + 1;
                        }
                    }
                    cnt += l;
                } else if (x < 0) {
                    int l = 0, r = n;
                    while (l < r) {
                        int mid = (l + r) >> 1;
                        if (1LL * x * nums2[mid] <= p) {
                            r = mid;
                        } else {
                            l = mid + 1;
                        }
                    }
                    cnt += n - l;
                } else if (p >= 0) {
                    cnt += n;
                }
            }
            return cnt;
        };
        while (l < r) {
            long long mid = (l + r) >> 1;
            if (count(mid) >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};

func kthSmallestProduct(nums1 []int, nums2 []int, k int64) int64 {
    m := len(nums1)
    n := len(nums2)
    a := max(abs(nums1[0]), abs(nums1[m-1]))
    b := max(abs(nums2[0]), abs(nums2[n-1]))
    r := int64(a) * int64(b)
    l := -r

    count := func(p int64) int64 {
        var cnt int64
        for _, x := range nums1 {
            if x > 0 {
                l, r := 0, n
                for l < r {
                    mid := (l + r) >> 1
                    if int64(x)*int64(nums2[mid]) > p {
                        r = mid
                    } else {
                        l = mid + 1
                    }
                }
                cnt += int64(l)
            } else if x < 0 {
                l, r := 0, n
                for l < r {
                    mid := (l + r) >> 1
                    if int64(x)*int64(nums2[mid]) <= p {
                        r = mid
                    } else {
                        l = mid + 1
                    }
                }
                cnt += int64(n - l)
            } else if p >= 0 {
                cnt += int64(n)
            }
        }
        return cnt
    }

    for l < r {
        mid := (l + r) >> 1
        if count(mid) >= k {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

function kthSmallestProduct(nums1: number[], nums2: number[], k: number): number {
    const m = nums1.length;
    const n = nums2.length;

    const a = BigInt(Math.max(Math.abs(nums1[0]), Math.abs(nums1[m - 1])));
    const b = BigInt(Math.max(Math.abs(nums2[0]), Math.abs(nums2[n - 1])));

    let l = -a * b;
    let r = a * b;

    const count = (p: bigint): bigint => {
        let cnt = 0n;
        for (const x of nums1) {
            const bx = BigInt(x);
            if (bx > 0n) {
                let l = 0,
                    r = n;
                while (l < r) {
                    const mid = (l + r) >> 1;
                    const prod = bx * BigInt(nums2[mid]);
                    if (prod > p) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                cnt += BigInt(l);
            } else if (bx < 0n) {
                let l = 0,
                    r = n;
                while (l < r) {
                    const mid = (l + r) >> 1;
                    const prod = bx * BigInt(nums2[mid]);
                    if (prod <= p) {
                        r = mid;
                    } else {
                        l = mid + 1;
                    }
                }
                cnt += BigInt(n - l);
            } else if (p >= 0n) {
                cnt += BigInt(n);
            }
        }
        return cnt;
    };

    while (l < r) {
        const mid = (l + r) >> 1n;
        if (count(mid) >= BigInt(k)) {
            r = mid;
        } else {
            l = mid + 1n;
        }
    }

    return Number(l);
}

impl Solution {
    pub fn kth_smallest_product(nums1: Vec<i32>, nums2: Vec<i32>, k: i64) -> i64 {
        let m = nums1.len();
        let n = nums2.len();
        let a = nums1[0].abs().max(nums1[m - 1].abs()) as i64;
        let b = nums2[0].abs().max(nums2[n - 1].abs()) as i64;
        let mut l = -a * b;
        let mut r = a * b;

        let count = |p: i64| -> i64 {
            let mut cnt = 0i64;
            for &x in &nums1 {
                if x > 0 {
                    let mut left = 0;
                    let mut right = n;
                    while left < right {
                        let mid = (left + right) / 2;
                        if (x as i64) * (nums2[mid] as i64) > p {
                            right = mid;
                        } else {
                            left = mid + 1;
                        }
                    }
                    cnt += left as i64;
                } else if x < 0 {
                    let mut left = 0;
                    let mut right = n;
                    while left < right {
                        let mid = (left + right) / 2;
                        if (x as i64) * (nums2[mid] as i64) <= p {
                            right = mid;
                        } else {
                            left = mid + 1;
                        }
                    }
                    cnt += (n - left) as i64;
                } else if p >= 0 {
                    cnt += n as i64;
                }
            }
            cnt
        };

        while l < r {
            let mid = l + (r - l) / 2;
            if count(mid) >= k {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        l
    }
}

2040. Kth Smallest Product of Two Sorted Arrays

Description

Solutions

Solution 1: Binary Search

Comments