[C++] O((M+N)log(10^10)) time, O(1) extra space
\nclass Solution {\npublic:\n    using ll = long long;\n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        int n =
```\nclass Solution {\npublic:\n    using ll = long long;\n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        int n = nums1.size(), m = nums2.size();\n        ll lo = -(ll)1e10 - 1, hi = (ll)1e10 + 1;\n        \n        int ln = -1;\n        for (int i = 0; i < m; ++i) {\n            if (nums2[i] < 0) ln = i;\n        }\n        \n        while (hi - lo > 1) {\n            ll mid = (hi + lo) / 2;\n            // cnt number of pairs whose product <= mid\n            // This is not as simple as addition\n            // Because product of two negative integers becomes positive\n            \n            ll cnt = 0;\n            ll l = 0;\n            \n            ll pos = ln + 1, neg = ln;\n            \n            // negative in nums1\n            while (l < n && nums1[l] < 0) {\n                while (pos < m && (ll)nums1[l] * nums2[pos] > mid) pos++;   \n                cnt += m - pos;\n                while (neg >= 0 && (ll)nums1[l] * nums2[neg] <= mid) neg--;\n                cnt += ln - neg;\n                ++l;\n            }\n            \n            neg = 0, pos = m - 1;;\n            \n            // positive in nums1\n            while (l < n) {\n                while (neg <= ln && (ll)nums1[l] * nums2[neg] <= mid) neg++;\n                cnt += neg;\n                while (pos > ln && (ll)nums1[l] * nums2[pos] > mid) pos--;\n                cnt += pos - ln;\n                ++l;\n            }\n            \n            if (cnt < k) lo = mid;\n            else hi = mid;\n        }\n        \n        return hi;\n    }\n};\n```
['Two Pointers', 'Binary Search']