Kth Smallest Product of Two Sorted Arrays

Kth Smallest Product of Two Sorted Arrays

1. What is this problem about?

The Kth Smallest Product of Two Sorted Arrays interview question asks you to find the $k^{th}$ smallest value among all possible products arr1[i] * arr2[j]. Both arrays are already sorted. This is a significantly harder version of the sorted matrix problem because the arrays can contain negative numbers, which flips the sorted relationship during multiplication.

2. Why is this asked in interviews?

Microsoft and Google ask this to evaluate a candidate's mastery of Binary Search and Two Pointers. It evaluations whether you can handle case-based logic (positive, negative, and zero) and still achieve an $O(N \log ( ext{Range}))$ solution. It is a "Hard" Array interview pattern.

3. Algorithmic pattern used

This follows the Binary Search on Value with Two Pointers Count pattern.

1. Range: The product ranges from $-10^{10}$ to $10^{10}$.
2. Counting Function: For a value $X$, count how many pairs $(i, j)$ satisfy arr1[i] * arr2[j] <= X.
   • If arr1[i] > 0: Find $j$ such that arr2[j] <= X / arr1[i]. (Sorted).
   • If arr1[i] < 0: Find $j$ such that arr2[j] >= X / arr1[i]. (Reversed).
   • If arr1[i] == 0: If $X \geq 0$, all $j$ work.
3. Binary Search: Find the smallest $X$ such that count(X) >= k.

4. Example explanation

arr1 = [-4, -2, 0, 3], arr2 = [2, 4], k = 6.

• Range [-16, 12].
• To count pairs $\leq -5$:
  • i=0 (-4): need $arr2[j] \geq -5 / -4 = 1.25$. All $j$ (2, 4). Count = 2.
  • i=1 (-2): need $arr2[j] \geq -5 / -2 = 2.5$. $j=1$ (value 4). Count = 1.
  • i=2 (0): $0 \leq -5$ is false. Count = 0.
  • i=3 (3): need $arr2[j] \leq -5 / 3 = -1.66$. None. Count = 0. Total count $\leq -5$ is 3.

5. Common mistakes candidates make

• Case blindness: Ignoring how negative numbers change the direction of inequalities ($A < B \implies -A > -B$).
• Inefficient count: Using binary search inside the binary search ($O(N \log N \log R)$) when two pointers can count in $O(N \log R)$.
• Division by zero: Forgetting to handle the arr1[i] == 0 case separately.

6. Interview preparation tip

For problems involving products of negative numbers, split the arrays into "Positives" and "Negatives." Counting the product of two positive arrays or two negative arrays is easy; the cross-product of one positive and one negative is where the logic flips. This is a vital Math interview pattern skill.