{x}
blog image

Kth Smallest Product of Two Sorted Arrays

Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return the kth (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 2nd 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 6th 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 3rd smallest product is -6.

 

Constraints:

  • 1 <= nums1.length, nums2.length <= 5 * 104
  • -105 <= nums1[i], nums2[j] <= 105
  • 1 <= k <= nums1.length * nums2.length
  • nums1 and nums2 are sorted.

Solution Explanation: 2040. Kth Smallest Product of Two Sorted Arrays

This problem asks to find the k-th smallest product from pairs of numbers, one from each of two sorted input arrays, nums1 and nums2. A brute-force approach of calculating all products and sorting would be O(mn log(mn)), where 'm' and 'n' are the lengths of the input arrays. This is inefficient for large arrays. The optimal solution leverages binary search for a significantly faster result.

The core idea is to use binary search on the space of possible product values. We'll define a search space that encompasses the minimum and maximum possible product values, then iteratively narrow this range until we pinpoint the k-th smallest product.

  1. Defining the Search Space: The minimum possible product is obtained by multiplying the most negative number in nums1 by the most positive number in nums2 (or vice versa), and the maximum is the product of the most positive numbers.

  2. count(p) Function: This crucial function takes a potential product p as input and counts how many products from all pairs are less than or equal to p. This involves iterating through nums1 and, for each element x:

    • If x > 0, the products increase as we move through nums2. Binary search on nums2 efficiently determines how many products with x are <= p.
    • If x < 0, the products decrease as we move through nums2. Binary search finds how many products are > p, and we subtract this from the length of nums2 to find the count <= p.
    • If x == 0, all products are 0 unless p is positive, in which case, all n products are <= p.

  3. Binary Search Loop: The binary search repeatedly divides the search space in half. If count(mid) (where mid is the midpoint) is greater than or equal to k, it means the k-th smallest product is in the lower half (or it is mid itself); otherwise, it is in the upper half. This process continues until the search space collapses to a single value, which is the answer.

Time and Space Complexity

  • Time Complexity: O(m * log(n) * log(R)), where 'm' is the length of nums1, 'n' is the length of nums2, and 'R' is the range of possible products. The dominant factor is the binary search within the count function (O(log n)) repeated within the outer binary search (O(log R)) for each element in nums1.

  • Space Complexity: O(1). The algorithm uses a constant amount of extra space.

Code Implementations

The code implementations below showcase the solution in Python, Java, C++, and Go. Note the slight variations in handling binary search and data types due to language differences.

Python3

import bisect
 
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)  # Integer division
                elif x < 0:
                    cnt += n - bisect_left(nums2, p // x)
                else:
                    cnt += n if p >= 0 else 0
            return cnt
 
        mx = max(abs(nums1[0]), abs(nums1[-1])) * max(abs(nums2[0]), abs(nums2[-1]))
        l, r = -mx, mx
        while l < r:
            mid = (l + r) // 2
            if count(mid) >= k:
                r = mid
            else:
                l = mid + 1
        return l

Java

import java.util.Arrays;
 
class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        long left = -1000000000000000000L; // Minimum product
        long right = 1000000000000000000L; // Maximum product
 
        while (left < right) {
            long mid = left + (right - left) / 2;
            long count = count(nums1, nums2, mid);
            if (count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
 
    private long count(int[] nums1, int[] nums2, long p) {
        long count = 0;
        for (int x : nums1) {
            if (x > 0) {
                count += binarySearch(nums2, p / x);
            } else if (x < 0) {
                count += nums2.length - binarySearch(nums2, (p + x - 1) / x); // Ceiling division to handle negative
            } else {
                if (p >= 0)
                    count += nums2.length;
            }
        }
        return count;
    }
 
    //Helper Binary Search function
    private int binarySearch(int[] nums, double target) {
        int l = 0, r = nums.length;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return l;
    }
}

C++

#include <vector>
#include <algorithm>
 
using namespace std;
 
class Solution {
public:
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        long long left = -1000000000000000000LL; 
        long long right = 1000000000000000000LL; 
 
        while (left < right) {
            long long mid = left + (right - left) / 2;
            long long count = count(nums1, nums2, mid);
            if (count >= k) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
 
    long long count(vector<int>& nums1, vector<int>& nums2, long long p) {
        long long count = 0;
        for (int x : nums1) {
            if (x > 0) {
                count += upper_bound(nums2.begin(), nums2.end(), p / x) - nums2.begin();
            } else if (x < 0) {
                count += nums2.size() - (lower_bound(nums2.begin(), nums2.end(), (p + x - 1) / x) - nums2.begin()); // Ceiling division
            } else {
                if (p >= 0) count += nums2.size();
            }
        }
        return count;
    }
};

Go

import (
	"sort"
)
 
func kthSmallestProduct(nums1 []int, nums2 []int, k int64) int64 {
	left := int64(-1000000000000000000)
	right := int64(1000000000000000000)
 
	for left < right {
		mid := left + (right-left)/2
		count := count(nums1, nums2, mid)
		if count >= k {
			right = mid
		} else {
			left = mid + 1
		}
	}
	return left
}
 
func count(nums1 []int, nums2 []int, p int64) int64 {
	var count int64
	for _, x := range nums1 {
		if x > 0 {
			count += int64(sort.Search(len(nums2), func(i int) bool { return int64(nums2[i])*int64(x) > p }))
		} else if x < 0 {
			count += int64(len(nums2)) - int64(sort.Search(len(nums2), func(i int) bool { return int64(nums2[i])*int64(x) <= p }))
		} else {
			if p >= 0 {
				count += int64(len(nums2))
			}
		}
	}
	return count
}

These code examples demonstrate the efficient binary search approach to solve the problem with significantly improved time complexity compared to a brute-force method. Remember to handle potential integer overflow when calculating products, especially for large input numbers.