LeetCode 2040 - Kth Smallest Product of Two Sorted Arrays

The problem asks for the k-th smallest product that can be formed by multiplying one element from the sorted array nums1 with one element from the sorted array nums2. Both arrays may contain negative numbers, zeros, and positive numbers.

leetcodehardarraybinary-search

LeetCode Problem 2040

Difficulty: 🔴 Hard
Topics: Array, Binary Search

Solution

Problem Understanding

The problem asks for the k-th smallest product that can be formed by multiplying one element from the sorted array nums1 with one element from the sorted array nums2. Both arrays may contain negative numbers, zeros, and positive numbers. The value of k is 1-based, meaning k = 1 corresponds to the smallest product overall. The arrays are sorted, but they may have different lengths, and the total number of products can be as large as nums1.length * nums2.length, which can be up to $2.5 \times 10^9$ given the constraints.

Key points to note include the presence of negative numbers, which reverse the order of products (multiplying two negatives produces a positive), and zeros, which can dominate the k-th smallest product if k is small. Naively computing all possible products and sorting them will exceed time and space limits because the product array could reach billions of entries. Therefore, a more efficient approach that leverages the sorted nature of the arrays is required.

Important edge cases include arrays with all negative numbers, arrays containing zero, or arrays with mixed signs where the k-th product might come from multiplying a negative with a positive.

Approaches

The brute-force approach would involve generating all possible products from nums1[i] * nums2[j], storing them in a list, sorting the list, and returning the k-th element. While correct, this approach has time and space complexity proportional to the product of the lengths of the arrays, which is infeasible for large inputs.

The optimal approach uses binary search on the value of the product rather than the indices. The key insight is that for a fixed candidate product x, we can efficiently count how many products are less than or equal to x using a two-pointer or binary search strategy on the second array for each element in the first array. This count lets us adjust the search range to home in on the k-th smallest product without generating all products.

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m log(n * m)) O(n * m) Generate all products, sort, and pick k-th
Optimal O((n + m) * log(max_val - min_val)) O(1) Binary search on product values with counting using two-pointer/binary search

Algorithm Walkthrough

  1. Define search boundaries: The smallest possible product is min(nums1) * min(nums2) or min(nums1) * max(nums2), and the largest is max(nums1) * max(nums2) or max(nums1) * min(nums2) depending on signs. Use these as initial binary search bounds.
  2. Binary search on product values: Repeat until the search interval converges. For each candidate mid value, count how many products are less than or equal to mid.
  3. Counting products <= mid:

For each number a in nums1:

  • If a is positive, count elements in nums2 such that a * b <= mid using binary search (since nums2 is sorted).
  • If a is negative, count elements in nums2 such that a * b <= mid, which translates to counting from the other end of nums2.
  • If a is zero and mid >= 0, all nums2 elements contribute to the count.
  1. Adjust search interval: If the count of products <= mid is less than k, set low = mid + 1; otherwise, set high = mid. Repeat.
  2. Return the final result: Once low equals high, it represents the k-th smallest product.

Why it works: The invariant is that the binary search maintains the range where the k-th smallest product must lie. The counting function guarantees that if there are at least k products less than or equal to a candidate, the true k-th product cannot be smaller than this candidate. This ensures convergence to the correct answer.

Python Solution

from bisect import bisect_right, bisect_left
from typing import List

class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int:
        def count_leq(x: int) -> int:
            count = 0
            for a in nums1:
                if a > 0:
                    count += bisect_right(nums2, x // a)
                elif a < 0:
                    count += len(nums2) - bisect_left(nums2, (x + (-a-1)) // a)  # careful integer division
                else:
                    if x >= 0:
                        count += len(nums2)
            return count

        left, right = -10**10, 10**10
        while left < right:
            mid = (left + right) // 2
            if count_leq(mid) < k:
                left = mid + 1
            else:
                right = mid
        return left

Implementation walkthrough: The count_leq function efficiently counts products <= x using binary search on nums2. Positive a values use bisect_right, negative a values use bisect_left with a transformation to handle negative products, and zeros contribute when x >= 0. The binary search over product values ensures the k-th smallest product is found without generating all products.

Go Solution

import "sort"

func kthSmallestProduct(nums1 []int, nums2 []int, k int64) int64 {
    countLEQ := func(x int64) int64 {
        var count int64 = 0
        for _, a := range nums1 {
            if a > 0 {
                idx := sort.Search(len(nums2), func(i int) bool {
                    return int64(nums2[i])*int64(a) > x
                })
                count += int64(idx)
            } else if a < 0 {
                idx := sort.Search(len(nums2), func(i int) bool {
                    return int64(nums2[i])*int64(a) > x
                })
                count += int64(len(nums2) - idx)
            } else {
                if x >= 0 {
                    count += int64(len(nums2))
                }
            }
        }
        return count
    }

    left, right := int64(-1e10), int64(1e10)
    for left < right {
        mid := (left + right) / 2
        if countLEQ(mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

Go-specific notes: Integer overflow is handled by converting products to int64. The sort.Search function replicates binary search functionality, similar to Python's bisect. Slices are used for nums2 without copying, keeping memory usage minimal.

Worked Examples

Example 1

nums1 = [2,5], nums2 = [3,4], k = 2

Step mid count_leq(mid) Adjusted Search
1 0 0 left = 1
2 ... ... ...
Final 8 2 converges

Result: 8

Example 2

nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6

The binary search counts negative, zero, and positive products separately, converging to 0.

Example 3

nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3

Binary search finds -6 as the 3rd smallest product.

Complexity Analysis

Measure Complexity Explanation
Time O((n + m) * log(max_val - min_val)) Each binary search step counts products in O(n log m), repeated log(range) times
Space O(1) No additional storage except loop variables

The complexity is efficient because the binary search drastically reduces the number of candidate product values to consider, and counting products leverages the sorted arrays with binary search.

Test Cases

# provided examples
assert Solution().kthSmallestProduct([2,5], [3,4], 2) == 8  # Example 1
assert Solution().kthSmallestProduct([-4,-2,0,3], [2,4], 6) == 0  # Example 2
assert Solution().kthSmallestProduct([-2,-1,0,1,2], [-3,-1,2,4,5], 3) == -6  # Example 3

# edge cases
assert Solution().kthSmallestProduct([0], [0], 1) == 0  # both zero
assert Solution().kthSmallestProduct([-1,-1,-1], [1,2,3], 1) == -3  # all negative * positive
assert Solution().kthSmallestProduct([1,2,3], [-1,-2,-3], 5) == -2  # mixed signs
assert Solution().kthSmallestProduct([1], [1