# Kth Smallest Product of Two Sorted Arrays
**Difficulty:** HARD
[External](https://leetcode.com/problems/kth-smallest-product-of-two-sorted-arrays)
Canonical: https://scaleengineer.com/dsa/problems/kth-smallest-product-of-two-sorted-arrays
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
**Companies:** [LinkedIn](https://scaleengineer.com/companies/linkedin)
---
## Problem
Given two **sorted 0-indexed** integer arrays `nums1` and `nums2` as well as an integer `k`, return _the_ `kth` _(**1-based**) smallest product of_ `nums1[i] * nums2[j]` _where_ `0 <= i < nums1.length` _and_ `0 <= j < nums2.length`. 

**Example 1:**

**Input:** nums1 = [2,5], nums2 = [3,4], k = 2
**Output:** 8
**Explanation:** The 2 smallest products are:
- nums1[0] * nums2[0] = 2 * 3 = 6
- nums1[0] * nums2[1] = 2 * 4 = 8
The 2nd smallest product is 8.

**Example 2:**

**Input:** nums1 = [-4,-2,0,3], nums2 = [2,4], k = 6
**Output:** 0
**Explanation:** The 6 smallest products are:
- nums1[0] * nums2[1] = (-4) * 4 = -16
- nums1[0] * nums2[0] = (-4) * 2 = -8
- nums1[1] * nums2[1] = (-2) * 4 = -8
- nums1[1] * nums2[0] = (-2) * 2 = -4
- nums1[2] * nums2[0] = 0 * 2 = 0
- nums1[2] * nums2[1] = 0 * 4 = 0
The 6th smallest product is 0.

**Example 3:**

**Input:** nums1 = [-2,-1,0,1,2], nums2 = [-3,-1,2,4,5], k = 3
**Output:** -6
**Explanation:** The 3 smallest products are:
- nums1[0] * nums2[4] = (-2) * 5 = -10
- nums1[0] * nums2[3] = (-2) * 4 = -8
- nums1[4] * nums2[0] = 2 * (-3) = -6
The 3rd smallest product is -6.

**Constraints:**

* `1 <= nums1.length, nums2.length <= 5 * 104`
* `-105 <= nums1[i], nums2[j] <= 105`
* `1 <= k <= nums1.length * nums2.length`
* `nums1` and `nums2` are sorted.

# Approaches
## Brute Force: Generate and Sort
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.
**Time:** O(m * n * log(m * n)). Generating all `m*n` products takes `O(m*n)` time. Sorting these products takes `O(m*n * log(m*n))` time. · **Space:** O(m * n), where `m` and `n` are the lengths of `nums1` and `nums2` respectively. This is required to store all possible products.
**Pros:** Simple to understand and implement.; Guaranteed to be correct.
**Cons:** Exceeds time limits for large inputs due to `O(m*n*log(m*n))` complexity.; Exceeds memory limits for large inputs as it requires storing `m*n` products.
### Explanation
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).

```java
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);
    }
}
```
### Algorithm
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)`.

## Binary Search on the Answer with O(m log n) Count
A more efficient approach is to use binary search on the answer. Instead of searching for the k-th product among the products themselves, we search for its value within the possible range of product values. For a guessed value `mid`, we can efficiently count how many products are less than or equal to `mid`. This count helps us narrow down the search space for the answer.
**Time:** O(m * log(n) * log(Range)), where `m` and `n` are array lengths and `Range` is the difference between the maximum and minimum possible products (`~2*10^10`). We can optimize by ensuring `m <= n`, making it `O(min(m,n) * log(max(m,n)) * log(Range))`. · **Space:** O(1), as we are not storing any data structures that scale with the input size.
**Pros:** Much more efficient than brute force in both time and space.; Avoids storing all products, leading to `O(1)` space complexity.
**Cons:** The time complexity might still be too high for the tightest time limits, although it's a significant improvement over brute force.
### Explanation
The range of possible products is from `-10^5 * 10^5 = -10^10` to `10^5 * 10^5 = 10^10`. We can binary search for the k-th smallest product's value in this range.

For a given value `p`, we need a function `countLessEqual(p)` that counts pairs `(i, j)` where `nums1[i] * nums2[j] <= p`. This function can be implemented by iterating through `nums1` and, for each `num1`, using binary search on `nums2` to find how many `num2` values satisfy the condition. The condition `num1 * num2 <= p` transforms to `num2 <= p / num1` if `num1 > 0`, and `num2 >= p / num1` if `num1 < 0`.

```java
class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        long low = -10000000001L; 
        long high = 10000000001L;
        long ans = high;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (countLessEqual(nums1, nums2, mid) >= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private long countLessEqual(int[] nums1, int[] nums2, long p) {
        long count = 0;
        for (int num1 : nums1) {
            if (num1 == 0) {
                if (p >= 0) {
                    count += nums2.length;
                }
            } else if (num1 > 0) {
                count += countLE(nums2, (double) p / num1);
            } else { // num1 < 0
                count += countGE(nums2, (double) p / num1);
            }
        }
        return count;
    }

    // Counts elements <= val in a sorted array
    private int countLE(int[] nums, double val) {
        int l = 0, r = nums.length - 1, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] <= val) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans + 1;
    }

    // Counts elements >= val in a sorted array
    private int countGE(int[] nums, double val) {
        int l = 0, r = nums.length - 1, ans = nums.length;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] >= val) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return nums.length - ans;
    }
}
```
### Algorithm
1. Define a search range for the product values. A safe range is `[-10^10, 10^10]`.
2. Apply binary search on this range. Let the search variables be `low` and `high`.
3. In each step of the binary search, pick a `mid` value.
4. Count how many products `nums1[i] * nums2[j]` are less than or equal to `mid`. Let this be `count`.
5. To calculate `count`, iterate through each element `x` in `nums1`:
   - If `x > 0`, we need `y <= mid / x`. Use binary search on `nums2` to find the number of such `y`.
   - If `x < 0`, we need `y >= mid / x`. Use binary search on `nums2` to find the number of such `y`.
   - If `x == 0`, all products are `0`. If `mid >= 0`, add `n` to `count`.
6. If `count >= k`, it means `mid` could be the answer, or the answer is smaller. So, we set `ans = mid` and `high = mid - 1`.
7. If `count < k`, `mid` is too small. We set `low = mid + 1`.
8. The loop continues until `low > high`. The final `ans` is the k-th smallest product.

## Binary Search on the Answer with O(m+n) Count
This approach builds upon the binary search on the answer but optimizes the counting step. The `countLessEqual(mid)` function, which counts products less than or equal to a value `mid`, can be implemented in `O(m+n)` time instead of `O(m log n)`. This is achieved by using a two-pointer technique that leverages the sorted nature of both arrays.
**Time:** O((m+n) * log(Range)). The binary search performs `log(Range)` iterations, and each call to the optimized `countLessEqual` function takes `O(m+n)` time. · **Space:** O(1), as no extra space proportional to the input size is used.
**Pros:** The most efficient solution for this problem.; Optimal time complexity that passes all test cases.; Maintains `O(1)` space complexity.
**Cons:** The logic for the `O(m+n)` count function is complex to reason about and implement correctly, especially due to the presence of negative numbers which flips inequalities.
### Explanation
The core idea remains binary searching on the product's value. The optimization lies in the `countLessEqual` function. By exploiting the sorted property of both arrays, we can count the valid pairs in linear time. 

We iterate through `nums1` and use pointers on `nums2`. The direction of these pointers depends on the sign of the element from `nums1`. A clever way to ensure the pointers on `nums2` move monotonically is to iterate `nums1` from right to left. 

- For `nums1[i] > 0`, as `i` decreases, `nums1[i]` decreases. We need `nums2[j] <= mid / nums1[i]`. The right side of the inequality increases, so a pointer `p_pos` on `nums2` can only move from left to right.
- For `nums1[i] < 0`, as `i` decreases, `nums1[i]` also decreases (becomes more negative). We need `nums2[j] >= mid / nums1[i]`. The right side of the inequality increases. A pointer `p_neg` on `nums2` can only move from right to left.

This ensures that the pointers on `nums2` don't reset, leading to an `O(m+n)` complexity for the counting function.

```java
class Solution {
    public long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
        long low = -10000000001L;
        long high = 10000000001L;
        long ans = high;

        while (low <= high) {
            long mid = low + (high - low) / 2;
            if (countLessEqual(nums1, nums2, mid) >= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private long countLessEqual(int[] nums1, int[] nums2, long p) {
        long count = 0;
        int m = nums1.length;
        int n = nums2.length;
        
        int p_pos = 0;
        int p_neg = n - 1;
        
        for (int i = m - 1; i >= 0; i--) {
            int x = nums1[i];
            if (x > 0) {
                while (p_pos < n && (long) x * nums2[p_pos] <= p) {
                    p_pos++;
                }
                count += p_pos;
            } else if (x < 0) {
                while (p_neg >= 0 && (long) x * nums2[p_neg] <= p) {
                    p_neg--;
                }
                count += (n - 1 - p_neg);
            } else { // x == 0
                if (p >= 0) {
                    count += n;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
1. The overall structure is the same as the previous binary search approach.
2. The key improvement is in the `countLessEqual(mid)` function, which is optimized to run in `O(m+n)` time.
3. To achieve this, we use a two-pointer technique. We iterate through `nums1` from right to left.
4. We maintain two pointers for `nums2`: `p_pos` starting at `0` and `p_neg` starting at `n-1`.
5. For each `x = nums1[i]`:
   - If `x > 0`: We need `y <= mid / x`. As `i` decreases, `x` decreases, so `mid / x` increases. The pointer `p_pos` can continue moving right from its last position to find the new boundary. We add `p_pos` to the total count.
   - If `x < 0`: We need `y >= mid / x`. As `i` decreases, `x` becomes more negative, so `mid / x` increases. The pointer `p_neg` can continue moving left from its last position. We add `n - 1 - p_neg` to the total count.
   - If `x == 0`: If `mid >= 0`, add `n` to the count.
6. Since both `p_pos` and `p_neg` only move in one direction throughout the iteration of `nums1`, the total work for the `countLessEqual` function is `O(m+n)`.

# Solutions
### Java

```java
class Solution {
private
  int[] nums1;
private
  int[] nums2;
public
  long kthSmallestProduct(int[] nums1, int[] nums2, long k) {
    this.nums1 = nums1;
    this.nums2 = nums2;
    int m = nums1.length;
    int n = nums2.length;
    int a = Math.max(Math.abs(nums1[0]), Math.abs(nums1[m - 1]));
    int b = Math.max(Math.abs(nums2[0]), Math.abs(nums2[n - 1]));
    long r = (long)a * b;
    long l = (long)-a * b;
    while (l < r) {
      long mid = (l + r) >> 1;
      if (count(mid) >= k) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
private
  long count(long p) {
    long cnt = 0;
    int n = nums2.length;
    for (int x : nums1) {
      if (x > 0) {
        int l = 0, r = n;
        while (l < r) {
          int mid = (l + r) >> 1;
          if ((long)x * nums2[mid] > p) {
            r = mid;
          } else {
            l = mid + 1;
          }
        }
        cnt += l;
      } else if (x < 0) {
        int l = 0, r = n;
        while (l < r) {
          int mid = (l + r) >> 1;
          if ((long)x * nums2[mid] <= p) {
            r = mid;
          } else {
            l = mid + 1;
          }
        }
        cnt += n - l;
      } else if (p >= 0) {
        cnt += n;
      }
    }
    return cnt;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long kthSmallestProduct(vector<int> &nums1, vector<int> &nums2,
                               long long k) {
    int m = nums1.size(), n = nums2.size();
    int a = max(abs(nums1[0]), abs(nums1[m - 1]));
    int b = max(abs(nums2[0]), abs(nums2[n - 1]));
    long long r = 1LL * a * b;
    long long l = -r;
    auto count = [&](long long p) {
      long long cnt = 0;
      for (int x : nums1) {
        if (x > 0) {
          int l = 0, r = n;
          while (l < r) {
            int mid = (l + r) >> 1;
            if (1LL * x * nums2[mid] > p) {
              r = mid;
            } else {
              l = mid + 1;
            }
          }
          cnt += l;
        } else if (x < 0) {
          int l = 0, r = n;
          while (l < r) {
            int mid = (l + r) >> 1;
            if (1LL * x * nums2[mid] <= p) {
              r = mid;
            } else {
              l = mid + 1;
            }
          }
          cnt += n - l;
        } else if (p >= 0) {
          cnt += n;
        }
      }
      return cnt;
    };
    while (l < r) {
      long long mid = (l + r) >> 1;
      if (count(mid) >= k) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def kthSmallestProduct(self, nums1: List[int], nums2: List[int], k: int) -> int: def count(p: int) -> int: cnt = 0 n = len(nums2) for x in nums1: if x > 0: cnt += bisect_right(nums2, p / x) elif x < 0: cnt += n - bisect_left(nums2, p / x) else: cnt += n * int(p >= 0) return cnt mx = max(abs(nums1[0]), abs(nums1[- 1])) * max(abs(nums2[0]), abs(nums2[- 1])) return bisect_left(range(- mx, mx + 1), k, key=count) - mx

```