Kth Smallest Product of Two Sorted Arrays

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.

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).

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