C++/Rust solution
We execute 4 simple algorithm on 4 sorted sub matrix to process negative rather than 1 complex algorithm.\n\nTime: O(n * log(10^10))\nSpace: O(1)\n\nRust\n\nThe
We execute 4 simple algorithm on 4 sorted sub matrix to process negative rather than 1 complex algorithm.\n\nTime: O(n * log(10^10))\nSpace: O(1)\n\nRust\n\nThe space complexity of this rust code is not O(1) since I\'m still a newbee on rust and\ndon\'t know how to implement it.\n\n```rust\nimpl Solution {\n    pub fn kth_smallest_product(nums1: Vec<i32>, nums2: Vec<i32>, k: i64) -> i64 {\n        let (neg1, pos1): (Vec<i32>, Vec<i32>) = nums1.iter().partition(|&&x| x < 0);\n        let (neg2, pos2): (Vec<i32>, Vec<i32>) = nums2.iter().partition(|&&x| x < 0);\n        let rneg1: Vec<i32> = neg1.iter().cloned().rev().collect();\n        let rneg2: Vec<i32> = neg2.iter().cloned().rev().collect();\n        let rpos1: Vec<i32> = pos1.iter().cloned().rev().collect();\n        let rpos2: Vec<i32> = pos2.iter().cloned().rev().collect();\n        let countle = |mid: i64| {\n            Solution::countle_in_sorted_matrix(&neg1, &rpos2, mid)\n                + Solution::countle_in_sorted_matrix(&rneg1, &rneg2, mid)\n                + Solution::countle_in_sorted_matrix(&rpos1, &neg2, mid)\n                + Solution::countle_in_sorted_matrix(&pos1, &pos2, mid)\n        };\n\n        let limit = 10_i64.pow(10);\n        let mut r = (-limit, limit);\n        while r.0 != r.1 {\n            let mid = r.0 + (r.1 - r.0) / 2;\n            if countle(mid) < k {\n                r.0 = mid + 1;\n            } else {\n                r.1 = mid;\n            }\n        }\n        r.0\n    }\n\n    fn countle_in_sorted_matrix(nums1: &[i32], nums2: &[i32], k: i64) -> i64 {\n        let mut j = nums2.len();\n        let mut cnt: i64 = 0;\n        for &v in nums1 {\n            while j != 0 && (nums2[j - 1] as i64) * (v as i64) > k {\n                j -= 1;\n            }\n            cnt += j as i64;\n        }\n\n        cnt\n    }\n}\n```\n\nC++\n\nO(1) space\n\n```cpp\nclass Solution {\n   public:\n    long long kthSmallestProduct(vector<int>& nums1,\n                                 vector<int>& nums2,\n                                 long long k) {\n        int64_t l = -1e10;\n        int64_t r = 1e10;\n        while (l != r) {\n            const auto mid = l + (r - l) / 2;\n            if (countle(nums1, nums2, mid) < k) {\n                l = mid + 1;\n            } else {\n                r = mid;\n            }\n        }\n        return l;\n    }\n\n    int64_t countle(const vector<int>& nums1,\n                    const vector<int>& nums2,\n                    int64_t k) {\n        const auto pos1 = partition_point(nums1.begin(),\n                                          nums1.end(),\n                                          [](const auto& x) { return x < 0; });\n        const auto pos2 = partition_point(nums2.begin(),\n                                          nums2.end(),\n                                          [](const auto& x) { return x < 0; });\n        const auto first1 = nums1.begin();\n        const auto last1 = nums1.end();\n        const auto first2 = nums2.begin();\n        const auto last2 = nums2.end();\n        return countle_in_sorted_matrix(pos1, last1, pos2, last2, k) +\n               countle_in_sorted_matrix(first1,\n                                        pos1,\n                                        make_reverse_iterator(last2),\n                                        make_reverse_iterator(pos2),\n                                        k) +\n               countle_in_sorted_matrix(make_reverse_iterator(pos1),\n                                        make_reverse_iterator(first1),\n                                        make_reverse_iterator(pos2),\n                                        make_reverse_iterator(first2),\n                                        k) +\n               countle_in_sorted_matrix(make_reverse_iterator(last1),\n                                        make_reverse_iterator(pos1),\n                                        first2,\n                                        pos2,\n                                        k);\n    }\n\n    template <class It1, class It2>\n    int64_t countle_in_sorted_matrix(\n        It1 first1, It1 last1, It2 first2, It2 last2, int64_t k) {\n        int64_t cnt = 0;\n        auto j = last2;\n        for (auto it = first1; it != last1; ++it) {\n            while (j != first2 && j[-1] * int64_t(*it) > k) {\n                --j;\n            }\n            cnt += distance(first2, j);\n        }\n        return cnt;\n    }\n};\n```
['C', 'Rust']