Optimal Approach ✅
K-th Smallest Product of Two Sorted ArraysProblem StatementGiven two sorted arrays, nums1 and nums2, containing integers (both positive and negative), we need t
## **K-th Smallest Product of Two Sorted Arrays**  

### **Problem Statement**  
Given two sorted arrays, `nums1` and `nums2`, containing integers (both positive and negative), we need to find the **k-th smallest product** formed by multiplying one element from `nums1` and one from `nums2`.

---

### **Approach: Binary Search on Answer**  
Since the arrays are sorted, the products formed by pairing their elements are also partially ordered. We leverage **binary search on the product range** to efficiently determine the k-th smallest product.  

#### **Steps:**  
1. **Define the Search Space:**  
   - The smallest possible product is \( -10^{10} \) (minimum negative product).  
   - The largest possible product is \( 10^{10} \) (maximum positive product).  
   - Set `s = -1e10` and `e = 1e10`.  

2. **Binary Search on `x`:**  
   - Check if `x` can be the k-th smallest product using `isPossible()`.  
   - If at least `k` products are **≤ `x`**, update `ans = x` and shrink the search space (`e = mid - 1`).  
   - Otherwise, move right (`s = mid + 1`).  

3. **Counting Products ≤ `x` (`isPossible` function):**  
   - For each `nums1[i]`, find how many products with `nums2[j]` are ≤ `x`.  
   - Use **binary search (`lower_bound` / `upper_bound`)** to efficiently count:  
     - **If `nums1[i] < 0`**, find the first `nums2[j]` such that `nums1[i] * nums2[j]` is ≥ `x`.  
     - **If `nums1[i] > 0`**, find the last `nums2[j]` such that `nums1[i] * nums2[j]` is ≤ `x`.  
     - **If `nums1[i] == 0`**, count all elements in `nums2` when `x ≥ 0`.  

---

### **Code Implementation**
```cpp
class Solution {
public:
    bool isPossible(vector<int>& nums1, vector<int>& nums2, long long k, long long x) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        long long count = 0;

        for (int i = 0; i < n1; i++) {
            if (nums1[i] < 0) {
                long long rem = ceil((double)x / nums1[i]);
                int ind = lower_bound(nums2.begin(), nums2.end(), rem) - nums2.begin();
                count += (n2 - ind);
            } else if (nums1[i] > 0) {
                long long rem = floor((double)x / nums1[i]);
                int ind = upper_bound(nums2.begin(), nums2.end(), rem) - nums2.begin();
                count += ind;
            } else { 
                if (x >= 0) count += n2;
            }

            if (count >= k) return true;
        }
        return count >= k;
    }

    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        long long s = -1e10, e = 1e10, ans = 0;

        while (s <= e) {
            long long mid = s + (e - s) / 2;

            if (isPossible(nums1, nums2, k, mid)) {
                ans = mid;
                e = mid - 1;
            } else {
                s = mid + 1;
            }
        }

        return ans;
    }
};
```

---

### **Complexity Analysis**  
#### **Time Complexity:**  

$$O(n \log m \log (10^{10}))$$
 
- **Binary search on product range:** \( O(\log (10^{10})) \)  
- **Counting valid products (`isPossible` function)**:  
  - Iterates through `nums1` → \( O(n) \)  
  - Each `lower_bound` / `upper_bound` operation → \( O(\log m) \)  
- **Total:** \( O(n \log m \log (10^{10})) \)  

#### **Space Complexity:**  
$$
O(1)
$$
- Only a few integer variables are used; no extra space required.

---

### **Why This Works Efficiently**
- **Avoids Sorting Large Lists:** Unlike naive approaches that generate all possible products, this uses **binary search on the result**.  
- **Binary Search + Two-Pointer Counting:** Efficiently counts elements ≤ `x` using **binary search**, reducing unnecessary computations.  

This method ensures that we find the **exact k-th smallest product efficiently**, even when `nums1` and `nums2` are large. 🚀
['Array', 'Binary Search', 'C++']