Binary Search and Two Pointers
There are a few problems like this. Generating products directly is expensive.\n\nHowever, finding how many products are less than a given number m can be done 
There are a few problems like this. Generating products directly is expensive.\n\nHowever, finding how many products are *less* than a given number `m` can be done in a linear time by using the two pointers approach.  Initially, `p1` points to the first element in the first array, and `p2` - the last element in the second array. For each element `p1`, we move `p2` to the left if the product is higher than `m`. The number of products therefore is defined by the position of `p2` in each step.\n\nFor example, we have `19` products less than `15` for these arrays `[1, 2, 3, 4, 5] [1, 2, 3, 4, 5]`:\n\n| p1 | p2 | products |\n| - | - | - | \n|[1]|[5]|[1, 2, 3, 4, 5]\n|[2]|[5]|[2,4,6,8,10]|\n|[3]|[4]|[3, 6, 9, 12]|\n|[4]|[3]|[4, 8, 12]|\n|[5]|[2]|[5, 10]|\n\nSo, we binary-search for a value `m`, count products less than `m`, and return the smallest value where the number of products is exactly `k`.\n\nThe trick here is that we have both positive and negative numbers. I broke my head trying to figure out the pointers algebra. So, instead I just created new arrays for positives, negatives, and the reverse versions of those. The `count` function uses two pointers to count values.  We use the same function for all four cases, though we will need to pass array in the correct order, depending on:\n- All numbers are non-negative (positive and zero).\n\t- Original order for both arrays\n- All numbers are negative.\n\t- Reverse order for both arrays\n- One array is negative, and the other is positive.\n\t- Reverse order for the positive one, original for negative.\n\n**C++**\n```cpp\nlong long count(vector<int>& n1, vector<int>& n2, long long m) {\n    long long cnt = 0;\n    for (int p1 = 0, p2 = n2.size() - 1; p1 < n1.size(); ++p1) {\n        while (p2 >= 0 && (long long)n1[p1] * n2[p2] > m)\n            --p2;\n        cnt += p2 + 1;\n    }\n    return cnt;\n}\nlong long kthSmallestProduct(vector<int>& n1, vector<int>& n2, long long k) {\n    auto lp = lower_bound(begin(n1), end(n1), 0), rp = lower_bound(begin(n2), end(n2), 0);\n    vector<int> neg1(begin(n1), lp), neg2(begin(n2), rp);\n    vector<int> pos1(lp, end(n1)), pos2(rp, end(n2));\n    vector<int> pos1_r(rbegin(pos1), rend(pos1)), pos2_r(rbegin(pos2), rend(pos2));\n    vector<int> neg1_r(rbegin(neg1), rend(neg1)), neg2_r(rbegin(neg2), rend(neg2)); \n    long long l = -10000000000, r = 10000000000;\n    while (l < r) {\n        long long m = (l + r - 1) / 2, cnt = 0;\n        if (m >= 0)\n            cnt = count(neg1_r, neg2_r, m) + count(pos1, pos2, m) \n                + neg1.size() * pos2.size() + neg2.size() * pos1.size();\n        else\n            cnt = count(pos2_r, neg1, m) + count(pos1_r, neg2, m);\n        if (cnt < k) \n            l = m + 1;\n        else\n            r = m;\n    }\n    return l;\n}\n```
[]