Return the K Smallest Pairwise Products of Two Sorted Arrays
Company: LinkedIn
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
You are given two integer arrays `nums1` and `nums2`, each sorted in non-decreasing order, and an integer `k`. Every pair of indices `(a, b)` with `0 <= a < len(nums1)` and `0 <= b < len(nums2)` forms the product `nums1[a] * nums2[b]`, so there are `len(nums1) * len(nums2)` products in total. Return the `k` smallest of them.
### Function Signature
```python
def k_smallest_products(nums1: list[int], nums2: list[int], k: int) -> list[int]:
```
### Rules
- Products are counted with multiplicity: two different index pairs contribute two products even when their values are equal, and equal values within one array are separate elements.
- Return exactly `k` values in non-decreasing order. Only values are returned, so the answer is unique.
### Constraints
- `1 <= len(nums1) <= 10^4` and `1 <= len(nums2) <= 10^4`
- `0 <= nums1[a] <= 10^5` and `0 <= nums2[b] <= 10^5`; both arrays are sorted in non-decreasing order
- `1 <= k <= min(len(nums1) * len(nums2), 10^4)`
- A product can be as large as `10^10`, which exceeds `2^31 - 1`; languages with fixed-width integers need 64-bit arithmetic.
### Examples
**Example 1**
```text
Input: nums1 = [1, 2, 4], nums2 = [1, 3, 5], k = 4
Output: [1, 2, 3, 4]
```
The nine products in sorted order are 1, 2, 3, 4, 5, 6, 10, 12 and 20.
**Example 2**
```text
Input: nums1 = [2, 2], nums2 = [3, 4], k = 3
Output: [6, 6, 8]
```
Each of the two 2s pairs with 3, giving the product 6 twice; the next smallest product is 8.
**Example 3**
```text
Input: nums1 = [0, 3], nums2 = [2, 7, 9], k = 5
Output: [0, 0, 0, 6, 21]
```
The 0 in `nums1` makes three products equal to 0, followed by 6 and 21; the largest product, 27, is excluded.
Overview: Given two sorted arrays of non-negative integers and an integer k, return the k smallest values among all pairwise products, counted with multiplicity and listed in non-decreasing order. It tests reasoning about ordered search spaces, duplicate products and products beyond the 32-bit range.
You are given two integer arrays `nums1` and `nums2`, each sorted in non-decreasing order, and an integer `k`. Every pair of indices `(a, b)` with `0 <= a < len(nums1)` and `0 <= b < len(nums2)` forms the product `nums1[a] * nums2[b]`, so there are `len(nums1) * len(nums2)` products in total. Return the `k` smallest of them.
Implement `k_smallest_products(nums1, nums2, k)`.
### Rules
- Products are counted with multiplicity: two different index pairs contribute two products even when their values are equal, and equal values within one array are separate elements.
- Return exactly `k` values in non-decreasing order. Only the product values are returned, so the answer is unique.
### Constraints
- `1 <= len(nums1) <= 10^4` and `1 <= len(nums2) <= 10^4`
- `0 <= nums1[a] <= 10^5` and `0 <= nums2[b] <= 10^5`
- Both arrays are sorted in non-decreasing order
- `1 <= k <= min(len(nums1) * len(nums2), 10^4)`
- A product can be as large as `10^10`, which exceeds `2^31 - 1`, so use 64-bit arithmetic: Java returns `long[]` and C++ returns `std::vector<long long>`. Every product stays below `2^53`, so JavaScript numbers hold it exactly.
### Examples
**Example 1**
```text
Input: nums1 = [1, 2, 4], nums2 = [1, 3, 5], k = 4
Output: [1, 2, 3, 4]
```
The nine products in sorted order are 1, 2, 3, 4, 5, 6, 10, 12 and 20; the first four are returned.
**Example 2**
```text
Input: nums1 = [2, 2], nums2 = [3, 4], k = 3
Output: [6, 6, 8]
```
Each of the two 2s pairs with 3, giving the product 6 twice; the next smallest product is 8.
Constraints
- 1 <= len(nums1) <= 10^4 and 1 <= len(nums2) <= 10^4
- 0 <= nums1[a] <= 10^5 and 0 <= nums2[b] <= 10^5
- Both nums1 and nums2 are sorted in non-decreasing order
- 1 <= k <= min(len(nums1) * len(nums2), 10^4)
- A product can be as large as 10^10, which exceeds 2^31 - 1; use 64-bit arithmetic (Java long, C++ long long)
Examples
Input: ([1, 2, 4], [1, 3, 5], 4)
Expected Output: [1, 2, 3, 4]
Explanation: Source example 1: the fourth smallest product 4 comes from nums1[2], so a row-by-row merge fails.
Input: ([2, 2], [3, 4], 3)
Expected Output: [6, 6, 8]
Explanation: Source example 2: both 2s pair with 3, so the product 6 is counted twice.
Hints
- Every element is non-negative and both arrays are sorted. How does nums1[a] * nums2[b] change when a or b increases by one?
- There can be up to 10^8 index pairs but k is at most 10^4, so try to avoid generating every product.
- Equal products from different index pairs each count separately, and a product can reach 10^10, so check your integer width.