Scale Engineer

Kth Smallest Product of Two Sorted Arrays

Hard
#1858Time: O(m * n * log(m * n)). Generating all `m*n` products takes `O(m*n)` time. Sorting these products takes `O(m*n * log(m*n))` time.Space: O(m * n), where `m` and `n` are the lengths of `nums1` and `nums2` respectively. This is required to store all possible products.1 company
Algorithms
Binary Search
Data structures
Array
Companies
LinkedIn

Prompt

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.

Approaches

3 approaches with complexity analysis and trade-offs.

The most straightforward approach is to generate all possible products, store them in a list, sort the list, and then pick the k-th element. This method is simple to understand and implement but is highly inefficient for the given constraints.

Algorithm

  1. Initialize an empty list, products.
  2. Iterate through each element num1 in the nums1 array.
  3. For each num1, iterate through each element num2 in the nums2 array.
  4. Calculate the product p = (long)num1 * num2.
  5. Add the product p to the products list.
  6. After iterating through all pairs, sort the products list in non-decreasing order.
  7. The k-th smallest product is the element at index k-1 in the sorted list. Return products.get(k-1).

Walkthrough

This method involves a nested loop to compute every possible product of pairs (nums1[i], nums2[j]). All these m * n products are stored in a dynamic array or list. Once all products are generated, the list is sorted numerically. The k-th smallest product is then simply the element at the (k-1)-th index of this sorted list (since k is 1-based).

import java.util.ArrayList;import java.util.Collections;import java.util.List; class Solution {    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {        List<Long> products = new ArrayList<>();        for (int num1 : nums1) {            for (int num2 : nums2) {                products.add((long) num1 * num2);            }        }        Collections.sort(products);        return products.get((int) k - 1);    }}

Complexity

Time

O(m * n * log(m * n)). Generating all `m*n` products takes `O(m*n)` time. Sorting these products takes `O(m*n * log(m*n))` time.

Space

O(m * n), where `m` and `n` are the lengths of `nums1` and `nums2` respectively. This is required to store all possible products.

Trade-offs

Pros

  • Simple to understand and implement.

  • Guaranteed to be correct.

Cons

  • Exceeds time limits for large inputs due to O(m*n*log(m*n)) complexity.

  • Exceeds memory limits for large inputs as it requires storing m*n products.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem