Kth smallest product of two sorted arrays

Array Binary Search

48.9% acceptance

Feb 25, 2026

1186

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn kth_smallest_product(nums1: Vec<i32>, nums2: Vec<i32>, k: i64) -> i64 {
    // Count how many products <= x
    let count = |x: i64| -> i64 {
      let mut cnt = 0i64;
      for &a in &nums1 {
        let a = a as i64;
        if a > 0 {
          // a*b <= x  =>  b <= x/a
          cnt += nums2.partition_point(|&b| (b as i64) * a <= x) as i64;
        } else if a < 0 {
          // a*b <= x  =>  b >= x/a (flip), count from partition point
          let n2 = nums2.len() as i64;
          cnt += n2 - nums2.partition_point(|&b| (b as i64) * a > x) as i64;
        } else {
          // a == 0, all products are 0
          if 0 <= x {
            cnt += nums2.len() as i64;
          }
        }
      }
      cnt
    };

    let mut lo = -10_000_000_000i64;
    let mut hi = 10_000_000_000i64;
    while lo < hi {
      let mid = lo + (hi - lo) / 2;
      if count(mid) >= k {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    lo
  }
}