My notes
My notes on this Q. You are welcome if it helped you otherwise let me know how I can improve.\n\nI know this is binary search but the implementation details kil
My notes on this Q. You are welcome if it helped you otherwise let me know how I can improve.\n\nI know this is binary search but the implementation details killed me.\n\nThe first puzzle is what should the check function return. I see most solution is to return true if number of x*y <= answer is >= k. \n\nwhy both has =? Can we return true if number of x*y < answer is > k and still make it work? I still don\'t know the answer.\n\nLet me explain why return true **if number of x*y <= answer is >= k** works with my binary search template:\n\n```\nint start = 0, end = max_val;\nwhile (start + 1 < end) {\n\tint mid = (start + end)/2;\n\t\n\tif (number of x*y <= mid is >= k) // we can tell the ans is in [start, mid]\n\t\tend = mid;\n    else\n\t   start = mid;\n}\n\nif (number of x*y <= start is >= k) // if start is satsified then end will also return true, so return start.\n\treturn start;\nelse\n\treturn end;\n```\nThis is when I feel my binary search template is not very good to solve this kind of questions, because I am not confident what check() should return.\n\nOk, the next step is to work on the check function. My C++ nlogn solution will TLE everytime, the complexity is 5*10^4 * log(5*10^4) * log(10^10) = 5 *10000 * 16 * 34 = 27,200,000. I will still mention as I keep getting WA during the contest.\n```\nans = 30, x = 4 then we are looking for y <=7\nans = 30, x = -4 then we are looking for y >= -7\nans = -30, x = 4 then we are looking for y <= -8  \nans = -30, x = -4 then we are looking for y >= 8\n```\n \nThe last two cases screwed me over. Below is the binary search check() function that will TLE.\n```\nclass Solution {\npublic:\n    // <= target\n    bool check(long long target, vector<int> & nums1, vector<int> & nums2, long long k) {\n        long long cnt = 0;\n        for (int i = 0; i < nums1.size(); i++) {\n            if (nums1[i] == 0) {\n                if (target >= 0) {\n                    cnt += nums2.size();\n                }\n            } else {\n                if (nums1[i] < 0) {\n                    // we need to patch the value by 1 \n                    long long x = target / nums1[i];\n                    if (target % nums1[i] != 0) {\n                        if (target < 0)\n                            x++;\n                    }\n                    auto it = lower_bound(nums2.begin(), nums2.end(), x);\n                    cnt += nums2.size() - (it - nums2.begin());\n                } else {\n                    // we need to patch the value by 1 \n                    long long x = target / nums1[i];\n                    if (target % nums1[i] != 0) {\n                        if (target < 0)\n                            x--;\n                    }\n                    auto it = upper_bound(nums2.begin(), nums2.end(), x);\n\n                    cnt += it - nums2.begin();\n                }\n            }\n        }\n\n        return cnt >= k;\n    }\n    \n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        long long start = -1e10, end = 1e10;\n        while (start + 1 < end) {\n            long long mid = start + end >> 1;\n            if (check(mid, nums1, nums2, k)) {\n                end = mid;\n            } else {\n                start = mid;\n            }\n        }\n        \n        if (check(start, nums1, nums2, k))\n            return start;\n        \n        return end;\n    }\n}; \n```\n\nSo we need to do better and we can use two pointers to make it O(m+n). It is much easier if all numbers are positive. Otherwise we need to break it down into 4 scenarios to make sure monotonicity\uFF08\u5355\u8C03\u6027\uFF09of x*y.\n\nThe idea is to separate the two array into two negatives and two positive(include 0) and count all 4 combinations.\n\n```\ntypedef long long LL;\n\nclass Solution {\npublic:\n    vector<LL> neg1, neg2, pos1, pos2;\n    \n    // <= target\n    bool check(long long target, long long k) {\n        long long cnt = 0;\n        \n        if (target >= 0) {\n            cnt += neg1.size() * pos2.size();\n            cnt += neg2.size() * pos1.size();\n            // neg1 and neg2\n            LL i = 0, j = neg2.size()-1;\n            for (; i < neg1.size(); i++) {\n                while (j >= 0 && neg1[i] * neg2[j] <= target) {\n                    j--;\n                }\n                \n                cnt += (LL)neg2.size() - j - 1;\n            }\n            \n            // pos1 and pos2\n            i = 0, j = pos2.size()-1;\n            for (; i < pos1.size(); i++) {\n                while (j >= 0 && pos1[i] * pos2[j] > target) {\n                    j--;\n                }\n                \n                cnt += j + 1;\n            }\n           \n        } else {\n            // neg1 and pos2 \n            LL i = 0, j = 0;\n            for (; i < neg1.size(); i++) {\n                while (j < pos2.size() && neg1[i] * pos2[j] > target) {\n                    j++;\n                }\n                \n                cnt += (LL)pos2.size() - j;\n            }\n            \n            // pos1 and neg2\n            i = 0, j = 0;\n            for (; i < neg2.size(); i++) {\n                while (j < pos1.size() && neg2[i] * pos1[j] > target) {\n                    j++;\n                }\n                \n                cnt += (LL)pos1.size() - j;\n            }\n            \n        }\n        \n        return cnt >= k;\n    }\n    \n    \n    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {\n        long long start = -1e10, end = 1e10;\n        \n        for (int num : nums1) {\n            if (num < 0)\n                neg1.push_back(num);\n            else\n                pos1.push_back(num);\n        }\n        \n        for (int num : nums2) {\n            if (num < 0)\n                neg2.push_back(num);\n            else\n                pos2.push_back(num);\n        }\n        \n      \n        while (start + 1 < end) {\n            long long mid = start + end >> 1;\n            if (check(mid, k)) {\n                end = mid;\n            } else {\n                start = mid;\n            }\n        }\n        \n        if (check(start, k))\n            return start;\n        \n        return end;\n    }\n}; \n```\n
[]