Problem statement

nums1 and nums2 are each sorted in non-decreasing order and may contain negative numbers and zeros.

Form every product nums1[i] * nums2[j] with 0 <= i < nums1.length and 0 <= j < nums2.length — there are nums1.length * nums2.length of them, counted with multiplicity. Return the k-th smallest (1-based) of these products.

CodeKairo bounds: the original problem allows values up to 10^5 and lengths up to 5 * 10^4, which needs 64-bit products and a 64-bit k. Here values are at most 10^4 in absolute value and lengths at most 10^4, so every product and every rank fits in a 32-bit integer.

Example 1

Input: nums1 = [-3,1,2], nums2 = [-1,4], k = 2
Output: -2
Explanation: The six products in order are -12, -2, -1, 3, 4, 8.

Example 2

Input: nums1 = [2,5], nums2 = [3,4], k = 2
Output: 8
Explanation: The products are 6, 8, 15 and 20.

Example 3

Input: nums1 = [-2,0,3], nums2 = [-4,-1,2], k = 6
Output: 0
Explanation: In order: -12, -4, -3, 0, 0, 0, 2, 6, 8 — the sixth is one of the three zeros.

Constraints

• 1 <= nums1.length, nums2.length <= 10^4
• -10^4 <= nums1[i], nums2[j] <= 10^4
• 1 <= k <= nums1.length * nums2.length
• nums1 and nums2 are sorted in non-decreasing order

Hints for Kth Smallest Product of Two Sorted Arrays

1. Hint 1

   Instead of finding the k-th product directly, count how many products are at most some value x.

2. Hint 2

   For a fixed nums1[i], the products with nums2 are sorted (ascending if nums1[i] > 0, descending if negative, all zero if zero) — so the count for one row is a binary search.

3. Hint 3

   The answer is the smallest x whose count reaches k; binary-search x over the product range.

How to solve Kth Smallest Product of Two Sorted Arrays

Binary search on the value of the answer. The number of products <= x is monotone in x and can be counted row by row with a binary search, because multiplying a sorted array by a fixed number keeps it sorted (or reverses it).

Approach

1. Search x in [-10^8, 10^8] for the smallest value with count(x) >= k.
2. count(x): for each a in nums1 — if a > 0, count the prefix of nums2 with a * b <= x (first index where it fails); if a < 0, a * b decreases along nums2, so count the suffix starting at the first index where a * b <= x; if a == 0, all nums2.length products are 0 and count when x >= 0.
3. Take the midpoint as lo + (hi - lo) / 2 so it floors correctly on negative ranges.
4. Return lo when the bounds meet.

Why it works

count(x) is non-decreasing in x, so the smallest x with count(x) >= k is well defined; at that x, fewer than k products are <= x - 1, so some product equals x and it is exactly the k-th smallest. The per-row searches are valid because b -> a * b is monotone for a fixed a.

Complexity

• Time — O(n1 · log n2 · log R) with R the product range (about 2 · 10^8)
• Space — O(1)

Pitfalls

• With negative bounds, (lo + hi) / 2 rounds toward zero in most languages and can loop forever — use lo + (hi - lo) / 2.
• Negative multipliers reverse the order: count the suffix, not the prefix.
• Zeros in nums1 contribute all-or-nothing depending on the sign of x.

Reference solution

Python

from typing import List

def kthSmallestProduct(nums1: List[int], nums2: List[int], k: int) -> int:
    n2 = len(nums2)

    def count_at_most(x):
        total = 0
        for a in nums1:
            if a > 0:
                lo, hi = 0, n2
                while lo < hi:
                    mid = (lo + hi) // 2
                    if a * nums2[mid] <= x:
                        lo = mid + 1
                    else:
                        hi = mid
                total += lo
            elif a < 0:
                lo, hi = 0, n2
                while lo < hi:
                    mid = (lo + hi) // 2
                    if a * nums2[mid] <= x:
                        hi = mid
                    else:
                        lo = mid + 1
                total += n2 - lo
            elif x >= 0:
                total += n2
        return total

    lo, hi = -10 ** 8, 10 ** 8
    while lo < hi:
        mid = (lo + hi) // 2
        if count_at_most(mid) >= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

Java

public static int kthSmallestProduct(int[] nums1, int[] nums2, int k) {
    int lo = -100000000, hi = 100000000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countProductsAtMost(nums1, nums2, mid) >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
}

static long countProductsAtMost(int[] nums1, int[] nums2, long x) {
    int n2 = nums2.length;
    long total = 0;
    for (int a : nums1) {
        int lo = 0, hi = n2;
        if (a > 0) {
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if ((long) a * nums2[mid] <= x) lo = mid + 1; else hi = mid;
            }
            total += lo;
        } else if (a < 0) {
            while (lo < hi) {
                int mid = (lo + hi) >>> 1;
                if ((long) a * nums2[mid] <= x) hi = mid; else lo = mid + 1;
            }
            total += n2 - lo;
        } else if (x >= 0) {
            total += n2;
        }
    }
    return total;
}

C++

long long countProductsAtMost(const vector<int>& nums1, const vector<int>& nums2, long long x) {
    int n2 = nums2.size();
    long long total = 0;
    for (int a : nums1) {
        int lo = 0, hi = n2;
        if (a > 0) {
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if ((long long)a * nums2[mid] <= x) lo = mid + 1; else hi = mid;
            }
            total += lo;
        } else if (a < 0) {
            while (lo < hi) {
                int mid = (lo + hi) / 2;
                if ((long long)a * nums2[mid] <= x) hi = mid; else lo = mid + 1;
            }
            total += n2 - lo;
        } else if (x >= 0) {
            total += n2;
        }
    }
    return total;
}

int kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, int k) {
    int lo = -100000000, hi = 100000000;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (countProductsAtMost(nums1, nums2, mid) >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
}

JavaScript

var kthSmallestProduct = function(nums1, nums2, k) {
    var n2 = nums2.length;
    var countAtMost = function(x) {
        var total = 0;
        for (var i = 0; i < nums1.length; i++) {
            var a = nums1[i];
            var lo = 0, hi = n2, mid;
            if (a > 0) {
                while (lo < hi) {
                    mid = (lo + hi) >> 1;
                    if (a * nums2[mid] <= x) lo = mid + 1; else hi = mid;
                }
                total += lo;
            } else if (a < 0) {
                while (lo < hi) {
                    mid = (lo + hi) >> 1;
                    if (a * nums2[mid] <= x) hi = mid; else lo = mid + 1;
                }
                total += n2 - lo;
            } else if (x >= 0) {
                total += n2;
            }
        }
        return total;
    };
    var lo = -100000000, hi = 100000000;
    while (lo < hi) {
        var mid = lo + Math.floor((hi - lo) / 2);
        if (countAtMost(mid) >= k) hi = mid; else lo = mid + 1;
    }
    return lo;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Design Movie Rental System Hard
• Prefix and Suffix Search Hard
• Height of Binary Tree After Subtree Removal Queries Hard
• Stamping the Grid Hard
• Maximum Number of Ways to Partition an Array Hard
• Smallest Rotation with Highest Score Hard