Problem

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.

Examples

Example 1

1
2
3
4
5
6

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

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

1
2
3
4
5
6
7

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 * 10^4
  • -105 <= nums1[i], nums2[j] <= 10^5
  • 1 <= k <= nums1.length * nums2.length
  • nums1 and nums2 are sorted.

Solution

Method 1 – Binary Search on Answer

Intuition

Instead of generating all possible products, we can use binary search to guess the answer. For a guessed product x, we can efficiently count how many pairs have product ≤ x using the sorted property of the arrays. This allows us to find the k-th smallest product without explicitly storing all products.

Approach

  1. Define a helper function to count the number of pairs (i, j) such that nums1[i] * nums2[j] ≤ x.
  2. Use binary search between the minimum and maximum possible product.
  3. For each mid-value in binary search, use the helper to count pairs ≤ mid.
  4. If the count is less than k, move the left boundary up; otherwise, move the right boundary down.
  5. The left boundary will be the k-th smallest product.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

class Solution {
public:
  long long count(const vector<int>& a, const vector<int>& b, long long x) {
    int n = a.size(), m = b.size();
    long long cnt = 0;
    for (int i = 0; i < n; ++i) {
      if (a[i] == 0) {
        if (x >= 0) cnt += m;
      } else if (a[i] > 0) {
        int l = 0, r = m;
        while (l < r) {
          int mid = (l + r) / 2;
          if ((long long)a[i] * b[mid] <= x) l = mid + 1;
          else r = mid;
        }
        cnt += l;
      } else {
        int l = 0, r = m;
        while (l < r) {
          int mid = (l + r) / 2;
          if ((long long)a[i] * b[mid] <= x) r = mid;
          else l = mid + 1;
        }
        cnt += m - l;
      }
    }
    return cnt;
  }
  long long kthSmallestProduct(vector<int>& a, vector<int>& b, long long k) {
    long long l = -1e10, r = 1e10, ans = 0;
    while (l <= r) {
      long long mid = l + (r - l) / 2;
      if (count(a, b, mid) < k) l = mid + 1;
      else ans = mid, r = mid - 1;
    }
    return ans;
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

func count(a, b []int, x int64) int64 {
  var cnt int64
  m := len(b)
  for _, v := range a {
    if v == 0 {
      if x >= 0 {
        cnt += int64(m)
      }
    } else if v > 0 {
      l, r := 0, m
      for l < r {
        mid := (l + r) / 2
        if int64(v)*int64(b[mid]) <= x {
          l = mid + 1
        } else {
          r = mid
        }
      }
      cnt += int64(l)
    } else {
      l, r := 0, m
      for l < r {
        mid := (l + r) / 2
        if int64(v)*int64(b[mid]) <= x {
          r = mid
        } else {
          l = mid + 1
        }
      }
      cnt += int64(m - l)
    }
  }
  return cnt
}

func kthSmallestProduct(a []int, b []int, k int64) int64 {
  l, r := int64(-1e10), int64(1e10)
  var ans int64
  for l <= r {
    mid := l + (r-l)/2
    if count(a, b, mid) < k {
      l = mid + 1
    } else {
      ans = mid
      r = mid - 1
    }
  }
  return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

class Solution {
  private long count(int[] a, int[] b, long x) {
    int m = b.length;
    long cnt = 0;
    for (int v : a) {
      if (v == 0) {
        if (x >= 0) cnt += m;
      } else if (v > 0) {
        int l = 0, r = m;
        while (l < r) {
          int mid = (l + r) / 2;
          if ((long)v * b[mid] <= x) l = mid + 1;
          else r = mid;
        }
        cnt += l;
      } else {
        int l = 0, r = m;
        while (l < r) {
          int mid = (l + r) / 2;
          if ((long)v * b[mid] <= x) r = mid;
          else l = mid + 1;
        }
        cnt += m - l;
      }
    }
    return cnt;
  }
  public long kthSmallestProduct(int[] a, int[] b, long k) {
    long l = -10000000000L, r = 10000000000L, ans = 0;
    while (l <= r) {
      long mid = l + (r - l) / 2;
      if (count(a, b, mid) < k) l = mid + 1;
      else {
        ans = mid;
        r = mid - 1;
      }
    }
    return ans;
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

class Solution {
  private fun count(a: IntArray, b: IntArray, x: Long): Long {
    var cnt = 0L
    val m = b.size
    for (v in a) {
      if (v == 0) {
        if (x >= 0) cnt += m
      } else if (v > 0) {
        var l = 0
        var r = m
        while (l < r) {
          val mid = (l + r) / 2
          if (v.toLong() * b[mid] <= x) l = mid + 1
          else r = mid
        }
        cnt += l
      } else {
        var l = 0
        var r = m
        while (l < r) {
          val mid = (l + r) / 2
          if (v.toLong() * b[mid] <= x) r = mid
          else l = mid + 1
        }
        cnt += m - l
      }
    }
    return cnt
  }
  fun kthSmallestProduct(a: IntArray, b: IntArray, k: Long): Long {
    var l = -10000000000L
    var r = 10000000000L
    var ans = 0L
    while (l <= r) {
      val mid = l + (r - l) / 2
      if (count(a, b, mid) < k) l = mid + 1
      else {
        ans = mid
        r = mid - 1
      }
    }
    return ans
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

class Solution:
  def count(self, a: list[int], b: list[int], x: int) -> int:
    m = len(b)
    cnt = 0
    for v in a:
      if v == 0:
        if x >= 0:
          cnt += m
      elif v > 0:
        l, r = 0, m
        while l < r:
          mid = (l + r) // 2
          if v * b[mid] <= x:
            l = mid + 1
          else:
            r = mid
        cnt += l
      else:
        l, r = 0, m
        while l < r:
          mid = (l + r) // 2
          if v * b[mid] <= x:
            r = mid
          else:
            l = mid + 1
        cnt += m - l
    return cnt

  def kthSmallestProduct(self, a: list[int], b: list[int], k: int) -> int:
    l, r = -10**10, 10**10
    ans = 0
    while l <= r:
      mid = (l + r) // 2
      if self.count(a, b, mid) < k:
        l = mid + 1
      else:
        ans = mid
        r = mid - 1
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

impl Solution {
  pub fn kth_smallest_product(a: Vec<i32>, b: Vec<i32>, k: i64) -> i64 {
    fn count(a: &Vec<i32>, b: &Vec<i32>, x: i64) -> i64 {
      let m = b.len();
      let mut cnt = 0i64;
      for &v in a {
        if v == 0 {
          if x >= 0 {
            cnt += m as i64;
          }
        } else if v > 0 {
          let (mut l, mut r) = (0, m);
          while l < r {
            let mid = (l + r) / 2;
            if (v as i64) * (b[mid] as i64) <= x {
              l = mid + 1;
            } else {
              r = mid;
            }
          }
          cnt += l as i64;
        } else {
          let (mut l, mut r) = (0, m);
          while l < r {
            let mid = (l + r) / 2;
            if (v as i64) * (b[mid] as i64) <= x {
              r = mid;
            } else {
              l = mid + 1;
            }
          }
          cnt += (m - l) as i64;
        }
      }
      cnt
    }
    let (mut l, mut r) = (-1e10 as i64, 1e10 as i64);
    let mut ans = 0i64;
    while l <= r {
      let mid = l + (r - l) / 2;
      if count(&a, &b, mid) < k {
        l = mid + 1;
      } else {
        ans = mid;
        r = mid - 1;
      }
    }
    ans
  }
}

Complexity

  • ⏰ Time complexity: O((n + m) * log(maxV) * log(m)), where n and m are the lengths of the arrays and maxV is the value range.
  • 🧺 Space complexity: O(1) (ignoring recursion stack or method call overhead).