Kth Smallest Product of Two Sorted Arrays

Kth Smallest Product of Two Sorted Arrays - Problem

Given two sorted 0-indexed integer arrays nums1 and nums2 as well as an integer k, return the k^th (1-based) smallest product of nums1[i] * nums2[j] where 0 <= i < nums1.length and 0 <= j < nums2.length.

The product of two integers can be positive, negative, or zero. You need to find the k^th smallest product among all possible products.

Input & Output

Example 1 — Basic Case

$ Input: nums1 = [2,5], nums2 = [3,4,6], k = 3

› Output: 12

💡 Note: All products: 2×3=6, 2×4=8, 2×6=12, 5×3=15, 5×4=20, 5×6=30. Sorted: [6,8,12,15,20,30]. The 3rd smallest is 12.

Example 2 — With Negative Numbers

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

› Output: 0

💡 Note: Products: -4×2=-8, -4×4=-16, -2×2=-4, -2×4=-8, 0×2=0, 0×4=0, 3×2=6, 3×4=12. Sorted: [-16,-8,-8,-4,0,0,6,12]. The 6th smallest is 0.

Example 3 — Edge Case Small Arrays

$ Input: nums1 = [1,7], nums2 = [3], k = 2

› Output: 21

💡 Note: Only two products: 1×3=3, 7×3=21. The 2nd smallest is 21.

Constraints

1 ≤ nums1.length, nums2.length ≤ 5 × 10⁴
-10⁵ ≤ nums1[i], nums2[j] ≤ 10⁵
nums1 and nums2 are sorted in non-decreasing order
1 ≤ k ≤ nums1.length × nums2.length

Visualization

Tap to expand

Understanding the Visualization

Input Arrays

Two sorted arrays nums1 and nums2

All Products

Generate products nums1[i] × nums2[j] for all pairs

Find Kth Smallest

Return the kth smallest product value

Key Takeaway

🎯 Key Insight: Binary search on answer space avoids generating all O(n²) products

Asked in

G Google 15 a Amazon 8 M Microsoft 12 A Apple 5

The key insight is to use binary search on the answer space instead of generating all products. We can efficiently count how many products are ≤ a target value using the sorted property of input arrays. Best approach is Binary Search on Answer with Time: O(n log(max-min)), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Products	O(n² log n)	O(n²)	Generate all possible products, sort them, and return the kth element
Binary Search on Answer	O(n log(max-min))	O(1)	Binary search on the answer space and count products ≤ target efficiently

Brute Force - Generate All Products — Algorithm Steps

Step 1: Generate all products nums1[i] * nums2[j] for every i,j pair
Step 2: Sort the products array in ascending order
Step 3: Return the kth element (1-based indexing)

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Products

Create all i*j combinations

Sort Products

Sort all products in ascending order

Return Kth

Return element at position k-1

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare(const void *a, const void *b) {
    long long x = *(long long*)a;
    long long y = *(long long*)b;
    if (x < y) return -1;
    if (x > y) return 1;
    return 0;
}

long long solution(int* nums1, int nums1Size, int* nums2, int nums2Size, int k) {
    long long* products = (long long*)malloc(nums1Size * nums2Size * sizeof(long long));
    int idx = 0;
    
    for (int i = 0; i < nums1Size; i++) {
        for (int j = 0; j < nums2Size; j++) {
            products[idx++] = (long long)nums1[i] * nums2[j];
        }
    }
    
    qsort(products, nums1Size * nums2Size, sizeof(long long), compare);
    long long result = products[k - 1];  // k is 1-based
    free(products);
    return result;
}

int main() {
    char line[10000];
    
    // Parse nums1
    fgets(line, sizeof(line), stdin);
    int nums1[1000], nums1Size = 0;
    char *token = strtok(line + 1, ",]");
    while (token) {
        nums1[nums1Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse nums2
    fgets(line, sizeof(line), stdin);
    int nums2[1000], nums2Size = 0;
    token = strtok(line + 1, ",]");
    while (token) {
        nums2[nums2Size++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    // Parse k
    fgets(line, sizeof(line), stdin);
    int k = atoi(line);
    
    printf("%lld\n", solution(nums1, nums1Size, nums2, nums2Size, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n² log n)

Generate n² products, then sort them

⚠ Quadratic Growth

Space Complexity

O(n²)

Store all n² products in array

⚠ Quadratic Space

23.4K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Generate All Products — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler